Implement a singly linked list in Dart with operations: insert at beginning, insert at end, delete by value, and reverse the list.

Overview

Linked List is a fundamental linear data structure where elements (nodes) are stored non-contiguously in memory. Each node contains data and a reference (pointer) to the next node. Unlike arrays, linked lists don't require contiguous memory and can grow/shrink dynamically without reallocation.

Linked lists are essential for understanding dynamic memory allocation, pointer manipulation, and serve as building blocks for more complex data structures like stacks, queues, and graphs. They're frequently tested in coding interviews and are crucial for systems programming.

Key characteristics:

• Dynamic size (no pre-allocation needed)
• O(1) insertion/deletion at head
• O(n) access by index (must traverse)
• No wasted memory from pre-allocation
• Non-contiguous memory storage

When to use:

• Frequent insertions/deletions at beginning
• Unknown or highly variable size
• Implementing stacks, queues, or LRU cache
• Memory fragmentation is a concern
• Don't need random access by index

---

Core Concepts

Node Structure:

Each node contains:

1. Data: The actual value stored
2. Next: Reference to next node (null if last)

Linked List Structure:

textCopy
Head → [Data|Next] → [Data|Next] → [Data|Next] → null
       Node 1        Node 2        Node 3

Operations Complexity:

---

Basic Node Class

dartCopy
class Node<T> {
  T data;
  Node<T>? next;

  Node(this.data, [this.next]);

  @override
  String toString() => data.toString();
}

---

Complete Linked List Implementation

dartCopy
class LinkedList<T> {
  Node<T>? _head;
  Node<T>? _tail;
  int _size = 0;

  /// Insert at beginning - O(1)
  void insertAtBeginning(T data) {
    final newNode = Node(data, _head);
    _head = newNode;

    // Update tail if list was empty
    if (_tail == null) {
      _tail = newNode;
    }

    _size++;
  }

  /// Insert at end - O(1) with tail pointer
  void insertAtEnd(T data) {
    final newNode = Node<T>(data);

    if (_head == null) {
      _head = newNode;
      _tail = newNode;
    } else {
      _tail!.next = newNode;
      _tail = newNode;
    }

    _size++;
  }

  /// Insert at end - O(n) without tail pointer
  void insertAtEndNoTail(T data) {
    final newNode = Node<T>(data);

    if (_head == null) {
      _head = newNode;
      return;
    }

    // Traverse to end
    Node<T> current = _head!;
    while (current.next != null) {
      current = current.next!;
    }

    current.next = newNode;
    _size++;
  }

  /// Insert at specific position - O(n)
  void insertAt(int index, T data) {
    if (index < 0 || index > _size) {
      throw RangeError('Index out of bounds');
    }

    if (index == 0) {
      insertAtBeginning(data);
      return;
    }

    if (index == _size) {
      insertAtEnd(data);
      return;
    }

    // Traverse to position
    Node<T> current = _head!;
    for (int i = 0; i < index - 1; i++) {
      current = current.next!;
    }

    final newNode = Node(data, current.next);
    current.next = newNode;
    _size++;
  }

  /// Delete by value (first occurrence) - O(n)
  bool deleteByValue(T value) {
    if (_head == null) return false;

    // Delete head
    if (_head!.data == value) {
      _head = _head!.next;
      if (_head == null) {
        _tail = null;
      }
      _size--;
      return true;
    }

    // Delete middle or tail
    Node<T> current = _head!;
    while (current.next != null) {
      if (current.next!.data == value) {
        // Update tail if deleting last node
        if (current.next == _tail) {
          _tail = current;
        }
        current.next = current.next!.next;
        _size--;
        return true;
      }
      current = current.next!;
    }

    return false;  // Value not found
  }

