What is a linked list?

A linked list is a sequence of objects of the same type, where each object leads to the next and contains some information. Each such object (node) always holds at least these two pieces of information: a value and a reference to the next node. In some cases, a node may also point, besides to the next node, to the previous one.

When we want to traverse each object in the list, we start from the first one, called the head, and move through the subsequent nodes until the last one. The last object has the characteristic that its pointer points to nowhere (null).

Advantages and Disadvantages

The main advantages of a linked list are its dynamic nature — you can add and delete as many elements as you want without having to declare the size in advance — and the ease of insertion or deletion of elements, since you only need to modify the pointers of the objects. The biggest disadvantage is the search speed, as you often have to traverse the entire list to find a specific object.

Example In Python

# Define a Node class
class Node:
    def __init__(self, data):
        self.data = data  # Store the data
        self.next = None  # Pointer to the next node

# Define a LinkedList class
class LinkedList:
    def __init__(self):
        self.head = None  # Start with an empty list

    # Function to add a new node at the end
    def append(self, data):
        new_node = Node(data)
        if not self.head:  # If the list is empty
            self.head = new_node
            return
        # Otherwise, find the last node
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    # Function to print the list
    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage:
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list()
                                        

Example In Java

                                            // Define a Node class
class Node {
    int data;
    Node next;

    // Constructor
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Define the LinkedList class
class LinkedList {
    Node head; // head of the list

    // Method to add a new node at the end
    public void append(int data) {
        Node newNode = new Node(data);

        // If the linked list is empty, make the new node the head
        if (head == null) {
            head = newNode;
            return;
        }

        // Otherwise, traverse to the end
        //of the list and add the new node
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Method to print the linked list
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

// Example usage
public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.append(1);
        list.append(2);
        list.append(3);

        list.printList();
    }
}