Confused about the reference type assignment-CodePudding

Following is a portion of a linked list implementation and I'm confused about the semantics:

class Node<T> {
    var value: T
    var next: Node?
    weak var previous: Node?
    
    init(value: T) {
        self.value = value
    }
}

struct LinkedList<T> {
    var head: Node<T>?
    var tail: Node<T>?
    
    init() { }
    
    // what this method actually does is unimportant, but it creates a linked list from a sequence
    func createChain<S>(of sequence: S) -> (head: Node<T>, tail: Node<T>)? where S: Sequence, S.Element == T {
        var iterator = sequence.makeIterator()
        guard let firstValue = iterator.next() else {
            return nil
        }
        var head: Node<T>
        var tail: Node<T>
        
        var currentNode = Node(value: firstValue)
        head = currentNode
        
        while let nextValue = iterator.next() {
            let newNode = Node(value: nextValue)
            currentNode.next = newNode
            newNode.previous = currentNode
            currentNode = newNode // ?
        }
        
        tail = currentNode
        return (head: head, tail: tail)
    }
}

Let's say if I were to create a linked list using above code:

let linkedList = LinkedList<Int>()
let sequence = [0, 1, 2]
let chain = linkedList.createChain(of: sequence)

On the first cycle of the while loop, the snapshot would be as follows:

while let nextValue = iterator.next() {
    let newNode = Node(value: nextValue) // newNode: previous = nil, next = nil, value = 1
    currentNode.next = newNode // currentNode: previous = nil, next = newNode, value = 0
    newNode.previous = currentNode // newNode: previous = currentNode, next = nil, value = 1
    currentNode = newNode // ?
}

When the final line is executed, I understand superficially that the new node has to replace the current node continuously to cycle through all the elements of the sequence, but I'm not exactly sure what's happening when currentNode sets newNode. It doesn't make sense that newNode overwrites currentNode since currentNode's next has just been assigned with newNode and newNode's next is nil.

If newNode is not overwriting currentNode, how does the content of newNode not affect currentNode in currentNode = newNode?

CodePudding user response：

Classes are reference types. This means that currentNode holds a reference to an instance of that Node. When you assign a new instance to currentNode, you are changing the object that is referenced. As long as some other variable or property holds a reference to the previous instance, it will remain in memory.

This is why it is important that the first Node referred to be currentNode is assigned to head; If head didn't hold the reference then that Node would be released when a new Node was assigned to currentNode. References to subsequent Nodes are held by the previous and next properties, keeping them in memory too.

To illustrate I will show the sequence using fictitious memory addresses denoted by *0, *1 etc:

Before the while loop:

currentNode = Node*0(0,nil,nil)
head = Node*0(0,nil,nil)

Note that currentNode and head refer to the same memory addresses.

First time through the while loop:

currentNode = Node*0(0,nil,nil)
newNode = Node*1(1,nil,nil)
currentNode = Node*0(0,Node*1,nil)
newNode = Node*1(0,nil,Node*0)
currentNode = Node*1(nil,Node*0)

Note that currentNode now references Node*1. head is still referring to Node*0 as is the previous value of Node*1

Next time through the while loop:

currentNode = Node*1(1,nil,Node*0)
newNode = Node*2(2,nil,nil)
currentNode = Node*1(0,Node*2,nil)
newNode = Node*2(0,nil,Node*1)
currentNode = Node*2(nil,Node*1)

And so on

Finally, the implementation of createChain is a little odd; It returns a tuple of (head,tail) and it operates on an empty LinkedList.

You can implement it as a static function that returns a LinkedList -

struct LinkedList<T> {
    var head: Node<T>
    var tail: Node<T>
    
    // what this method actually does is unimportant, but it creates a linked list from a sequence
    static func createChain<S>(of sequence: S) -> LinkedList<S.Element>? where S: Sequence, S.Element == T {
        var iterator = sequence.makeIterator()
        guard let firstValue = iterator.next() else {
            return nil
        }
        var head: Node<S.Element>
        var tail: Node<S.Element>
        
        var currentNode = Node(value: firstValue)
        head = currentNode
        
        while let nextValue = iterator.next() {
            let newNode = Node(value: nextValue)
            currentNode.next = newNode
            newNode.previous = currentNode
            currentNode = newNode // ?
        }
        
        tail = currentNode
        return LinkedList(head: head, tail: tail)
    }
}

Then you can create your linked list with

let sequence = [0, 1, 2]

let list = LinkedList.createChain(of: sequence)