  /// Delete at specific position - O(n)
  T? deleteAt(int index) {
    if (index < 0 || index >= _size) {
      throw RangeError('Index out of bounds');
    }

    T data;

    // Delete head
    if (index == 0) {
      data = _head!.data;
      _head = _head!.next;
      if (_head == null) {
        _tail = null;
      }
      _size--;
      return data;
    }

    // Delete at position
    Node<T> current = _head!;
    for (int i = 0; i < index - 1; i++) {
      current = current.next!;
    }

    data = current.next!.data;

    // Update tail if deleting last node
    if (current.next == _tail) {
      _tail = current;
    }

    current.next = current.next!.next;
    _size--;

    return data;
  }

  /// Reverse the list - Iterative - O(n)
  void reverse() {
    if (_head == null || _head!.next == null) return;

    Node<T>? prev;
    Node<T>? current = _head;
    Node<T>? next;

    _tail = _head;  // Old head becomes tail

    while (current != null) {
      next = current.next;  // Save next
      current.next = prev;  // Reverse pointer
      prev = current;       // Move prev forward
      current = next;       // Move current forward
    }

    _head = prev;  // New head is last node processed
  }

  /// Reverse the list - Recursive - O(n)
  void reverseRecursive() {
    if (_head == null || _head!.next == null) return;

    _tail = _head;  // Old head becomes tail
    _head = _reverseRecursiveHelper(_head!);
  }

  Node<T> _reverseRecursiveHelper(Node<T> node) {
    // Base case: last node
    if (node.next == null) {
      return node;
    }

    // Recursive case
    Node<T> newHead = _reverseRecursiveHelper(node.next!);
    node.next!.next = node;  // Reverse pointer
    node.next = null;        // Remove old pointer

    return newHead;
  }

  /// Search for value - O(n)
  bool contains(T value) {
    Node<T>? current = _head;

    while (current != null) {
      if (current.data == value) return true;
      current = current.next;
    }

    return false;
  }

  /// Get value at index - O(n)
  T? getAt(int index) {
    if (index < 0 || index >= _size) {
      throw RangeError('Index out of bounds');
    }

    Node<T> current = _head!;
    for (int i = 0; i < index; i++) {
      current = current.next!;
    }

    return current.data;
  }

  /// Find middle element - O(n) using slow/fast pointers
  T? getMiddle() {
    if (_head == null) return null;

    Node<T>? slow = _head;
    Node<T>? fast = _head;

    while (fast?.next != null && fast?.next?.next != null) {
      slow = slow!.next;
      fast = fast.next!.next;
    }

    return slow?.data;
  }

  /// Detect cycle - O(n) using Floyd's algorithm
  bool hasCycle() {
    if (_head == null) return false;

    Node<T>? slow = _head;
    Node<T>? fast = _head;

    while (fast?.next != null) {
      slow = slow!.next;
      fast = fast.next!.next;

      if (slow == fast) return true;
    }

    return false;
  }

  /// Convert to list - O(n)
  List<T> toList() {
    final result = <T>[];
    Node<T>? current = _head;

    while (current != null) {
      result.add(current.data);
      current = current.next;
    }

    return result;
  }

  /// Clear all nodes - O(1)
  void clear() {
    _head = null;
    _tail = null;
    _size = 0;
  }

  /// Getters
  int get size => _size;
  bool get isEmpty => _head == null;
  bool get isNotEmpty => _head != null;
  T? get first => _head?.data;
  T? get last => _tail?.data;

  @override
  String toString() {
    if (_head == null) return '[]';

    final buffer = StringBuffer('[');
    Node<T>? current = _head;

    while (current != null) {
      buffer.write(current.data);
      if (current.next != null) {
        buffer.write(' → ');
      }
      current = current.next;
    }

    buffer.write(']');
    return buffer.toString();
  }
}

---

Usage Examples

