Misunderstand singly Linked List

Abdelfatah Ashour 0
Viewed 34

I have misunderstood the implementation of a singly linked list, if the length in a linked list is 0, let the head and tail equal the new node there is no problem with me.

But when I try to add a new node I mutate it with this.tail.next = newNode and this.tail equal newNode.

The problem how this.head take new node?

enter image description here

enter image description here

singly-linked-list data-structures
1 Answers

how this.head take new node?

When the second node is added, this.head references the first node, and that is what it still should reference after the second node has been added. The addition happens by mutating the next member of the first node, so that it references the second node.

It may help to visualse this. After the first node has been inserted (let's say with value 1), we have this state with the instance of the SinglyLinkedList class and the first instance of the Node class:

 this
  ↓
┌────────────┐
│ tail: ─────────┐
│ head: ───────┐ │
│ length: 1  │ │ │
└────────────┘ │ │
               ▼ ▼
         ┌────────────┐
         │ value: 1   │
         │ next: null │
         └────────────┘

Now let's look at what happens when the second node (with value 2) is added. First newNode is assigned a new instance of Node that has received a value:

 this
  ↓
┌────────────┐
│ tail: ─────────┐
│ head: ───────┐ │
│ length: 1  │ │ │
└────────────┘ │ │
               ▼ ▼
         ┌────────────┐   ┌────────────┐
         │ value: 1   │   │ value: 2   │
         │ next: null │   │ next: null │
         └────────────┘   └────────────┘
                                ↑
                             newNode

Then the link is established with this.tail.next = newNode:

 this
  ↓
┌────────────┐
│ tail: ─────────┐
│ head: ───────┐ │
│ length: 1  │ │ │
└────────────┘ │ │
               ▼ ▼
         ┌────────────┐   ┌────────────┐
         │ value: 1   │   │ value: 2   │
         │ next: ────────│ next: null │
         └────────────┘   └────────────┘
                                ↑
                             newNode

Note how this builds a chain of references, such that now not only this.tail.next === newNode, but also this.head.next === newNode!

Just to finish up the scenario of insertion, we execute this.tail = newNode and this.length++ which results in this state:

 this
  ↓
┌────────────┐
│ tail: ────────────────────────┐
│ head: ───────┐                │
│ length: 2  │ │                │
└────────────┘ │                │
               ▼                ▼
         ┌────────────┐   ┌────────────┐
         │ value: 1   │   │ value: 2   │
         │ next: ────────│ next: null │
         └────────────┘   └────────────┘
                                ↑
                             newNode

I hope this clarifies it.

trincot0
Related