How these 2 algorithms' outputs are different from each other in a linked list data structure

user_5418940 0
Viewed 25

I have created a Linked-List data structure as follows:

class Node<T> {
  T value;
  Node<T>? nextNode;
  Node({required this.value, this.nextNode});

  @override
  String toString() {
    if (nextNode == null) return '$value';
    return '$value --> ${nextNode.toString()}';
  }
}

Then create a LinkedList class that holds a head and tail node, and by printing the head, we can see the list of values.

class LinkedList<E> {
  Node<E>? head;
  Node<E>? tail;

  bool get isEmpty => head == null;
  // To add a node in front of the list 
  void push(E value) {
    if (isEmpty) {
      head = Node(value: value);
      tail = head;
      return;
    }
    head = Node(value: value, nextNode: head);
  }

  // To add a node behind the list
  void append(E value) {
    if (isEmpty) {
      push(value);
      return;
    }
    tail!.nextNode = Node(value: value);
    tail = tail!.nextNode;  //* variation 1
    // tail = Node(value: value);  //** variation 2
  }

  @override
  String toString() {
    return head.toString();
  }
}

As you can see in the comments we could create 2 variations of the append algorithm.

The first one has tail = tail!.nextNode; and the second one has tail = Node(value: value); line. The first variation works as we expected which means when we print the list it prints correctly as you can see here:

void main() {
  final list = LinkedList<int>();
  print(list);  // output: 'Empty List'
  list.append(1);
  list.append(2);
  list.append(3);
  list.append(4);
  print(list); // output : 1 --> 2 --> 3 --> 4
}

But with the second variation algorithm we have :

void main() {
  final list = LinkedList<int>();
  print(list);  // output: 'Empty List'
  list.append(1);
  list.append(2);
  list.append(3);
  list.append(4);
  print(list); // output : 1 --> 2 
}

Why is the output different for the second algorithm?

dart linked-list list algorithm
1 Answers

Let's discuss the second algorithm step by step using your example.

  1. list.append(1): Since the list is empty, a new head node is created.
  2. list.append(2): A new node is created (let's say N2).
    tail!.nextNode = Node(value: value); means that head.next points to N2.
    However, when you do tail = Node(value: value), tail now points to an entirely new node, whereas head.next still points to N2.
  3. list.append(3): Subsequent append calls will not add any new nodes to the original linked list, since the tail pointer is pointing to a arbitrary node which isn't connected to the original list.
user_93507200
Related