Swift- 链表实现

/*双向链表*/
//节点
public class Node<T> {
    var value:T
    weak var previous:Node?//避免循环引用
    var next:Node?
    init(value:T) {
        self.value = value
    }
}
//链表
public class NodeLlist<T> {
    fileprivate var head:Node<T>?
    private var tail:Node<T>?
    
    public var isEmpty:Bool {
        return head == nil
    }
    
    public var first:Node<T>? {
        return head
    }
    
    public var last : Node<T>? {
        return tail
    }
    //Node add
    public func append(value:T) {
        //1.
        let newNode = Node(value: value)
        //2.
        if let tailNode = tail {
            newNode.previous = tailNode
            tailNode.next = newNode
        } else {
            head = newNode
        }
        //3.
        tail = newNode
    }
    
    //Node at
    public func nodeAt(index:Int) -> Node<T>? {
        //1.大于等于0才有意义
        if index >= 0 {
            //b2.遍历到目标node,就返回
            var node = head
            var i = index
            while node != nil {
                if i == 0 {
                    return node
                }
                i -= 1
                node = node!.next
            }
        }
        return nil
    }
    
    //move
    public func remove(node:Node<T>) -> T {
        let prevNode = node.previous
        let nextNode = node.next
        //1.node如果有prevNode,说明不是head(链表的第一个节点)，那么就更新next指针
        if let prev = prevNode {
          prev.next = nextNode
        } else { //2.没有就说明这个node是head(链表的第一个节点)，直接将next提为head
          head = nextNode
        }
        //3.将previous指针指向被移除的节点的previous指针。
        nextNode?.previous = prevNode
        //4.如果你移除的是链表的最后一个节点，那么就更新tail指针。
        if nextNode == nil {
          tail = prevNode
        }
        
        //5.将移除的节点的previous和next指针置为nil。
        node.previous = nil
        node.next = nil
        
        //6.返回移除的节点。
        return node.value
    }
    
    //move all
    public func removeAll() {
        head = nil
        tail = nil
    }
}

//重写 description属性 用于打印
extension NodeLlist: CustomStringConvertible {
    public var description: String {
        var text = "["
        var node = head
        while node != nil {
            text += "\(node!.value)"
            node = node!.next
            if node != nil { text += ", " }
        }
        return text + "]"
    }
}

extension Node : CustomStringConvertible {
    public var description: String {
        return "\(value)"
    }
}

let egNodeList = NodeLlist<String>()
egNodeList.append(value: "dog")
egNodeList.append(value: "cat")
egNodeList.append(value: "rabbit")
egNodeList.append(value: "person")

print(egNodeList)
print(egNodeList.nodeAt(index: 5) ?? "没有找到哦")
print(egNodeList.first ?? "is nil")
print(egNodeList.last ?? "is nil")

本文参考链接