Shawn

public class Node {
    public var prev: Node?
    public var next: Node?
    public var id: String
    public var data: String
    
    public init(prev: Node? = nil, next: Node? = nil, id: String, data: String) {
        self.prev = prev
        self.next = next
        self.id = id
        self.data = data
    }
}

public class LRUCacheDoublyLinkedList {
    private var size: Int = 0
    let capacity: Int
    private var head: Node?
    private var tail: Node?
    
    
    private var dict: [String: Node] = [:]
    
    public init(capacity: Int) {
        self.capacity = capacity
    }
    
    //Update the node to be the head
    private func update(_ node: Node) {
        let prev = node.prev
        let next = node.next
        
        //It is a middle node in the list
        if prev != nil {
            prev?.next = next
        }
        else {
            //This case It is first node(head)
            head = next
        }
        //If it is not last node
        if next != nil {
            next?.prev = prev
        }
        else {
            //It is the last node (tail)
            tail = prev
        }
        add(node)
    }
    
    //get item with ID and move to the head because It used
    public func get(_ id: String) -> Node? {
        guard let node = dict[id] else {
            return nil
        }
        update(node)
        return node
    }
    
    //Always add node at Head
    private func add(_ node: Node) {
        node.next = head
        if head != nil {
            head?.prev = node
        }
        //Set new head node
        head = node
        
        //If there is 1 node in the list, it is the head as well as the tail
        if tail == nil {
            tail = node
        }
        dict[node.id] = node
    }
    
    private func removeTail() {
        let tailId = tail?.id
        var cachedTail: Node?
        if let tailId = tail?.id, let lastNode = dict[tailId] {
            cachedTail = lastNode
        }
        tail = tail?.prev
        if tail != nil {
            tail?.next = nil
        }
        
        if let tailId {
            dict.removeValue(forKey: tailId)
        }
        cachedTail = nil
    }
    
    public func put(id: String, data: String) {
        if let node = dict[id] {
            node.data = data
            update(node)
            return
        }
        
        //the data is not present in the cache so insert
        let newNode = Node(id: id, data: data)
        
        //Check cache size
        if size < capacity {
            size += 1
            //insert into the cache and set it to be the head node
            add(newNode)
        }
        else {
            //cache is full, remove the last item and insert new one
            removeTail()
            add(newNode)
        }
    }
    
    public func printAll() {
        var pointNode = head
        while pointNode != nil {
            if let data = pointNode?.data {
                print("\(data)", terminator: pointNode?.next != nil ? " -> " : "")
            }
            pointNode = pointNode?.next
        }
        print("\n")
    }
}