以节点为结构的 swift 中的 LinkedList

Question

谁能告诉我如何快速创建一个以节点为结构、以链表为类的链表。

我试图创建一个引用自身的节点 Node 并遇到错误“值类型‘节点’不能有一个引用自身的存储属性”

为了解决这个问题，我又创建了一个 Next 类，现在我无法继续。

Answer 1

您不能将节点作为“结构”，因为 Swift 将结构和枚举视为值类型，将类视为引用类型。

当您创建 LinkedList 类时，您很可能会创建对节点结构的引用。现在 struct 是一种值类型，为值类型捕获 self 是危险的做法并且不鼓励。

因此，我建议您将 Node 创建为 Class 并利用 Swift 中的各种访问说明符来实现您想要的抽象。

有关在值类型中捕获 self 的更多详细信息，您可以参考https://github.com/Wolox/ios-style-guide/blob/master/rules/avoid-struct-closure-self.md。

Answer 2

细节

• Xcode 11.3.1、斯威夫特 5.1

基础接口

可节点化协议

import Foundation

protocol Nodeable: class {
    associatedtype Value
    var value: Value { get set }
    var next: Self? { get set }
    init(value: Value, next: Self?)
}

// MARK: Extensions

extension Nodeable where Self.Value: Equatable {
    static func == (lhs: Self, rhs: Self) -> Bool { lhs.value == rhs.value }
}

extension Nodeable where Self: AnyObject {
    var retainCount: Int { CFGetRetainCount(self as CFTypeRef) }
}

extension Nodeable where Self: CustomStringConvertible {
    var description: String { return "{ value: \(value), next: \(next == nil ? "nill" : "exist") }" }
}

链表协议

import Foundation

protocol LinkedListable where Node.Value == Value {
    associatedtype Node: Nodeable
    associatedtype Value
    var firstNode: Node? { get set }
    var lastNode: Node? { get set }
    init()
}

extension LinkedListable {
    var firstValue: Value? { return firstNode?.value }
    var lastValue: Value? { return lastNode?.value }
    var isEmpty: Bool { return firstNode == nil }
}

// MARK: Initializers

extension LinkedListable {
    init(_ array: [Value]) {
        self.init()
        array.forEach { append(newLast: $0) }
    }

    init(copyValuesFrom linkedList: Self) {
        self.init()
        if linkedList.isEmpty { return }
        linkedList.forEachNode { append(newLast: $0.value) }
    }

    init(copyReferencesFrom linkedList: Self) {
        self.init()
        firstNode = linkedList.firstNode
        lastNode = linkedList.lastNode
    }
}

// MARK: Iteration

extension LinkedListable {

    func node(at index: Int) -> Node? {
        if isEmpty { return nil }
        var currentIndex = 0
        var resultNode: Node?
        forEachWhile {
            if index == currentIndex { resultNode = $0; return false }
            currentIndex += 1
            return true
        }
        return resultNode
    }

    func forEachWhile(closure: (Node) -> (Bool)) {
        var currentNode = self.firstNode
        while currentNode != nil {
            guard closure(currentNode!) else { return }
            currentNode = currentNode?.next
        }
    }

    func forEachNode(closure: (Node) -> ()) {
        forEachWhile { closure($0); return true }
    }
}

// MARK: Add/Get values

extension LinkedListable {
    func value(at index: Int) -> Value? { node(at: index)?.value }

    // MARK: Add new node to the end of list

    mutating func append(newLast value: Value) {
        let newNode = Node(value: value, next: nil)
        if firstNode == nil {
            firstNode = newNode
            lastNode = firstNode
        } else {
            lastNode?.next = newNode
            lastNode = lastNode?.next
        }
    }
}

LinkedListable 协议扩展

// MARK: CustomStringConvertible

