Swift 创建链表(Linked List)

// 定义节点
public class LinkedListNode<T> {
    var value: T
    
    // 前一个节点
    weak var pervious: LinkedListNode?
    
    // 下一个节点
    var next: LinkedListNode?
    
    // 初始化节点
    public init(value: T) {
        self.value = value
    }
}

public class LinkedList<T> {
    public typealias Node = LinkedListNode<T>
    
    // 指向第一个节点的指针 私有
    private var head: Node?
    
    // 是否为空
    public var isEmpty: Bool {
        return head == nil
    }
    
    // 节点总数
    public var count: Int {
        guard var node = head else {
            return 0
        }
        
        var count = 1
        while let next = node.next {
            node = next
            count += 1
        }
        return count
    }
    
    // 指向第一个节点的指针 公共
    public var first: Node? {
        return head
    }
    
    // 指向最后的节点的指针
    public var last: Node? {
        guard var node = head else {
            return nil
        }
        
        // 直到 node.next 为nil
        while let next = node.next {
            node = next
        }
        return node
    }
    
    // 得到index 的 node
    public func node(atIndex index: Int) -> Node? {
        guard index != 0 else {
            return head!
        }
        
        var node = head!.next
        guard index < count else {
            return nil
        }
        
        for _ in 1 ..< index {
            node = node?.next
            if node == nil {
                break
            }
        }
        return node!
    }
    
    /// 插入节点
    //  插入到最后
    public func appendToTail(value: T) {
        let newNode = Node(value: value)
        
        // 更新最后一个节点，newNode成为最后一个节点
        // 前一个节点成为成为倒数第二个节点
        if let lastNode = last {
            newNode.pervious = lastNode
            lastNode.next = newNode
        } else {
            // 空白链表直接插入
            head = newNode
        }
    }
    
    // 插入到最前
    public func insertToHead(value: T) {
        let newHead = Node(value: value)
        if head == nil {
            // 空链表直接插入
            head = newHead
        } else {
            newHead.next = head
            head?.pervious = newHead
            head = newHead
        }
        
    }
    
    // 插入到特定的索引位置
    public func insert(_ node: Node, atIndex index: Int) {
        if index < 0 {
            print("invalid input index")
            return
        }
        
        let newNode = node
        
        if count == 0 {
            head = newNode
        } else {
            if index == 0 {
                newNode.next = head
                head?.pervious = newNode
                head = newNode
            } else {
                if index > count {
                    print("out of range")
                    return
                }
                
                let prev = self.node(atIndex: index - 1)
                let next = prev?.next
                
                newNode.pervious = prev
                newNode.next = prev?.next
                prev?.next = newNode
                next?.pervious = newNode
            }
        }
    }
    
    /// 移除节点
    // 移除所有节点
    public func removeAll(){
        head = nil
    }
    
    // 移除最后一个节点
    public func removeLast() -> T? {
        guard !isEmpty else {
            return nil
        }
        return remove(node: last!)
    }
    
    // 通过引用移除节点
    public func remove(node: Node) -> T? {
        guard head != nil else {
            print("Linked List is empty")
            return nil
        }
        
        let prev = node.pervious
        let next = node.next
        
        if let prev = prev {
            prev.next = next
        } else {
            head = next
        }
        
        next?.pervious = prev
        
        node.pervious = nil
        node.next = nil
        return node.value
    }
    
    // 通过index移除节点
    public func removeAt(_ index: Int) -> T? {
        guard head != nil else {
            print("Linked List is empty")
            return nil
        }
        
        let node = self.node(atIndex: index)
        guard node == nil else {
            return nil
        }
        return remove(node: node!)
    }
    
    // 打印所有节点
    public func printAllNodes() {
        guard head != nil else {
            print("Linked List is empty")
            return
        }

        var node = head
        print("\nsatart printing all nodes:")
        for index in 0 ..< count {
            if node == nil {
                break
            }
            print("[\(index)]\(node!.value)")
            node = node!.next
        }
    }
}

使用链表

let list = LinkedList<String>()

list.isEmpty
list.first
list.count

list.appendToTail(value: "Swift")
list.isEmpty
list.first!.value
list.count
list.last!.value

list.appendToTail(value: "Java")
list.first!.value
list.last!.value

list.insert(LinkedListNode.init(value: "C++"), atIndex: 2)

list.printAllNodes()