bug in the remove function in my LinkedList in swift

Question

I am trying to implement a generic linkedList API like in Java in swift.This has been done probably in hundreds of ways but my question is not on how to do it rather, on what is wrong with a part of my logic when removing an item whose index is zero. I know, there are alternate ways to achieve what I want and I did that but I need to understand the flaw in a particular logic. please have a look.

I have following functions for now.

var size : Int { get } //give the size of the list
func add(_ value: Item) //add items to the list
func removeAt(index: Int) // removes the item from the specified index
func print() //prints the list

My logic flaw is in the remove(index:) method only when I try to remove an item from the beginning of the list(index=0). My logic is to set the head's next node to be the head if there are more than 1 item in the list(list.size>0).

The following is the full implementation-

import Foundation

class Node{
    var value: Item
    var next: Node?
    
    init(value: Item) {
        self.value = value
        self.next = nil
    }
}

class LinkedList {
    var head: Node?
    
    public init(){
        self.head = nil
    }
    
    public init(_ value: Item){
        self.head = Node(value: value)
    }
    
    private func isEmpty()->Bool{
        if head == nil{
            return true
        }
        return false
    }
    
    var size : Int {
        guard var current = head else{
            return 0
        }
        var count = 1
        while current.next != nil {
            guard let next = current.next else {
                return count
            }
            count = count + 1
            current = next
        }
        return count
    }
    
    func add(_ value: Item){
        let node = Node(value: value)
        if isEmpty(){
            head = node
            return
        }
        guard let head = head else {
            return
        }
        var currentNode = head
        while currentNode.next != nil {
            guard let nextNode = currentNode.next else {
                break
            }
            currentNode = nextNode
        }
        currentNode.next = node
    }
    
    func removeAt(index: Int) {
        if isEmpty() || index >= self.size{
            return
        }
        guard var last = head, var secondLast = head else{
            return
        }
        // when index is zero and either the list has only one item or it has multiple items
        if index == 0{ //here is the bug
            if let next = last.next{
                last = next
            }else{
                head = nil
            }
            return
        }
        var count = 0
        while count < index{
            guard let next = last.next else{
                return
            }
            secondLast = last
            last = next
            count = count + 1
        }
        secondLast.next = last.next
    }
    
    func print(){
        guard var current = head else {
            return
        }
        if current.next == nil{ //if list contains only head
            Swift.print(current.value)
            return
        }
        while current.next != nil{
            Swift.print(current.value)
            guard let next = current.next else {
                return
            }
            current = next
        }
        Swift.print(current.value)
    }
}

Testing the code like -

let list = LinkedList()
for i in 0...5{
   list.add(i)
}
list.print()
let index = 0
list.removeAt(index: index)
print("After removing..")
list.print()

Output:

1
2
3
4
5
After removing..
1
2
3
4
5

Can anyone please points out my fault.

Natasha · Accepted Answer

Firstly, I really appreciate the time and effort @Shadowrun put into. However, the explanation still lack the reason as of why the code works when I am iterating the list and removing in between the list. The reason is List itself only holds one pointer, head which is referring to an address in memory. Sure the last node points to the same address but when I try to update update the head (index = 0) with the help of last, last is points to a different address which means it deviates from head as soon as it leaves the scope. While list has no clue that there was a change and list still holds the same pointer to address as of before.

Now when I am iterating from head(index>0), the last is same as head and with each iteration the last moves forward to the next node. I change the next pointer of any node at anytime, the next pointer gets updated for that node successfully. Here the starting node is same as head as last and head is pointing to the same address. So, for iteration over the list, it doesn't matter whether I start with head or last, the chain linking is same. Here head and last is same at the beginning. But for index = 0, as list's head, itself needs to be changed, making last pointing to a different node won't work because list knows head and the head is not updated. So, the real reason is the list has no clue of how the node's are inter-related with one exception and that is the head.

It's not about assigning object or anything else. It's about list pointing to only one node and that is head.

bug in the remove function in my LinkedList in swift

Answers (2)

Related Questions