面试题：Swift中如何自定义一个链表数据结构并进行简单优化

Question

请用Swift代码实现一个链表数据结构，包含节点的创建、插入和删除操作。同时，思考在频繁插入和删除操作场景下，如何对这个链表结构进行简单的优化，以提高性能，并阐述优化思路。

Answer 1

// 定义链表节点
class ListNode {
    var value: Int
    var next: ListNode?
    init(_ value: Int) {
        self.value = value
    }
}

// 定义链表
class LinkedList {
    var head: ListNode?
    
    // 创建节点并插入到链表头部
    func insert(_ value: Int) {
        let newNode = ListNode(value)
        newNode.next = head
        head = newNode
    }
    
    // 删除指定值的节点
    func delete(_ value: Int) {
        var current = head
        var previous: ListNode?
        while current != nil {
            if current!.value == value {
                if previous == nil {
                    head = current?.next
                } else {
                    previous?.next = current?.next
                }
                return
            }
            previous = current
            current = current?.next
        }
    }
}

优化思路

1. 双向链表优化：在频繁插入和删除操作场景下，单向链表在删除节点时，需要遍历找到前一个节点，时间复杂度为O(n)。而双向链表可以在找到目标节点后，直接通过前驱指针修改前一个节点的指针，时间复杂度降为O(1)。
2. 使用虚拟头节点：虚拟头节点可以简化链表插入和删除操作的边界条件处理。在插入或删除节点时，不需要额外处理头节点为空的情况，使得代码逻辑更简洁，从而提高代码的可读性和维护性，间接提升性能。