LinkedList

open class LinkedList<T>

Linked List. A linked list is a linear collection of data elements where each element points to the next. A linked list has several theoretical advantages over contiguous storage options such as the Swift Array:

  • Constant time insertion and removal from the front of the list.

  • Reliable performance characteristics.

    • Note

    Use a linked list over a Swift array if you need to store a large amount of data and you need to perform insertions and removals from any position in the sequence.

    Do not use a linked list if you need indexing, sorting, random access to the data or sequence traversal from the back of the sequence to the front.

    Warning

    Due to the fact that each node has a reference to the next node, the memory footprint of a linked list can have a negative impact on the device if the list becomes extremely large.

    Public Properties

    • Undocumented

      Declaration

      Swift

      public var head: LinkedListNode<T>?

    • Undocumented

      Declaration

      Swift

      public var tail: LinkedListNode<T>?

    • true if the linked list is empty. false if not.

      Declaration

      Swift

      public var isEmpty: Bool { get }

    Initialization

    • Undocumented

      Declaration

      Swift

      public init()

    Public Functions

    • Returns the linked list head’s value.

      Declaration

      Swift

      public func peek() -> T?

      Return Value

      The head’s value.

    • Returns the node at the given index, or nil if the node can’t be found.

      Complexity

      O(n)

      Declaration

      Swift

      public func node(at index: Int) -> LinkedListNode<T>?

      Parameters

      index

      The index to use.

      Return Value

      The node at the given index.

    Adding Functions

    • Adds a value at the beginning of the linked list.

      Complexity

      O(1)

      Declaration

      Swift

      @discardableResult
public func push(_ value: T) -> LinkedListNode<T>

      Parameters

      value

      The value to add.

      Return Value

      The newly added node.

    • Appends a value at the end of the linked list.

      Complexity

      O(1)

      Declaration

      Swift

      @discardableResult
public func append(_ value: T) -> LinkedListNode<T>

      Parameters

      value

      The value to add.

      Return Value

      The newly added node.

    • Inserts a value after the given node.

      Complexity

      O(1)

      Declaration

      Swift

      @discardableResult
public func insert(value: T, after node: LinkedListNode<T>) -> LinkedListNode<T>

      Parameters

      value

      The value to insert.
      node

      The node to add after.

      Return Value

      The newly added node.

    Removing Functions

    • Removes the value at the top of the list.

      Complexity

      O(1)

      Declaration

      Swift

      public func pop() -> T?

      Return Value

      The value at top of the list.

    • Removes the last node of the list.

      Complexity

      O(n)

      Declaration

      Swift

      public func removeLast() -> T?

      Return Value

      The value at the end of the list.

    • Removes the node after the given node.

      Complexity

      O(1)

      Declaration

      Swift

      @discardableResult
public func remove(after node: LinkedListNode<T>) -> T?

      Parameters

      node

      The node to use.

      Return Value

      The value removed.