I'm reviewing data structures and came across something that I never realized when it comes to Linked Lists. This specific example is for Linked Lists, but the concept I think will be largely around properties that follow reference semantics within a struct (value semantics).

Here is the situation: I declare a new node, and say that this new node and head in the LinkedList share the same reference. Then, I change the value of head. I would assume that since the new node and head reference the same space in memory, they would both reflect the update. However, this is not the case. head shows the update` but the new node does not. Please see code below.

public struct LinkedList<Value> {
    public var head: Node<Value>?

    public init() {}
    /* 
    append, push, isEmpty, insert, pop functions
    */
}



public class Node<Value> {
    public var value: Value
    public var next: Node?

    public init(value: Value, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}

var list = LinkedList<Int>()
list.append(1)
list.append(2)
list.append(3)

let node = list.head
list.head = list.head?.next

print(list.head)  // prints 2 -> 3
print(node)       // prints 1 -> 2 -> 3

Since Node is a class, I would have thought that list.head and node would both reflect updates made to either. Why are the class semantics above behaving differently than below:

// Reference type example
class C { var data: Int = -1 }
var x = C()
var y = x                       // y now points to the same memory address as x
x.data = 42                     // changes the instance referred to by x (and y)
println("\(x.data), \(y.data)") // prints "42, 42"

CodePudding user response：

Because you setup LinkedList and Node is class. So when a variable assign to a class variable it points to the address in memory where that class variable is stored.

From this 2 line of your code you see that

let node = list.head
list.head = list.head?.next

First one is node = list.head means that node is pointed to the memory address where list.head is stored. Means that both node and list.head at this time both assign to same memory address.

Second one is list.head = list.head?.next means that list.head is pointed to the memory address where list.head?.next is stored. Means that both node and list.head at this time not assign to same memory address.

So the list.head change memory address to list.head?.next doesn't affect where node currently memory address.

Example: A -> B -> C ( which is list memory access from a LinkedList)

• At first, list.head is pointed to memory A

• Then, node is pointed to memory A

• Then, list.head is pointed to memory B which is list.head?.next.

• So node doesn't change at all still at memory A.