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 = 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? 😕

>Solution :

The thing is that tail.next = 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 = new Node 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.