dartCopy
void main() {
  var list = LinkedList<int>();

  // Insert at beginning
  list.insertAtBeginning(10);
  list.insertAtBeginning(20);
  list.insertAtBeginning(30);
  print(list);  // [30 → 20 → 10]

  // Insert at end
  list.insertAtEnd(5);
  list.insertAtEnd(1);
  print(list);  // [30 → 20 → 10 → 5 → 1]

  // Insert at position
  list.insertAt(2, 15);
  print(list);  // [30 → 20 → 15 → 10 → 5 → 1]

  // Delete by value
  list.deleteByValue(15);
  print(list);  // [30 → 20 → 10 → 5 → 1]

  // Search
  print(list.contains(20));  // true
  print(list.contains(99));  // false

  // Access
  print(list.getAt(2));      // 10
  print(list.first);         // 30
  print(list.last);          // 1
  print(list.getMiddle());   // 10 (middle element)

  // Reverse
  list.reverse();
  print(list);  // [1 → 5 → 10 → 20 → 30]

  // Convert to list
  print(list.toList());  // [1, 5, 10, 20, 30]
}

---

Reverse List - Step-by-Step

Iterative Approach:

dartCopy
// Initial: 1 → 2 → 3 → null
// Step 1:  null ← 1   2 → 3 → null  (prev=null, current=1, next=2)
// Step 2:  null ← 1 ← 2   3 → null  (prev=1, current=2, next=3)
// Step 3:  null ← 1 ← 2 ← 3         (prev=2, current=3, next=null)
// Result:  3 → 2 → 1 → null

void reverse() {
  Node? prev;
  Node? current = head;
  Node? next;

  while (current != null) {
    next = current.next;     // Save next node
    current.next = prev;     // Reverse the link
    prev = current;          // Move prev to current
    current = next;          // Move to next node
  }

  head = prev;  // Update head to last node
}

Recursive Approach:

dartCopy
// Recursively reverse from node onwards
Node reverseRecursive(Node node) {
  // Base case: last node becomes new head
  if (node.next == null) {
    return node;
  }

  // Recursive call returns new head
  Node newHead = reverseRecursive(node.next);

  // Reverse the link
  node.next.next = node;
  node.next = null;

  return newHead;
}

---

Comparison: Array vs Linked List

When to use Array:

• Need random access by index
• Mostly read operations
• Fixed or predictable size
• Cache performance matters

When to use Linked List:

• Frequent insertions/deletions at beginning
• Unknown or highly variable size
• Implementing stacks, queues
• Memory fragmentation is a concern

---

Use Case Example: LRU Cache

Linked list is perfect for LRU (Least Recently Used) cache.

dartCopy
class LRUCacheNode<K, V> {
  K key;
  V value;
  LRUCacheNode<K, V>? prev;
  LRUCacheNode<K, V>? next;

  LRUCacheNode(this.key, this.value);
}

class LRUCache<K, V> {
  final int capacity;
  final Map<K, LRUCacheNode<K, V>> _cache = {};
  LRUCacheNode<K, V>? _head;
  LRUCacheNode<K, V>? _tail;

  LRUCache(this.capacity);

  V? get(K key) {
    if (!_cache.containsKey(key)) return null;

    final node = _cache[key]!;
    _moveToFront(node);
    return node.value;
  }

  void put(K key, V value) {
    if (_cache.containsKey(key)) {
      final node = _cache[key]!;
      node.value = value;
      _moveToFront(node);
    } else {
      final node = LRUCacheNode(key, value);
      _cache[key] = node;
      _addToFront(node);

      if (_cache.length > capacity) {
        final removed = _removeLast();
        _cache.remove(removed.key);
      }
    }
  }

  void _addToFront(LRUCacheNode<K, V> node) {
    node.next = _head;
    node.prev = null;

    if (_head != null) {
      _head!.prev = node;
    }
    _head = node;

    if (_tail == null) {
      _tail = node;
    }
  }

  void _moveToFront(LRUCacheNode<K, V> node) {
    _removeNode(node);
    _addToFront(node);
  }

