Linked List Data Structure: Complete Guide with Code Examples

A linked list is a linear data structure where elements (called nodes) are stored in separate memory locations and connected via pointers. Unlike an array, a linked list does not store elements in contiguous memory — each node holds the data and a reference to the next node.

Linked lists are a fundamental CS topic that appear in every data structures course and in roughly 20 % of coding interview questions at major tech companies.

Quick reference

* O(1) tail insert when you maintain a tail pointer.

What is a node?

Every linked list is built from nodes. A node contains two things:

1. Data — the value stored (integer, string, object, etc.)
2. Next pointer — a reference to the next node (or null/None at the end)

[ data | next ] → [ data | next ] → [ data | next ] → null
   head                                  tail

Types of linked lists

Singly linked list

Each node has one pointer: next. Traversal goes only forward.

head
 ↓
[10 | •] → [20 | •] → [30 | null]

Doubly linked list

Each node has two pointers: prev and next. Traversal goes both ways.

null ← [10 | •] ↔ [20 | •] ↔ [30 | •] → null
       head                     tail

Circular linked list

The tail's next pointer points back to the head instead of null.

[10 | •] → [20 | •] → [30 | •]
 ↑                          |
 └──────────────────────────┘

Singly linked list — implementation

Python

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

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

    # Insert at head — O(1)
    def prepend(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    # Insert at tail — O(n)
    def append(self, data):
        node = Node(data)
        if not self.head:
            self.head = node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = node

    # Delete first occurrence — O(n)
    def delete(self, data):
        if not self.head:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                return
            current = current.next

    # Search — O(n)
    def search(self, data):
        current = self.head
        while current:
            if current.data == data:
                return True
            current = current.next
        return False

    # Print all nodes — O(n)
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" → ".join(elements) + " → null")


# Usage
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.prepend(5)
ll.display()  # 5 → 10 → 20 → 30 → null
ll.delete(20)
ll.display()  # 5 → 10 → 30 → null

JavaScript

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

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

  prepend(data) {
    const node = new Node(data);
    node.next = this.head;
    this.head = node;
  }

  append(data) {
    const node = new Node(data);
    if (!this.head) { this.head = node; return; }
    let cur = this.head;
    while (cur.next) cur = cur.next;
    cur.next = node;
  }

  delete(data) {
    if (!this.head) return;
    if (this.head.data === data) { this.head = this.head.next; return; }
    let cur = this.head;
    while (cur.next) {
      if (cur.next.data === data) { cur.next = cur.next.next; return; }
      cur = cur.next;
    }
  }

  toArray() {
    const arr = [];
    let cur = this.head;
    while (cur) { arr.push(cur.data); cur = cur.next; }
    return arr;
  }
}

const ll = new LinkedList();
ll.append(10); ll.append(20); ll.append(30);
console.log(ll.toArray()); // [10, 20, 30]

Java

public class LinkedList {
    static class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; }
    }

    private Node head;

    public void prepend(int data) {
        Node node = new Node(data);
        node.next = head;
        head = node;
    }

    public void append(int data) {
        Node node = new Node(data);
        if (head == null) { head = node; return; }
        Node cur = head;
        while (cur.next != null) cur = cur.next;
        cur.next = node;
    }

    public void delete(int data) {
        if (head == null) return;
        if (head.data == data) { head = head.next; return; }
        Node cur = head;
        while (cur.next != null) {
            if (cur.next.data == data) { cur.next = cur.next.next; return; }
            cur = cur.next;
        }
    }

    public void display() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.data + " → ");
            cur = cur.next;
        }
        System.out.println("null");
    }
}

Go

package main

import "fmt"

type Node struct {
    Data int
    Next *Node
}

type LinkedList struct {
    Head *Node
}

func (l *LinkedList) Prepend(data int) {
    l.Head = &Node{Data: data, Next: l.Head}
}

func (l *LinkedList) Append(data int) {
    node := &Node{Data: data}
    if l.Head == nil { l.Head = node; return }
    cur := l.Head
    for cur.Next != nil { cur = cur.Next }
    cur.Next = node
}

func (l *LinkedList) Delete(data int) {
    if l.Head == nil { return }
    if l.Head.Data == data { l.Head = l.Head.Next; return }
    cur := l.Head
    for cur.Next != nil {
        if cur.Next.Data == data { cur.Next = cur.Next.Next; return }
        cur = cur.Next
    }
}

func (l *LinkedList) Display() {
    cur := l.Head
    for cur != nil {
        fmt.Printf("%d → ", cur.Data)
        cur = cur.Next
    }
    fmt.Println("nil")
}

Doubly linked list — implementation

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):          # O(1) with tail pointer
        node = DNode(data)
        if not self.tail:
            self.head = self.tail = node
            return
        node.prev = self.tail
        self.tail.next = node
        self.tail = node

    def prepend(self, data):         # O(1)
        node = DNode(data)
        if not self.head:
            self.head = self.tail = node
            return
        node.next = self.head
        self.head.prev = node
        self.head = node

    def delete(self, node: DNode):   # O(1) when you have the node reference
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next    # deleting head
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev    # deleting tail

    def display_forward(self):
        cur, out = self.head, []
        while cur:
            out.append(str(cur.data))
            cur = cur.next
        print(" ↔ ".join(out))

    def display_backward(self):
        cur, out = self.tail, []
        while cur:
            out.append(str(cur.data))
            cur = cur.prev
        print(" ↔ ".join(out))

