Linked list

In computer science, a linked list is a data structure that is a linear collection of items whose order is not given by their physical placement in memory. Instead, each item links to the next item. The last item links to a terminator used to mark the end of the list.

Types of linked lists

Singly linked list

A singly linked list whose items have two fields: a value and a link to the next item

A singly linked list is a linked list that's used to store items in order. Each item is usually called a node. A node has two parts: the data it holds and a link to the next node. The first node is called the head. The last node points to nothing, indicating the end of the list. One can move through the list one step at a time, following the links from one node to the next.

Doubly linked list

A doubly linked list whose items have three fields: a value, the link forward to the next item, and the link backward to the previous item

A doubly linked list is a type of linked list. Each node in the list holds three things: a piece of data, a pointer to the next node, and a pointer to the previous node. The first node, called the head, has a previous pointer that is null. The last node, called the tail, has a next pointer that is null. This allows the list to be traversed in either direction.

Circular linked list

A circular linked list

A circular linked list is a variation of a linked list where the last node's pointer does not point to a null value. Instead, it points back to the first node, called the head, forming a continuous loop. This structure has no natural beginning or end, allowing traversal to start from any node and continue through the entire list.

Linked list algorithms

Creating a singly linked list

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

public class LinkedList {
    public static void main(String[] args) {
        // Create three nodes
        Node first = new Node(10);
        Node second = new Node(20);
        Node third = new Node(30);
        
        // Link the nodes together
        first.next = second;
        second.next = third;
        // The third node's next remains null, indicating the list end
    }
}

Reversing a singly linked list

Item reverseList(Item head) {
    Item prev = null;
    Item curr = head;
    while (curr != null) {
        Item following = curr.next;
        curr.next = prev;
        prev = curr;
        curr = following;
    }
    return prev;
}