链接列表的自定义索引类型
Swift 5.0，Xcode 10.3
我最近在swift中实现了一个双重链表类型。当我开始做它的时候，我的目标是给用户提供与使用Array相同的易用性，但是与双链表相关联的算法复杂性。考虑到这一目标，我决定了实现这一目标的主要方法之一是让Node键入一个实现细节；让用户看不见，也不去想。我还决定，必须将LinkedList作为struct实现，以便提供适当的不可变性/可变性支持。
不过，要确定LinkedList类型及其私有的Node类型的语义非常困难。这主要是由于LinkedList是一个struct和Node是一个class。因此，每当复制了一个LinkedList值时，改变复制的链接列表也会改变初始变量。例如，在所描述的情况下，会发生这种情况：

let list1 = LinkedList([1, 2, 3])
var list2 = list1
list2.append(4) // Mutates both list1 and list2
print(list1)
// Prints "[1, 2, 3, 4]"

let list1 = LinkedList([1, 2, 3])
var list2 = list1
list2.append(4) // Nodes are copied 
print(list1)
// Prints "[1, 2, 3]"
print(list2)
// Prints "[1, 2, 3, 4]"

extension LinkedList: Collection {

    //... 

    public struct Index: Comparable {
        fileprivate weak var node: Node?
        fileprivate var offset: Int

        fileprivate init(node: Node?, offset: Int) {
            self.node = node
            self.offset = offset
        }

        public static func ==(lhs: Index, rhs: Index) -> Bool {
            return lhs.offset == rhs.offset
        }

        public static func <(lhs: Index, rhs: Index) -> Bool {
            return lhs.offset < rhs.offset
        }
    }
}

public struct LinkedList<Element> {

    private var headNode: Node?
    private var tailNode: Node?
    public private(set) var count: Int = 0

    public init() { }

}

//MARK: - LinkedList Node
extension LinkedList {

    fileprivate class Node {
        public var value: Element
        public var next: Node?
        public weak var previous: Node?

        public init(value: Element) {
            self.value = value
        }
    }

}

//MARK: - Initializers
public extension LinkedList {

    private init(_ nodeChain: NodeChain?) {
        guard let chain = nodeChain else {
            return
        }
        headNode = chain.head
        tailNode = chain.tail
        count = chain.count
    }

    init<S>(_ sequence: S) where S: Sequence, S.Element == Element {
        if let linkedList = sequence as? LinkedList<Element> {
            self = linkedList
        } else {
            self = LinkedList(NodeChain(of: sequence))
        }
    }

}

//MARK: NodeChain
extension LinkedList {
    private struct NodeChain {
        let head: Node!
        let tail: Node!
        private(set) var count: Int

        // Creates a chain of nodes from a sequence. Returns `nil` if the sequence is empty.
        init?<S>(of sequence: S) where S: Sequence, S.Element == Element {
            var iterator = sequence.makeIterator()

            guard let firstValue = iterator.next() else {
                return nil
            }

            var currentNode = Node(value: firstValue)
            head = currentNode
            count = 1

            while let nextElement = iterator.next() {
                let nextNode = Node(value: nextElement)
                currentNode.next = nextNode
                nextNode.previous = currentNode
                currentNode = nextNode
                count += 1
            }
            tail = currentNode
        }

    }
}

//MARK: - Copy Nodes
extension LinkedList {

    private mutating func copyNodes(settingNodeAt index: Index, to value: Element) {

        var currentIndex = startIndex
        var currentNode = Node(value: currentIndex == index ? value : currentIndex.node!.value)
        let newHeadNode = currentNode
        currentIndex = self.index(after: currentIndex)

        while currentIndex < endIndex {
            let nextNode = Node(value: currentIndex == index ? value : currentIndex.node!.value)
            currentNode.next = nextNode
            nextNode.previous = currentNode
            currentNode = nextNode
            currentIndex = self.index(after: currentIndex)
        }
        headNode = newHeadNode
        tailNode = currentNode
    }

    @discardableResult
    private mutating func copyNodes(removing range: Range<Index>) -> Range<Index> {

        var currentIndex = startIndex

        while range.contains(currentIndex) {
            currentIndex = index(after: currentIndex)
        }

        guard let headValue = currentIndex.node?.value else {
            self = LinkedList()
            return endIndex..<endIndex
        }

        var currentNode = Node(value: headValue)
        let newHeadNode = currentNode
        var newCount = 1

        var removedRange: Range<Index> = Index(node: currentNode, offset: 0)..<Index(node: currentNode, offset: 0)
        currentIndex = index(after: currentIndex)

        while currentIndex < endIndex {
            guard !range.contains(currentIndex) else {
                currentIndex = index(after: currentIndex)
                continue
            }

            let nextNode = Node(value: currentIndex.node!.value)
            if currentIndex == range.upperBound {
                removedRange = Index(node: nextNode, offset: newCount)..<Index(node: nextNode, offset: newCount)
            }
            currentNode.next = nextNode
            nextNode.previous = currentNode
            currentNode = nextNode
            newCount += 1
            currentIndex = index(after: currentIndex)

        }
        if currentIndex == range.upperBound {
            removedRange = Index(node: nil, offset: newCount)..<Index(node: nil, offset: newCount)
        }
        headNode = newHeadNode
        tailNode = currentNode
        count = newCount
        return removedRange
    }

}


