LinkedList

class SKLinkedMapNode {
    var _pre: SKLinkedMapNode?
    var _next: SKLinkedMapNode?
    var _key: String
    var _value: AnyObject
    init(key: String, value: AnyObject) {
        _key = key
        _value = value
    }
}
extension SKLinkedMapNode: CustomDebugStringConvertible, CustomStringConvertible{
    var debugDescription: String {
        return "debug:\(self.description)"
    }
    
    var description: String{
        return "\(_key) \(_value)"
    }
}
extension SKLinkedMapNode: Equatable{
    static func == (lhs: SKLinkedMapNode, rhs: SKLinkedMapNode) -> Bool {
        return rhs.description == lhs.description || rhs.debugDescription == lhs.debugDescription
    }
    
    
}
struct SKLinkedMap{
    var _dic: [String: Any]
    var _head: SKLinkedMapNode?
    var _tail: SKLinkedMapNode?
    var totalCount = 0
    init() {
        _dic = [String: Any]()
    }
 
    mutating func insertNodeAtHead(_ node: SKLinkedMapNode ) -> Void {
        if _head == nil {
            _head =  node
            _tail = node
            _head?._next = _tail
            _tail?._pre = _head
        }else{
            node._next = _head
           
            _tail?._next = node
            
            _head?._pre = node
            node._pre = _tail
            _head = node
            if totalCount == 0 {
                _tail = _head;
            }
        }
        totalCount = totalCount + 1

    }
    func find(node: SKLinkedMapNode?) -> SKLinkedMapNode? {
        if node == nil {
            return nil
        }
        if self.totalCount == 0 {
            return nil
        }
        if node == _head {
            return _head
        }
        var tmp = _head?._next
        if tmp == node {
            return tmp
        }
        while tmp?._next != nil {
            if tmp?._next == node{
                return tmp?._next
            }
            if tmp?._next == _tail{
                return nil
            }
            tmp = tmp?._next
        }
        return nil
    }
    mutating func bringNodeToHead(node: SKLinkedMapNode?) -> Void {
        if node == nil {
            return
        }
        //摘除 node
        node?._pre?._next = node?._next
        node?._next?._pre = node?._pre
        //置换 head的pre 和 tail的next
        node?._next = _head
        _head?._pre = node
        _tail?._next = node
        _head = node
    }
    mutating func remoreNode(node: SKLinkedMapNode?) -> SKLinkedMapNode?{
        var tmp =  self.find(node: node)
        if tmp == nil {
            return nil
        }else{
            if tmp == _head {
                tmp = _head?._next?._pre

                _tail?._next = _head?._next
                _head?._next?._pre = _tail
                _head = _head?._next
               
            }else{
                tmp?._pre?._next = tmp?._next
                tmp?._next?._pre = tmp?._pre
            }
            totalCount = totalCount - 1
            tmp?._pre = nil
            tmp?._next = nil
        }
        return tmp
    }
    func test() -> Void {
        var tmp = _head 
        while tmp != nil {
            print(tmp)
            if tmp == _tail {
                break;
            }
            
            tmp = tmp?._next
        }
    }
}

extension String: SKNodeKey{}
extension String: SKNodeValue{}
extension Int: SKNodeValue{}
extension Int8: SKNodeValue{}
extension SKLinkedMapNode: SKNodeValue{}

var head = SKLinkedMap.init()

["A","B"].reversed().forEach { (item:String) in
    head.insertNodeAtHead(SKLinkedMapNode.init(key: item, value:  head.totalCount as AnyObject))
}

head.test()
print("\n查询节点")

var destNode = head.find(node: SKLinkedMapNode.init(key: "B", value: 4 as AnyObject))
print(destNode ?? "")
print("\n节点\(destNode)移动至首位")
head.bringNodeToHead(node: destNode)
print("\n")
head.test()

print("节点删除\(destNode)")
destNode = head.remoreNode(node: destNode)
print( destNode )
print("删除后")
head.test()

head.insertNodeAtHead(SKLinkedMapNode.init(key: "1", value: destNode as AnyObject))
print(head)

测试预览

测试预览

删除首节点 尾节点

 mutating func remoeFirst() -> SKLinkedMapNode? {
        let tmp = _head?._next?._pre
        _tail?._next = _head?._next
        _head = _head?._next
        _head?._pre = _tail
        // 尾节点的 next = 首的next
// 首节点 = 首的next
// 最后关联首位实现闭环
        return tmp
    }
   mutating func removeLast() -> SKLinkedMapNode? {
       
        if totalCount == 0 {
            return nil
        }
        let tmp = _tail
        // 删除最后一个
        _tail?._pre?._next = _head
        _head?._pre = _tail?._pre
        _tail = _head?._pre
        totalCount = totalCount - 1
        return tmp
    }

首位节点