What are and how to use LinkedList

LINKED LIST, or linked list, is a collection of elements where each of them is linked to other elements forming a sequence.

A LINKED LIST consists of nodes linked to each other. Each of these nodes consists of a value (the element) and a link to the next node in the sequence. The first node of the list is known as the head, while the last node is called the tail.

To traverse a LINKED LIST, we have to “jump” from node to node, through each of the links. It is not possible to access through an index, we have to traverse the entire chain.

On the other hand, the double LinkedList is an improved version of the “simple” linked list, where each node contains a link to the next and the previous node. This allows traversal in both forward and backward directions.

The most common operations in a LINKED LIST are:

• Insertion: Allows adding a new node at any position in the list.
• Deletion: Allows removing a node from the list, adjusting the links properly.
• Access: Allows accessing an element at a specific position in the list.
• Search: Allows searching for a specific element in the list by traversing the nodes in order.

Properties

When to use a LinkedList

First of all, unless in class exercises, it is normal that if you have to use a LINKED LIST you always use a Double LinkedList. The overhead is very small, and provides the versatility of going in both directions.

On the other hand, the main use of a LINKED LIST (Double) is to have a collection in which we can quickly add or remove elements at any position.

A LINKED LIST (Double) is a series of elements forming “a chain”. The great advantage it has is that at any time we can “split” the chain, and add or remove an element from the middle.

On the other hand, LINKED LIST have the disadvantage of not being able to access by index. If we want to go to position 237, we will have to start from the first element, and jump to node 237. That is, random access is very slow.

Therefore, LINKED LIST only make sense in collections that have “a lot of movement” of adding and removing elements in the middle.

Example of LinkedList in different programming languages:

The syntax for using a LinkedList may vary depending on the programming language being used.

Next, we will see examples in some popular languages:

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        LinkedList<int> linkedList = new LinkedList<int>();

        linkedList.AddLast(5);
        linkedList.AddLast(10);
        linkedList.AddLast(15);

        foreach (int item in linkedList)
        {
            Console.WriteLine(item);
        }
    }
}

#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> linkedList;

    linkedList.push_back(5);
    linkedList.push_back(10);
    linkedList.push_back(15);

    for (int item : linkedList)
    {
        cout << item << endl;
    }

    return 0;
}

class Node {
    constructor(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class DoubleLinkedList {
    constructor() {
        this.head = null;
    }

    addNode(data) {
        const newNode = new Node(data);
        if (this.head === null) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next !== null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.prev = current;
        }
    }
}

const list = new DoubleLinkedList();
list.addNode(1);
list.addNode(2);
list.addNode(3);

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoubleLinkedList:
    def __init__(self):
        self.head = None

    def addNode(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = new_node
            new_node.prev = current

# Usage of the Double Linked List
list = DoubleLinkedList()
list.addNode(1)
list.addNode(2)
list.addNode(3)

Internal operation Advanced

A LINKED LIST consists of nodes. Each of these nodes has the element it contains, and a reference to the next node.

A doubly linked LINKED LIST is similar to a LinkedList, but each node has a reference to both the next and the previous node. This allows traversing the list in both forward and backward directions.

Efficiency

A LINKED LIST is a linked data structure where each node contains a value and a reference to the next node.

Reading elements in a LinkedList requires traversing them sequentially, which has a linear time complexity O(n). Searching in a LinkedList also requires traversing it sequentially, which has a linear time complexity O(n).

However, insertion and deletion of elements in a LinkedList are very efficient, as it only requires modifying the links. So it has a constant time complexity O(1).

Read more about collection efficiency read more