  void _removeNode(LRUCacheNode<K, V> node) {
    if (node.prev != null) {
      node.prev!.next = node.next;
    } else {
      _head = node.next;
    }

    if (node.next != null) {
      node.next!.prev = node.prev;
    } else {
      _tail = node.prev;
    }
  }

  LRUCacheNode<K, V> _removeLast() {
    final node = _tail!;
    _removeNode(node);
    return node;
  }
}

void main() {
  var cache = LRUCache<int, String>(3);

  cache.put(1, 'one');
  cache.put(2, 'two');
  cache.put(3, 'three');

  print(cache.get(2));  // 'two' (moves to front)

  cache.put(4, 'four');  // Evicts key 1 (least recently used)
  print(cache.get(1));   // null (evicted)
  print(cache.get(3));   // 'three'
}

---

Advanced Operations

1. Detect Cycle (Floyd's Algorithm)

dartCopy
bool hasCycle() {
  if (head == null) return false;

  Node? slow = head;
  Node? fast = head;

  while (fast?.next != null) {
    slow = slow!.next;
    fast = fast.next!.next;

    if (slow == fast) return true;  // Cycle detected
  }

  return false;
}

2. Find Middle Element

dartCopy
T? findMiddle() {
  if (head == null) return null;

  Node? slow = head;
  Node? fast = head;

  while (fast?.next != null && fast?.next?.next != null) {
    slow = slow!.next;
    fast = fast.next!.next;
  }

  return slow?.data;
}

3. Remove Duplicates (Sorted List)

dartCopy
void removeDuplicates() {
  Node? current = head;

  while (current?.next != null) {
    if (current!.data == current.next!.data) {
      current.next = current.next!.next;
    } else {
      current = current.next;
    }
  }
}

---

Best Practices

1. Always Check for Null

dartCopy
// ✅ Good - null safety
if (head != null) {
  print(head.data);
}

// ❌ Bad - may throw
print(head!.data);  // Crashes if null!

2. Update Tail Pointer

dartCopy
// ✅ Good - maintain tail for O(1) append
void insertAtEnd(T data) {
  final newNode = Node(data);
  if (head == null) {
    head = tail = newNode;
  } else {
    tail!.next = newNode;
    tail = newNode;
  }
}

// ❌ Bad - O(n) every append
void insertAtEndSlow(T data) {
  Node current = head;
  while (current.next != null) {
    current = current.next;
  }
  current.next = Node(data);
}

3. Use Dart List for Most Cases

dartCopy
// ✅ Good - use built-in List for general purpose
var list = <int>[1, 2, 3];
list.insert(0, 0);  // Still efficient enough

// ❌ Overkill - custom linked list for simple use
var linkedList = LinkedList<int>();  // Use only when needed

---

Interview Tips

Common Interview Questions:

Q: "Reverse a linked list"

• Show both iterative and recursive approaches
• Explain time O(n) and space O(1) for iterative
• Recursive has O(n) space due to call stack

Q: "Detect cycle in linked list"

• Use Floyd's cycle detection (slow/fast pointers)
• Slow moves 1 step, fast moves 2 steps
• If they meet, there's a cycle

Q: "Find middle element"

• Use two pointers (slow/fast)
• Slow moves 1, fast moves 2
• When fast reaches end, slow is at middle

Q: "Merge two sorted linked lists"

• Compare heads, take smaller
• Move pointer of chosen list forward
• Repeat until one list is exhausted

Follow-up Questions:

• "LinkedList vs ArrayList?" → Insert/delete vs random access
• "Singly vs Doubly linked list?" → Memory vs bidirectional traversal
• "When to use linked list?" → Unknown size, frequent head operations

Red Flags to Avoid:

• Not handling null pointers ❌
• Losing reference to head node ❌
• Forgetting to update tail pointer ❌
• Not knowing when to use vs array ❌

---

Resources

• Linked List - Wikipedia
• Dart List Class - Built-in Alternative
• Linked List Visualization