CODEWITHSUNDEEP
swiftlinked-list
syedfa
syedfa

Reputation: 2819

Need clarification about Linked Lists using Swift

I am looking at some code implementing a LinkedList using Swift, and I need someone to clarify for me a couple of things. First off, here is the code below for my LinkedList class, and my function to remove a Node from the list:

public class Node<T> {

   var value:T
   var next: Node?

}

public class LinkedList<T:Equatable> {

    private var head = Node<T>()

    func remove(at index: Int) {

        if ((index < 0 || (index > (self.count - 1)) || (head.value == nil)) {
            print("link does not exist.")
            return
        }

        var current: Node? = head
        var previous: Node<T>?
        var listIndex:Int = 0

        if index == 0 {
           current = current?.next
           head = current!
           return
        }

        while current != nil {
           if listIndex == index {
              previous!.next = current?.next
              current = nil
              break
           }

           previous = current
           current = current?.next
           listIndex += 1
        }
    }
}

When it comes to removing an object from the list, in the following code block:

        if index == 0 {
           current = current?.next
           head = current!
           return
        }

My question related to the above code block is, I realize that I move the current pointer down one node in the list, and then change the reference of the head pointer to point to the node that current is now pointing to, however, what happens to the node that originally was pointing to current.next? There are no references to it, but IT still has a reference to the second node in the list, correct? How is this node removed completely if it still has a reference to the next node in the list? I have the same question for the following block later on, when the node is found in the middle of the list:

   if listIndex == index {
      previous!.next = current?.next
      current = nil
      break
   }

Please note: I am not in school and this is not homework. I'm studying algorithms on my own to review the concepts I learned originally in Java, and apply them to Swift.

Upvotes: 1

Views: 265

Answers (1)

tom
tom

Reputation: 22989

You correct that after the index == 0 block executes, there will be no references to the original head. This means that for the rest of the program you cannot do anything with that node. It is desirable that the memory allocated for the node should be reclaimed so it can be used for other objects (otherwise you'll have a completely useless node that is wasting memory).

Swift uses automatic reference counting, so it detects when there a no references to an object and reclaims the memory. The memory will be reclaimed without you having to do anything special.

How is this node removed completely if it still has a reference to the next node in the list?

The fact that the original head has a reference to another node does not prevent it from being reclaimed by the system. The program can't query which objects reference that other node, so it makes no difference to the rest of the program if the original head is reclaimed or not (other than the extra memory that becomes available).

Upvotes: 1

Related Questions