//MARK: - Computed Properties
public extension LinkedList {
    var head: Element? {
        return headNode?.value
    }

    var tail: Element? {
        return tailNode?.value
    }
}

//MARK: - Sequence Conformance
extension LinkedList: Sequence {

    public typealias Element = Element

    public __consuming func makeIterator() -> Iterator {
        return Iterator(node: headNode)
    }

    public struct Iterator: IteratorProtocol {

        private var currentNode: Node?

        fileprivate init(node: Node?) {
            currentNode = node
        }

        public mutating func next() -> Element? {
            guard let node = currentNode else {
                return nil
            }
            currentNode = node.next
            return node.value
        }

    }
}

//MARK: - Collection Conformance
extension LinkedList: Collection {

    public var startIndex: Index {
        return Index(node: headNode, offset: 0)
    }

    public var endIndex: Index {
        return Index(node: nil, offset: count)
    }

    public var first: Element? {
        return head
    }

    public var isEmpty: Bool {
        return count == 0
    }

    public func index(after i: Index) -> Index {
        precondition(i.offset != endIndex.offset, "LinkedList index is out of bounds")
        return Index(node: i.node?.next, offset: i.offset + 1)
    }

    public struct Index: Comparable {
        fileprivate weak var node: Node?
        fileprivate var offset: Int

        fileprivate init(node: Node?, offset: Int) {
            self.node = node
            self.offset = offset
        }

        public static func ==(lhs: Index, rhs: Index) -> Bool {
            return lhs.offset == rhs.offset
        }

        public static func <(lhs: Index, rhs: Index) -> Bool {
            return lhs.offset < rhs.offset
        }
    }

}


//MARK: - MutableCollection Conformance
extension LinkedList: MutableCollection {

    public subscript(position: Index) -> Element {
        get {
            precondition(position.offset != endIndex.offset, "Index out of range")
            guard let node = position.node else {
                preconditionFailure("LinkedList index is invalid")
            }
            return node.value
        }
        set {
            precondition(position.offset != endIndex.offset, "Index out of range")

            // Copy-on-write semantics for nodes
            if !isKnownUniquelyReferenced(&headNode) {
                copyNodes(settingNodeAt: position, to: newValue)
            } else {
                position.node?.value = newValue
            }
        }
    }
}



//MARK: LinkedList Specific Operations
public extension LinkedList {

    mutating func prepend(_ newElement: Element) {
        replaceSubrange(startIndex..<startIndex, with: CollectionOfOne(newElement))
    }

    mutating func prepend<S>(contentsOf newElements: __owned S) where S: Sequence, S.Element == Element {
        replaceSubrange(startIndex..<startIndex, with: newElements)
    }

    @discardableResult
    mutating func popFirst() -> Element? {
        if isEmpty {
            return nil
        }
        return removeFirst()
    }

    @discardableResult
    mutating func popLast() -> Element? {
        guard isEmpty else {
            return nil
        }
        return removeLast()
    }
}

//MARK: - BidirectionalCollection Conformance
extension LinkedList: BidirectionalCollection {
    public var last: Element? {
        return tail
    }

    public func index(before i: Index) -> Index {
        precondition(i.offset != startIndex.offset, "LinkedList index is out of bounds")
        if i.offset == count {
            return Index(node: tailNode, offset: i.offset - 1)
        }
        return Index(node: i.node?.previous, offset: i.offset - 1)
    }

}

//MARK: - RangeReplaceableCollection Conformance
extension LinkedList: RangeReplaceableCollection {

    public mutating func append<S>(contentsOf newElements: __owned S) where S: Sequence, Element == S.Element {
        replaceSubrange(endIndex..<endIndex, with: newElements)
    }

