DoublyLink

public class DoublyLink<Element>

DoublyLink: Minimal doubly linked list used for LRU ordering.

Designed as a building block for higher-level queues (such as priority-based LRU structures), providing O(1) average operations for push/pop from both ends and node removal when the node reference is known.

Complexity

Complexity:

  • enqueueFront: O(1)
  • dequeueFront / dequeueBack: O(1)
  • removeNode (with node reference): O(1)

  • Thread-safety: Not synchronized; use external synchronization when accessed concurrently.

  • Invariants: front is the most-recent node; back is the least-recent node; count is >= 0.

  • Most-recent node (head) of the list.

    Declaration

    Swift

    public private(set) var front: Node? { get }

  • Least-recent node (tail) of the list.

    Declaration

    Swift

    public private(set) var back: Node? { get }

  • Number of nodes currently in the list.

    Declaration

    Swift

    public private(set) var count: Int { get }

  • Maximum number of nodes allowed; 0 means no storage.

    Declaration

    Swift

    public let capacity: Int

  • Creates a list with the given maximum number of nodes.

    Declaration

    Swift

    public init(with capacity: Int)

    Parameters

    capacity

    Maximum number of nodes to retain.

  • Enqueues a new element at the front of the queue. If the queue is full, removes the least recently used (back) node.

    Declaration

    Swift

    @discardableResult
public func enqueueFront(element: Element) -> (newNode: Node?, evictedNode: Node?)

    Parameters

    key

    Key of the new element.
    element

    Value of the new element.

    Return Value

    Tuple of the new node and the evicted node (if any). When capacity == 0, no node is created and the returned evictedNode echoes the input element.

  • Eviction strategy applied when enqueuing into a full list.

    See more

    Declaration

    Swift

    public enum EvictedStrategy

  • Enqueues an existing node to the front of the queue. Removes the least recently used node if at capacity, unless .LIFO is specified, in which case the insertion is rejected and the original node is returned.

    Declaration

    Swift

    @discardableResult
public func enqueueFront(node: Node, evictedStrategy: EvictedStrategy = .FIFO) -> Node?

    Parameters

    node

    Node to enqueue.

    Return Value

    Evicted node if any; returns the input node when rejected due to .LIFO policy; otherwise nil.

  • Removes and returns the node at the back of the queue (least recently used).

    Declaration

    Swift

    @discardableResult
public func dequeueBack() -> Node?

    Return Value

    The removed node, or nil if queue is empty.

  • Removes and returns the node at the front of the queue (most recently used).

    Declaration

    Swift

    @discardableResult
public func dequeueFront() -> Node?

    Return Value

    The removed node, or nil if queue is empty.

  • Removes a specific node from the queue.

    Important

    The node must currently belong to this list; removing an external node yields undefined behavior and will corrupt count.

    Declaration

    Swift

    public func removeNode(_ node: Node)

    Parameters

    node

    The node to remove.

  • A node in the doubly linked list storing the element and links to adjacent nodes.

    See more

    Declaration

    Swift

    class Node