Data structure in Dart & Flutter – Linked Lists

1. What is a Linked List?

A linked list is a linear data structure where elements (called nodes) are connected using pointers (references).

Each node contains:

data → the actual value
next → a reference (pointer) to the next node

Unlike arrays:

Memory is not contiguous.
Dynamic size (can grow/shrink easily).
Insertions/deletions are faster (no shifting like arrays).

2. Types of Linked Lists

1. Singly Linked List

Each node points to the next node.

[Data|Next] -> [Data|Next] -> [Data|Next] -> null

2. Doubly Linked List

Each node has two pointers: prev and next.

null <- [Prev|Data|Next] <-> [Prev|Data|Next] -> null

3. Circular Linked List

The last node points back to the first node, forming a circle.

[Data|Next] -> [Data|Next] -> [Data|Next]
      ^---------------------------------|

3. Singly Linked List in Dart

Let’s implement a basic Singly Linked List.

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

  Node(this.data);
}

class SinglyLinkedList<T> {
  Node<T>? head;

  // Insert at end
  void insert(T data) {
    Node<T> newNode = Node(data);
    if (head == null) {
      head = newNode;
      return;
    }
    Node<T>? current = head;
    while (current!.next != null) {
      current = current.next;
    }
    current.next = newNode;
  }

  // Delete by value
  void delete(T data) {
    if (head == null) return;
    if (head!.data == data) {
      head = head!.next;
      return;
    }
    Node<T>? current = head;
    while (current!.next != null) {
      if (current.next!.data == data) {
        current.next = current.next!.next;
        return;
      }
      current = current.next;
    }
  }

  // Traverse and print
  void printList() {
    Node<T>? current = head;
    while (current != null) {
      print(current.data);
      current = current.next;
    }
  }
}

void main() {
  var list = SinglyLinkedList<int>();
  list.insert(10);
  list.insert(20);
  list.insert(30);
  list.printList();

  list.delete(20);
  print("After deletion:");
  list.printList();
}

Output:

10
20
30
After deletion:
10
30

4. Real-World Use Case in Flutter

Imagine a music playlist app.

Songs are linked one after another.
If you delete a song, you just reconnect the links without shifting all elements (like arrays).

Example:

class Song {
  String title;
  Song(this.title);
}

void main() {
  var playlist = SinglyLinkedList<Song>();
  playlist.insert(Song("Song A"));
  playlist.insert(Song("Song B"));
  playlist.insert(Song("Song C"));

  playlist.printList(); // Song A, Song B, Song C

  playlist.delete(Song("Song B")); // Won’t work directly because objects differ
  // For real Flutter app → use IDs or unique keys
}

In a Flutter app, this could back a dynamic playlist screen.

5. Common Linked List Problems

Reverse a Linked List

Node<T>? reverse<T>(Node<T>? head) {
  Node<T>? prev;
  Node<T>? current = head;
  while (current != null) {
    Node<T>? next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

Detect a Cycle (Floyd’s Algorithm)

bool hasCycle<T>(Node<T>? head) {
  Node<T>? slow = head;
  Node<T>? fast = head;
  while (fast != null && fast.next != null) {
    slow = slow!.next;
    fast = fast.next!.next;
    if (slow == fast) return true;
  }
  return false;
}

6. Complexity

Operation	Singly LL	Doubly LL
Access	O(n)	O(n)
Insert Head	O(1)	O(1)
Insert Tail	O(n)	O(1) if tail kept
Delete Node	O(n)	O(1) if pointer given

7. Diagrams / Illustrations

You can add these diagrams for clarity:

Singly Linked List diagram → [10|next] → [20|next] → [30|null]
Doubly Linked List diagram → null ← [10|↔] ↔ [20|↔] ↔ [30|null]
Circular Linked List → loop back to first node
Music Playlist UI in Flutter showing linked tracks

8. Summary

Linked Lists allow dynamic memory allocation.
Efficient for insertions/deletions, less efficient for random access.
Used in music playlists, undo/redo, caches.
Dart implementation requires custom Node and LinkedList classes.

Coming Next (Module 3 Preview)

In Module 3, we’ll cover Stacks & Queues:

Stack → Undo/Redo, recursion, expression evaluation
Queue → Scheduling, buffering, BFS traversal