Linked List in Dart

In computer science, a linked list is a fundamental data structure that consists of a sequence of nodes, where each node holds a value and a reference to the next node in the sequence. Linked lists are dynamic data structures, meaning they can grow or shrink in size during program execution, unlike arrays that have a fixed size.

In this article, we’ll explore the concept of linked lists, their advantages, and how to implement and utilize them in Dart.

Advantages of Linked Lists

Linked lists offer several advantages over other data structures, such as arrays:

1. Dynamic Size: Linked lists can easily grow or shrink in size at runtime by adding or removing nodes, respectively.
2. Efficient Insertions and Deletions: Inserting or deleting an element at the beginning or middle of a linked list is generally faster than doing the same operations on an array because linked lists don’t require shifting elements.
3. Flexible Memory Allocation: Linked lists use memory efficiently, allocating memory for each node as needed. This makes them suitable for situations where memory allocation is limited or unpredictable.

Implementing a Linked List in Dart

To implement a linked list in Dart, we’ll define two classes: Node and LinkedList.

Node Class

The Node class represents a single node in the linked list. It contains two properties: value, which holds the node's value, and next, which is a reference to the next node in the sequence.

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

  Node(this.value);
}

LinkedList Class

The LinkedList class encapsulates the linked list and provides operations to manipulate it. It maintains a reference to the first node in the list, known as the head.

class LinkedList<T> {
  Node<T>? head; // Reference to the first node in the list

  LinkedList();

  bool get isEmpty => head == null; // Check if the list is empty

  // Add a new node to the end of the list
  void add(T value) {
    final newNode = Node<T>(value);
    if (isEmpty) {
      // If the list is empty, set the new node as the head
      head = newNode;
    } else {
      var current = head;
      while (current!.next != null) {
        // Traverse the list to find the last node
        current = current.next;
      }
      current.next = newNode; // Set the new node as the next node of the last node
    }
  }

  // Remove the first node with the given value
  void remove(T value) {
    if (isEmpty) return;

    if (head!.value == value) {
      // If the value is in the head node, update the head to the next node
      head = head.next;
      return;
    }

    var current = head;
    while (current!.next != null) {
      if (current.next!.value == value) {
        // If the value is found in the next node, skip the next node
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
  }

  // Print the values of all nodes in the list
  void printList() {
    var current = head;
    while (current != null) {
      print(current.value);
      current = current.next;
    }
  }
}

Example Usage

Let’s see an example of how to use the LinkedList class we just defined:

void main() {
  final linkedList = LinkedList<int>();

  linkedList.add(10);
  linkedList.add(20);
  linkedList.add(30);

  linkedList.printList(); // Output: 10 20 30

  linkedList.remove(20);

  linkedList.printList(); // Output: 10 30
}

Now, let’s represent the linked list visually using ASCII art at each step:

Initial state: Empty linked list

head
 |
 v
null

After adding the node with value 10:

     head
       |
       v
      +---+
      | 10 |
      +---+
      |    |
      v    v
     null  null

After adding the node with value 20:

     head
       |
       v
      +---+      +---+
      | 10 | ---> | 20 |
      +---+      +---+
      |           |
      v           v
     null        null

After adding the node with value 30:

     head
       |
       v
      +---+      +---+      +----+
      | 10 | ---> | 20 | ---> | 30 |
      +---+      +---+      +----+
      |           |           |
      v           v           v
     null        null        null

And now the linked list contains nodes with values 10, 20, and 30 in sequence. Each node is connected to the next node through the next reference.

remove()

After removing the node with value 20:

     head
       |
       v
      +---+      +----+
      | 10 | ---> | 30 |
      +---+      +----+
      |           |
      v           v
     null        null

And now the node with value 20 has been successfully removed from the linked list.

Conclusion

Linked lists are powerful data structures that provide dynamic size and efficient insertions and deletions. In this article, we explored the concept of linked lists and implemented a basic linked list in Dart.

Linked lists offer flexibility and efficient memory allocation, making them suitable for various scenarios. They are particularly useful when the size of the data structure needs to change frequently, or when efficient insertions and deletions are required.

By using the Node and LinkedList classes provided in this article, you can easily create and manipulate linked lists in your Dart programs. Feel free to extend the functionality of the LinkedList class to suit your specific requirements.

Remember to consider the trade-offs of using linked lists. While they excel in certain operations, they may not be the best choice for tasks that involve random access or require contiguous memory allocation.

As you continue your journey in programming, further exploring data structures and their applications will enhance your problem-solving skills and enable you to design efficient algorithms. Linked lists are just the tip of the iceberg when it comes to the exciting world of data structures.

Keep experimenting, practicing, and diving into new concepts. Happy coding!