extension LinkedListable where Self: CustomStringConvertible {
    var description: String {
        var values = [String]()
        forEachNode { values.append("\($0.value)") }
        return values.joined(separator: ", ")
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: ExpressibleByArrayLiteral

extension LinkedListable where Self: ExpressibleByArrayLiteral, ArrayLiteralElement == Value {
    init(arrayLiteral elements: Self.ArrayLiteralElement...) { self.init(elements) }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: Sequence

extension LinkedListable where Self: Sequence {
    typealias Iterator = LinkedListableIterator<Node>
    func makeIterator() -> LinkedListableIterator<Node> { return .init(firstNode) }
}

struct LinkedListableIterator<Node>: IteratorProtocol where Node: Nodeable {
    private var currentNode: Node?
    init(_ firstNode: Node?) { self.currentNode = firstNode }
    mutating func next() -> Node.Value? {
        let node = currentNode
        currentNode = currentNode?.next
        return node?.value
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: Collection

extension LinkedListable where Self: Collection, Self.Index == Int, Self.Element == Value {
    var startIndex: Index { 0 }
    var endIndex: Index {
        guard !isEmpty else { return 0 }
        var currentIndex = 0
        forEachNode { _ in currentIndex += 1 }
        return currentIndex
    }

    func index(after i: Index) -> Index { i+1 }
    subscript(position: Index) -> Element { node(at: position)!.value }
    var isEmpty: Bool { return firstNode == nil }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


extension LinkedListable where Self: MutableCollection, Self.Index == Int, Self.Element == Value {

    subscript(position: Self.Index) -> Self.Element {
        get { return node(at: position)!.value }
        set(newValue) { node(at: position)!.value = newValue }
    }
}

用法

Node类的实现

import Foundation

final class LinkedListNode<Value>: Nodeable {
    var value: Value
    var next: LinkedListNode?
    init(value: Value, next: LinkedListNode?) {
        self.value = value
        self.next = next
    }
}

extension LinkedListNode: Equatable, CustomStringConvertible where Value: Equatable {}

List类的实现（选项 1）

class BaseLinkedList<Value>: LinkedListable where Value: Equatable {
    typealias Node = LinkedListNode<Value>
    var firstNode: LinkedListNode<Value>?
    weak var lastNode: LinkedListNode<Value>?
    required init() { }
}

使用List类进行操作（选项 1）

var linkedList = BaseLinkedList(["one", "two", "three"])
linkedList = BaseLinkedList(copyReferencesFrom: linkedList)
linkedList = BaseLinkedList(copyValuesFrom: linkedList)

var node = linkedList.firstNode!
print("node value: \(node.value) \(String(describing: node.next))")

node = linkedList.lastNode!
print("node value: \(node.value) \(String(describing: node.next))")

print("isEmpty: \(linkedList.isEmpty)")

linkedList.append(newLast: "four")

linkedList.forEachNode { print($0.value) }

linkedList.forEachNode { print($0.value) }

print("node at index 3: \(String(describing: linkedList.node(at: 3)))")
print("value at index 5: \(String(describing: linkedList.value(at: 4)))")

List类的实现（选项 2）

class LinkedList<Value>: BaseLinkedList<Value> where Value: Equatable {}
extension LinkedList: CustomStringConvertible, ExpressibleByArrayLiteral, Sequence, Collection, MutableCollection {}

使用List类进行操作（选项 2）

var linkedList = LinkedList(arrayLiteral: "one", "two", "three")

print(linkedList)
print(linkedList.map { $0 + "!" })
print(linkedList.reduce("", { "\($0)_\($1)" }))
linkedList[2] = "five"
print(linkedList[2])
print(linkedList.count)

一些单元测试

import XCTest

// MARK: Test basic List functionality

class TestBasicList: XCTestCase {
    typealias LinkedList = BaseLinkedList<Int>
    // typealias Value = Int

    private var linkedList: LinkedList!
    private var possibleValues: [LinkedList.Value] { [1, 2, 3, 4] }

    override func setUp() { linkedList = LinkedList() }

    func testInitListFromArray() {
        TestBasicList.assertCollectionsContainsSameValues(linkedList: LinkedList(possibleValues), array: possibleValues)
    }

    func testInitListByCopyingValuesFromAnotherList() {
        linkedList = .init(possibleValues)
        let copiedLinkedList = LinkedList(copyValuesFrom: linkedList)
        assertCollections(linkedList1: linkedList, linkedList2: copiedLinkedList, containEqualValues: true)
        assertCollections(linkedList1: linkedList, linkedList2: copiedLinkedList, containsSameReferencesToNodes: false)
    }

    func testInitListByCopyingElementsReferencesFromAnotherList() {
        linkedList = .init(possibleValues)
        let copiedLinkedList = LinkedList(copyReferencesFrom: linkedList)
        assertCollections(linkedList1: linkedList, linkedList2: copiedLinkedList, containEqualValues: true)
        assertCollections(linkedList1: linkedList, linkedList2: copiedLinkedList, containsSameReferencesToNodes: true)
    }

    func testPushFunctionality() {
        possibleValues.forEach { linkedList.append(newLast: $0) }
        TestBasicList.assertCollectionsContainsSameValues(linkedList: linkedList, array: possibleValues)
    }

    func testRandomAccess() {
        linkedList = .init(possibleValues)
        (0 ..< possibleValues.count).forEach {
            XCTAssertEqual(possibleValues[$0], linkedList.node(at: $0)?.value)
        }
    }

    private func assertCollections(linkedList1: LinkedList, linkedList2: LinkedList, containEqualValues: Bool) {
        var values1 = [LinkedList.Value]()
        linkedList1.forEachNode { values1.append($0.value) }

        var values2 = [LinkedList.Value]()
        linkedList2.forEachNode { values2.append($0.value) }

        if containEqualValues {
            XCTAssertEqual(values1, values2)
        } else {
            XCTAssertNotEqual(values1, values2)
        }
    }

    private func assertCollections(linkedList1: LinkedList, linkedList2: LinkedList, containsSameReferencesToNodes: Bool) {
        var values1 = [LinkedList.Node]()
        linkedList1.forEachNode { values1.append($0) }

        var values2 = [LinkedList.Node]()
        linkedList2.forEachNode { values2.append($0) }

        var areSame: Bool!
        for i in 0 ..< values1.count {
            areSame = values1[i] === values2[i]
            if containsSameReferencesToNodes {
                XCTAssertTrue(areSame)
            } else {
                XCTAssertFalse(areSame)
            }
        }
    }
}

extension TestBasicList {
    class func assertCollectionsContainsSameValues<List: LinkedListable>(linkedList: List, array: [List.Value]) where List.Value: Equatable  {
        var values = [List.Value]()
        linkedList.forEachNode { values.append($0.value) }
        XCTAssertEqual(values, array)
    }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: Sequence

class LinkedListSequence<Value>: BaseLinkedList<Value>, Sequence where Value: Equatable {}

protocol LinkedListSequenceTestable {
    typealias Value = Int
    typealias LinkedList = LinkedListSequence<Value>
    var linkedList: LinkedList { get set }
    var possibleValues: [Value] { get}
}

extension LinkedListSequenceTestable {

    func _testFilter() {
        XCTAssertEqual(linkedList.filter ({ $0 % 2 == 0 }),
                       possibleValues.filter({ $0 % 2 == 0 }))
    }

    func _testMap() {
        guard let num = possibleValues.first else { return }
        XCTAssertEqual(linkedList.map({ $0 + num}), possibleValues.map({ $0 + num}))
    }

    func _testCompactMap() {
        let array1 = linkedList.compactMap { value -> String? in
            if value % 2 != 0 { return "\(value)" }
            return nil
        }

        let array2 = possibleValues.compactMap { value -> String? in
            if value % 2 != 0 { return "\(value)" }
            return nil
        }
        XCTAssertEqual(array1, array2)
    }

    func _testReduce() {
        let result1 = linkedList.reduce(LinkedList.Element()) { $0 + $1 }
        let result2 = possibleValues.reduce(LinkedList.Element()) { $0 + $1 }
        XCTAssertEqual(result1, result2)
    }

    func _testForEach() {
        var values1 = [LinkedList.Value]()
        linkedList.forEach { values1.append($0) }

        var values2 = [LinkedList.Value]()
        possibleValues.forEach { values2.append($0) }

        XCTAssertEqual(values1, values2)
    }
}

class TestLinkedListSequence_nonEmpty: XCTestCase, LinkedListSequenceTestable {

    var linkedList = LinkedList()
    var possibleValues: [Value] { [1, 2, 3, 4] }

    override func setUp() { linkedList = LinkedList(possibleValues) }

    func testFilter() { _testFilter() }
    func testMap() { _testMap() }
    func testCompactMap() { _testCompactMap() }
    func testReduce() { _testReduce() }
    func testForEach() { _testForEach() }
}

class TestLinkedListSequence_oneElement: TestLinkedListSequence_nonEmpty {
    override var possibleValues: [Value] { [1] }
}

class TestLinkedListSequence_empty: TestLinkedListSequence_nonEmpty {
    override var possibleValues: [Value] { [] }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: Collection

class LinkedListCollection<Value>: BaseLinkedList<Value>, Sequence, Collection where Value: Equatable {}

protocol LinkedListCollectionTestable {
    associatedtype Value: Equatable
    typealias LinkedList = LinkedListCollection<Value>
    var linkedList: LinkedList { get set }
    var possibleValues: [Value] { get}
}

extension LinkedListCollectionTestable {

    func _testCount() {
        XCTAssertEqual(linkedList.count, possibleValues.count)
    }

    func _testIsEmpty() {
        XCTAssertEqual(linkedList.isEmpty, possibleValues.isEmpty)
        XCTAssertEqual(LinkedList().isEmpty, [].isEmpty)
    }

    func _testIndexes() {
        for i in 0 ..< linkedList.count {
            XCTAssertEqual(linkedList.index(after: i), possibleValues.index(after: i))
        }
    }
}
class TestLinkedListCollection_nonEmpty: XCTestCase, LinkedListCollectionTestable {
    typealias LinkedList = LinkedListCollection<Int>
    var linkedList = LinkedList()
    var possibleValues: [LinkedList.Value] { [1, 2, 3, 4] }
    override func setUp() { linkedList = LinkedList(possibleValues) }

    func testCount() { _testCount() }
    func testIsEmpty() { _testIsEmpty() }
    func testIndexes() { _testIndexes() }
}

class TestLinkedListCollection_oneElement: TestLinkedListCollection_nonEmpty {
    override var possibleValues: [LinkedList.Value] { [1] }
}

class TestLinkedListCollection_empty: TestLinkedListCollection_nonEmpty {
    override var possibleValues: [LinkedList.Value] { [] }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: RangeReplaceableCollection

class LinkedListMutableCollection<Value>: BaseLinkedList<Value>, Sequence, Collection, MutableCollection where Value: Equatable & Comparable {}

protocol LinkedListMutableCollectionTestable {
    associatedtype Value: Equatable & Comparable
    typealias LinkedList = LinkedListMutableCollection<Value>
    var linkedList: LinkedList { get set }
    var possibleValues: [Value] { get}
}

extension LinkedListMutableCollectionTestable {
    func _testSorted() {
        XCTAssertEqual(linkedList.sorted(by: { $0 > $1 }),
                       possibleValues.sorted(by: { $0 > $1 }))

    }

    func _testSubscriptReading() {
        for (index, value) in possibleValues.enumerated() {
            XCTAssertEqual(linkedList[index], value)
        }
    }

    func _testSubscriptWriting() {
        var list = linkedList
        var testArray = possibleValues
        TestBasicList.assertCollectionsContainsSameValues(linkedList: linkedList, array: testArray)
        for (index, value) in possibleValues.reversed().enumerated() {
            testArray[index] = value
            list[index] = value
            XCTAssertEqual(linkedList[index], testArray[index])
        }
        print(testArray)
        TestBasicList.assertCollectionsContainsSameValues(linkedList: linkedList, array: testArray)
    }
}

class TestLinkedListMutableCollection_nonEmptyCollection: XCTestCase, LinkedListMutableCollectionTestable {
    typealias LinkedList = LinkedListMutableCollection<Int>
    var linkedList = LinkedList()
    var possibleValues: [LinkedList.Value] { [1, 3, 2, 4] }
    override func setUp() { linkedList = LinkedList(possibleValues) }

    func testSorted() { _testSorted() }
    func testSubscriptReading() { _testSubscriptReading() }
    func testSubscriptWriting() { _testSubscriptWriting() }
}

class TestLinkedListMutableCollection_oneElement: TestLinkedListMutableCollection_nonEmptyCollection {
    override var possibleValues: [LinkedList.Value] { [1] }
}

class TestLinkedListMutableCollection_empty: TestLinkedListMutableCollection_nonEmptyCollection {
    override var possibleValues: [LinkedList.Value] { [] }
}

Answer 3

对于 Stack Overflow 来说，这确实不是一个好问题，但无论如何我都会回答。这是单链表的超级基本实现：

class Node {

    let value: Int
    var next: Node?

    init(value: Int, next: Node? = nil) {
        self.value = value
        self.next = next
    }

}

class LinkedList {

    let head: Node

    init(node: Node) {
        self.head = node
    }

    convenience init(nodeValue: Int) {
        self.init(node: Node(value: nodeValue))
    }

    func addNode(node: Node) {
        var current: Node = self.head
        while current.next != nil {
            current = current.next!
        }
        current.next = node
    }

    func addNode(withValue value: Int) {
        self.addNode(node: Node(value: value))
    }

}

let list = LinkedList(nodeValue: 4)
list.addNode(withValue: 3)
list.addNode(withValue: 8)
//The list is now [ 4 ]->[ 3 ]->[ 8 ]