Core operations — time and space complexity

Linked list vs array

Use an array when: you need fast index access, binary search, or cache-friendly iteration.

Use a linked list when: you have frequent head/tail insertions or deletions, need O(1) splicing, or are building higher-level structures (stack, queue, deque, LRU cache).

Common linked list interview problems

1. Reverse a singly linked list

def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev          # new head

Time: O(n) · Space: O(1)

2. Detect a cycle (Floyd's tortoise and hare)

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Time: O(n) · Space: O(1)

3. Find middle node

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow           # middle (or second middle for even length)

4. Merge two sorted linked lists

def merge_sorted(l1, l2):
    dummy = Node(0)
    cur = dummy
    while l1 and l2:
        if l1.data <= l2.data:
            cur.next = l1; l1 = l1.next
        else:
            cur.next = l2; l2 = l2.next
        cur = cur.next
    cur.next = l1 or l2
    return dummy.next

5. Remove Nth node from end

def remove_nth_from_end(head, n):
    dummy = Node(0); dummy.next = head
    fast = slow = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next
    return dummy.next

6. Check if linked list is palindrome

def is_palindrome(head):
    # Step 1: find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # Step 2: reverse second half
    prev, cur = None, slow
    while cur:
        nxt = cur.next; cur.next = prev; prev = cur; cur = nxt
    # Step 3: compare
    left, right = head, prev
    while right:
        if left.data != right.data:
            return False
        left = left.next; right = right.next
    return True

7. Find start of cycle

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # Move one pointer to head
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow   # start of cycle
    return None

Linked list as stack and queue

Stack (LIFO) — prepend + delete head

class Stack:
    def __init__(self):
        self._list = LinkedList()

    def push(self, data):
        self._list.prepend(data)   # O(1)

    def pop(self):
        if not self._list.head:
            raise IndexError("empty")
        val = self._list.head.data
        self._list.head = self._list.head.next
        return val                 # O(1)

    def peek(self):
        return self._list.head.data if self._list.head else None

Queue (FIFO) — append + delete head

class Queue:
    def __init__(self):
        self.head = self.tail = None

    def enqueue(self, data):        # O(1) with tail pointer
        node = Node(data)
        if self.tail:
            self.tail.next = node
        self.tail = node
        if not self.head:
            self.head = node

    def dequeue(self):              # O(1)
        if not self.head:
            raise IndexError("empty")
        val = self.head.data
        self.head = self.head.next
        if not self.head:
            self.tail = None
        return val

Real-world uses of linked lists

LRU cache — linked list + hash map

The most famous linked-list-in-production pattern is the LRU (Least Recently Used) cache. It achieves O(1) get and O(1) put by combining a doubly linked list with a hash map.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()  # preserves insertion order

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)   # mark as recently used
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # evict LRU (first item)

Common mistakes

Linked list vs array vs deque

Practical note: In Python, collections.deque IS a doubly linked list under the hood. In Java, LinkedList implements both List and Deque. You almost never implement a linked list from scratch in production — you implement them to demonstrate understanding in interviews.

FAQ

Q: When should I use a linked list instead of an array? Use a linked list when you have very frequent insertions or deletions at the head or tail and don't need index access. In practice, collections.deque (Python) or ArrayDeque (Java) are often better choices because they provide O(1) operations at both ends with better cache performance than a custom linked list.

Q: Why is binary search not practical on a linked list? Binary search requires O(1) random access to jump to the middle element. A linked list can only reach the middle by traversing from the head — O(n) — making the algorithm O(n log n) overall, worse than linear search O(n).

Q: What is the difference between a singly and doubly linked list in terms of memory? A doubly linked list stores two pointers per node (prev and next) instead of one. On a 64-bit system, each pointer is 8 bytes, so a doubly linked list uses 8 extra bytes per node. For a list of 1 million integers, that's ~8 MB of extra overhead.

Q: How do I detect a cycle in a linked list? Use Floyd's cycle detection algorithm (two pointers, slow and fast). The slow pointer advances one step; the fast pointer advances two steps. If they ever meet, there is a cycle. Time O(n), space O(1). See the code example above.

Q: How is a linked list used in a hash table? Most hash tables handle collisions with separate chaining: each bucket holds a linked list of all key-value pairs that hash to that bucket. Lookup traverses the list at the target bucket — O(1) average, O(n) worst case.

Q: What is the difference between a linked list and a binary tree? A linked list is a linear structure — each node has at most one successor. A binary tree is a hierarchical structure — each node has at most two children (left and right). Both use nodes with pointers, but binary trees support O(log n) search when balanced, which a linked list cannot.