LinkedList tail assigned to head at the init block, why can't we append the head?

Alon Shlider 0
Viewed 34

I am having a hard time grasping the append() method when trying to learn about basic LinkedList implementation:

class LinkedList(value : Int) {

    private var head : Node = Node()
    private var tail : Node
    private var length : Int = 0

    init {
        head.value = value
        tail = head
        length++
    }


    fun append(value: Int): LinkedList {
        val newNode = Node(value)
        tail.next = newNode
        tail = newNode
        length++
        return this
    }
    
    override fun toString(): String {
        return "LinkedList {\nhead: $head,\ntail: $tail,\nlength: $length }"
    }

    class Node(var value : Int = -1, var next : Node? = null) {

        override fun toString(): String {
            return "Node { value: $value next: $next }"
        }
    }
}

As you can see in my implementation, when using the append() method we assign tail.next to the newNode that we created. The thing is that tail.next is head.next, since at the init block we initialized tail = head, therefore I can't understand why in the append() method we can't do head.next = newNode instead of tail.next = newNode.

Technically I know what would happen - we would not advance any further than one time and just rewrite the same node over and over, but I am finding it really hard to understand why since at the init { } block we declared tail to point to the same address in memory that head is, therefore anyway what we are doing is advancing the head.next over and over, so why not use it in the first place?

linked-list kotlin
2 Answers

The thing is that tail.next is head.next, since at the init block we initialized tail = head, therefore I can't understand why in the append() method we can't do head.next = newNode instead of tail.next = newNode.

Your proposal would work the first time it executes, but as the next statement moves tail to reference the new node by doing tail = newNode, the equivalence of head and tail no longer holds. And so if append() is called again, head.next should no longer be touched.

It may help to visualise this. Let's say we start in a scenario where we have a list myLinkedList, and it has already one node:

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

As you correctly indicate, head == tail at this stage. So now, we call append(2). The first action is calling the Node constructor and assigning that reference to the local variable newNode:

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

Then tail.next = newNode is executed, which indeed has the same result as doing head.next = newNode:

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

But then we do tail = newNode, which makes tail different from head:

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

The length is also updated (above). It is clear that on a next execution of append(), we want the next member of the second node to be updated, not of the first node, and so it must be tail.next that gets assigned the new node's reference. Let's say we call append(3), then after we have created a new node and assigned it to newNode we get this:

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

If now we would do head.next = newNode we would not get the desired effect:

 myLinkedList
 ↓
┌────────────┐ 
│ tail: ───────────────────────┐
│ head: ────────┐              │
│ length: 2  │  │              │
└────────────┘  │              │                     newNode
                ▼              ▼                        ↓
           ┌────────────┐    ┌────────────┐    ┌────────────┐
           │ value: 1   │    │ value: 2   │    │ value: 3   │
           │ next: ────────┐ │ next: null │ ┌─│ next: null │
           └────────────┘  │ └────────────┘ │  └────────────┘
                           └────────────────┘ (Wrong!)

This is wrong. That next reference in the first node should not have changed. Instead, we want the tail node to get its next reference updated from null to newNode:

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

And now finally, the tail reference will be updated to point to the new node that is now really the tail. And the length updates as well:

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

We can now see that head.next should not be changed by append ever again. It should only happen when the second node is added. The common principle is that the last node in the list should get its next member updated. In one particular case that last node happens to be head, but that is just coincidence. We can better rely on updating tail.next, as that is guaranteed to be an update in the tail node, where null will be replaced with a reference to the new node.

I hope this clarifies it.

trincot0

tail is the same as head only initially. After a call of append, tail is set to the new node, here,

tail = newNode

which is not head anymore.

If you replace tail.next = newNode with head.next = newNode, the first time you call append, it will work as expected, because head and tail are the same. But after that, tail points to the newly inserted node, and head doesn't change.

[ node ] -> [ node ]
  ^^^^        ^^^^
  head        tail

A subsequent append would change head.next to the new node, so you would end up with head pointing to a node, which is linked to another node, and tail pointing to a third node that is not linked to the former two.

     ----------------------|
    |                      V
[ node ]    [ node ]   [ node ]
  ^^^^        ^^^^       
  head        tail

That's not what you want, is it?

You can, however, do head.next = newNode, and also do head = newNode. That is equivalent to renaming tail to head and head to tail at the same time.

Sweeper0
Related