    public mutating func replaceSubrange<S, R>(_ subrange: R, with newElements: __owned S) where S: Sequence, R: RangeExpression, Element == S.Element, Index == R.Bound {

        var range = subrange.relative(to: indices)

        precondition(range.lowerBound >= startIndex && range.upperBound <= endIndex, "Subrange bounds are out of range")

        // If range covers all elements and the new elements are a LinkedList then set references to it
        if range.lowerBound == startIndex, range.upperBound == endIndex, let linkedList = newElements as? LinkedList {
            self = linkedList
            return
        }

        var newElementsCount = 0

        // There are no new elements, so range indicates deletion
        guard let nodeChain = NodeChain(of: newElements) else {

            // If there is nothing in the removal range
            // This also covers the case that the linked list is empty because this is the only possible range
            guard range.lowerBound != range.upperBound else {
                return
            }

            // Deletion range spans all elements
            if range.lowerBound == startIndex && range.upperBound == endIndex {
                headNode = nil
                tailNode = nil
                count = 0
                return
            }

            // Copy-on-write semantics for nodes and remove elements in range
            guard isKnownUniquelyReferenced(&headNode) else {
                copyNodes(removing: range)
                return
            }

            // Update count after mutation to preserve startIndex and endIndex validity
            defer {
                count = count - (range.upperBound.offset - range.lowerBound.offset)
            }

            // Move head up if deletion starts at start index
            if range.lowerBound == startIndex {
                // Can force unwrap node since the upperBound is not the end index
                headNode = range.upperBound.node!
                headNode!.previous = nil

                // Move tail back if deletion ends at end index
            } else if range.upperBound == endIndex {
                // Can force unwrap since lowerBound index must have an associated element
                tailNode = range.lowerBound.node!.previous
                tailNode!.next = nil

                // Deletion range is in the middle of the linked list
            } else {
                // Can force unwrap all bound nodes since they both must have elements
                range.upperBound.node!.previous = range.lowerBound.node!.previous
                range.lowerBound.node!.previous!.next = range.upperBound.node!
            }

            return
        }

        // Obtain the count of the new elements from the node chain composed from them
        newElementsCount = nodeChain.count

        // Replace entire content of list with new elements
        if range.lowerBound == startIndex && range.upperBound == endIndex {
            headNode = nodeChain.head
            tailNode = nodeChain.tail
            count = nodeChain.count
            return
        }

        // Copy-on-write semantics for nodes before mutation
        if !isKnownUniquelyReferenced(&headNode) {
            range = copyNodes(removing: range)
        }

        // Update count after mutation to preserve startIndex and endIndex validity
        defer {
            count += nodeChain.count - (range.upperBound.offset - range.lowerBound.offset)
        }

        // Prepending new elements
        guard range.upperBound != startIndex else {
            headNode?.previous = nodeChain.tail
            nodeChain.tail.next = headNode
            headNode = nodeChain.head
            return
        }

        // Appending new elements
        guard range.lowerBound != endIndex else {
            tailNode?.next = nodeChain.head
            nodeChain.head.previous = tailNode
            tailNode = nodeChain.tail
            return
        }

        if range.lowerBound == startIndex {
            headNode = nodeChain.head
        }
        if range.upperBound == endIndex {
            tailNode = nodeChain.tail
        }

        range.lowerBound.node!.previous!.next = nodeChain.head
        range.upperBound.node!.previous = nodeChain.tail
    }

}

//MARK: - ExpressibleByArrayLiteral Conformance
extension LinkedList: ExpressibleByArrayLiteral {
    public typealias ArrayLiteralElement = Element

    public init(arrayLiteral elements: ArrayLiteralElement...) {
        self.init(elements)
    }
}

//MARK: - CustomStringConvertible Conformance
extension LinkedList: CustomStringConvertible {
    public var description: String {
        return "[" + lazy.map { "\($0)" }.joined(separator: ", ") + "]"
    }
}

let immutableList: LinkedList = [1, 2, 3, 4]
var mutableList: LinkedList = [5, 6, 7, 8]

let immutableIndex = immutableList.index(after: immutableList.startIndex)

mutableList[immutableIndex] = 0

print("Immutable List:", immutableList)
print("Mutable List:", mutableList)

// Prints:
//   Immutable List: [1, 0, 3, 4]
//   Mutable List: [5, 6, 7, 8]

var list: LinkedList = [1, 2, 3, 4]
let idx1 = list.index(list.startIndex, offsetBy: 2) // Index to node with value of 3 and offset of 2

list.remove(at: list.index(before: idx1))
print(list)
// Prints: "[1, 3, 4]"

let idx2 = list.index(before: list.endIndex) // Index to node with value of 4 and offset of 2
print(idx1 == idx2) 
// Prints: "true"

print(Array(list[idx1...idx2]))
// Prints: "[3]"

最佳答案

让我们先解决第二个问题：
此外，索引的偏移量在变异到其节点的父列表后失效，从而导致了荒谬的情况…
这是所有集合的期望值。从Collections开始：
由于操作发生变化，保存的索引可能会变得无效。
使用无效索引是未定义的行为，任何事情都可能发生：意外结果、致命错误…下面是一个简单的swift字符串示例：

var s = "a??bcd"
let i = s.firstIndex(of: "??")!
s.remove(at: s.startIndex) // invalidates `i`
s.remove(at: i)
print(s) // \360cd

mutableList[immutableIndex] = 0

关于swift - Swift中链接列表的自定义索引，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57532898/