swift 中我的 LinkedList 中的删除函数中的错误

Question

我正在尝试实现一个通用的 linkedList API 就像 Java 在 swift.This 中可能已经以数百种方式完成，但我的问题不是如何做而是，关于删除索引为零的项目时我的部分逻辑有什么问题。我知道，有其他方法可以实现我想要的，我做到了，但我需要了解特定逻辑中的缺陷。请看

我现在有以下功能。

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

只有当我尝试从列表开头（索引=0）删除项目时，我的逻辑缺陷才出现在 remove(index:) 方法中。我的逻辑是如果列表中有超过 1 个项目 (list.size>0).

，则将头部的 next 节点设置为 head

以下是完整的实现-

import Foundation

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

class LinkedList<Item> {
    var head: Node<Item>?
    
    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)
    }
}

测试代码如-

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

输出：

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

谁能指出我的错误。

Answer 1

列表的头部成为下一项，如果有的话。如果下一项为 nil，则列表的头部也为 nil，如下所示：

    if index == 0 { //here is the bug
        head = head?.next
        return
    }

此代码：

if let next = last.next{
    last = next
}else{
    head = nil
}

在第一个分支中，你return没有改变“head”，所以列表的头部保持不变。

假设 head 在地址 100 列表中的第二项位于地址 200

let list = LinkedList<Int>()
list's head -> 100

在索引 0 处的删除中，我们将 last 设置为 head，secondLast 也设置为 head

last -> 100[ |next -> 200]
secondLast -> 100[ |next -> 200]

然后我们说

if let next = last.next { last = next } return

现在最后指向200：

last -> 200[ |next -> 300]

但是列表的头部没有改变

list's head -> 100[ |next -> 200]
secondLast -> 100[ |next -> 200]

最后一个超出范围，当我们return时，列表结构（在堆中）没有发生任何变化。

在工作分支中（索引 > 0）：

    while count < index{
        guard let next = last.next else{
            return
        }
        secondLast = last
        last = next
        count = count + 1
    }
    secondLast.next = last.next

我们遍历操作 secondLast 和 last 的循环，然后在某个点我们到达行

secondLast.next = ...

然后我们实际分配给对象，我们改变堆中的对象，它是下一个指针，我们从这样的东西开始：

secondLast -> 100[ |next -> 200]

secondLast -> 100[ |next -> 300]

所以现在列表本身已经改变，在堆中，地址处的对象例如100 有一个指向某个对象的下一个指针，例如地址 300.

Answer 2

首先，我非常感谢@Shadowrun 投入的时间和精力。但是，当我迭代列表并在 list 之间删除代码时，解释仍然缺乏代码工作的原因。原因是List本身只有一个指针head，指向内存中的一个地址。当然，last 节点指向相同的地址，但是当我尝试在 last 的帮助下更新 head（索引 = 0）时，last 指向一个不同的地址，这意味着它一旦离开范围就会偏离头部。虽然 list 不知道发生了变化并且列表仍然持有与以前相同的指向地址的指针。

现在，当我从 head(index>0) 迭代时，最后一个与 head 相同，并且每次迭代 last 都会向前移动到 next 节点。我随时更改任何节点的下一个指针，下一个指针成功更新为该节点。这里的起始节点与上一个节点相同，并且 head 指向相同的地址。因此，对于列表的迭代，无论我是从 head 还是从 last 开始，链式链接都是相同的。这里的 head 和 last 一开始是一样的。但是对于 index = 0，作为 list 的 head，本身需要改变，使 last 指向不同的节点是行不通的，因为 list 知道 head 而 head 没有更新。所以，真正的原因是列表不知道节点是如何与一个例外相互关联的，那就是头部。

这与分配对象或其他任何事情无关。这是关于仅指向一个节点的列表，即 head.

swift 中我的 LinkedList 中的删除函数中的错误

bug in the remove function in my LinkedList in swift

reference

data-structures

singly-linked-list

swift