LinkedList

public class LinkedList<Value> : Sequence, CustomStringConvertible
extension LinkedList: Equatable where Value: Equatable

A doubly linked list.

Discussion

A workflow is ultimately a doubly linked list. This is the underlying sequence type used.

  • The beginning index of the linked list (0 indexed).

    Complexity

    O(1)

    Declaration

    Swift

    public var startIndex: LinkedList.Index { get }

  • The last index in the list.

    Complexity

    O(n). The linked list must traverse to the end.

    Declaration

    Swift

    public var endIndex: LinkedList.Index { get }

  • A textual representation of the linked list and its elements.

    Declaration

    Swift

    public var description: String { get }

  • A boolean to indicate whether the linked list contains any values.

    Complexity

    O(1)

    Declaration

    Swift

    public var isEmpty: Bool { get }

  • The number of elements in the linked list.

    Complexity

    O(n). The linked list must traverse to the end to determine the count.

    Declaration

    Swift

    public var count: LinkedList.Index { get }

  • The first node in the linked list.

    Declaration

    Swift

    public var first: Element?

  • The last node in the linked list.

    Complexity

    O(n). The linked list must traverse to the end.

    Declaration

    Swift

    public var last: Element? { get }

  • Creates a copy of a LinkedList by providing the first node and copying it.

    Declaration

    Swift

    public required init(_ node: Element? = nil)

  • Creates a LinkedList by providing the first node in the list.

    Important

    This can potentially cause memory retention issues, you are passing a reference, be aware.

    Declaration

    Swift

    public required init(withoutCopying node: Element?)

  • Returns an iterator over the elements of this sequence.

    Declaration

    Swift

    public func makeIterator() -> Iterator

  • Returns the last element of the sequence that satisfies the given predicate.

    Complexity

    O(n). The linked list must traverse to the end.

    Example

    This example uses the last(where:) method to find the last negative number in an array of integers:

    let numbers = LinkedList([3, 7, 4, -2, 9, -6, 10, 1])
if let lastNegative = numbers.last(where: { $0.value < 0 }) {
   print("The last negative number is \(lastNegative).")
}
// Prints "The last negative number is -6."

    Declaration

    Swift

    public func last(where predicate: (Element) throws -> Bool) rethrows -> Element?

    Parameters

    predicate

    A closure that takes an element of the sequence as its argument and returns a Boolean value indicating whether the element is a match.

    Return Value

    The last element of the sequence that satisfies predicate, or nil if there is no element that satisfies predicate.

  • Appends a new node to the end of the linked list.

    Important

    This operation mutates the original LinkedList.

    Declaration

    Swift

    public func append(_ element: Value)

    Parameters

    element

    the concrete value that should be appended.

  • Appends a collection of nodes to the end of the linked list.

    Important

    This operation mutates the original LinkedList.

    Declaration

    Swift

    public func append<S>(contentsOf newElements: S) where Value == S.Element, S : Sequence

    Parameters

    newElements

    a sequence of concrete elements that should be appended.

  • Inserts a new node at a specified location.

    Important

    This operation mutates the original LinkedList.

    Declaration

    Swift

    public func insert(_ element: Value, atIndex i: Index)

    Parameters

    element

    the concrete value that should be inserted.
    i

    the index the value should be inserted at.

  • Inserts a sequence of new nodes at a specified location.

    Important

    This operation mutates the original LinkedList.

    Declaration

    Swift

    public func insert<C>(contentsOf newElements: C, at i: Index) where Value == C.Element, C : Collection

    Parameters

    newElements

    a sequence of concrete values that should be inserted.
    i

    the index the sequence should be inserted at.

  • Removes a node at the specified index.

    Important

    This operation mutates the original LinkedList.

    Important

    If you pass an index greater than the count of the LinkedList this will be a NO-OP.

    Declaration

    Swift

    public func remove(at i: Index)

    Parameters

    i

    the index the value should be removed from.

  • Removes a node at the specified index.

    Important

    This operation mutates the original LinkedList.

    Declaration

    Swift

    public func remove(where predicate: (Element) -> Bool)

    Parameters

    predicate

    a closure indicating whether that node should be removed.

  • Removes the first n nodes from the linked list.

    Important

    This operation mutates the original LinkedList.

    Important

    If you pass a value greater than the count of the linked list you will remove all items.

    Declaration

    Swift

    public func removeFirst(_ n: Int = 1)

    Parameters

    n

    the number of nodes that should be removed.

  • Removes the last n nodes from the linked list.

    Important

    This operation mutates the original LinkedList.

    Important

    If you pass a value greater than the count of the linked list you will remove all items.

    Declaration

    Swift

    public func removeLast(_ n: Int = 1)

    Parameters

    n

    the number of nodes that should be removed.

  • Removes the last node from the linked list; returns the removed concrete type.

    Important

    This operation mutates the original LinkedList.

    Declaration

    Swift

    public func popLast() -> Value?

    Return Value

    the concrete type the node encapsulated that was removed; nil if no node exists.

  • Removes all nodes from the linked list.

    Important

    This operation mutates the original LinkedList.

    Declaration

    Swift

    public func removeAll()

  • Swaps the concrete values of 2 nodes.

    Important

    This operation mutates the original LinkedList.

    Important

    If you call this with an invalid index you will cause a fatalError and stop execution of the process.

    Declaration

    Swift

    public func swapAt(_ i: Int, _ j: Int)

    Parameters

    i

    the index of the first item to be swapped.
    j

    the index of the second item to be swapped.

  • Replaces the concrete value of the node at the specified index.

    Important

    This operation mutates the original LinkedList.

    Important

    If you call this with an invalid index this will be a NO-OP.

    Declaration

    Swift

    public func replace(atIndex index: Int, withItem newItem: Value)

    Parameters

    index

    the index of the node with the value to be replaced.
    newItem

    the concrete value that should replace the old value.

  • Reverses the linked list.

    Important

    This operation mutates the original LinkedList.

    Declaration

    Swift

    public func reverse()

  • Sorts the linked list.

    Important

    This operation mutates the original LinkedList.

    Important

    This will not mutate any references to nodes you have, for memory and performance reasons this sorts the LinkedList without modifying original nodes.

    Complexity

    O(n log(n)) This uses Merge Sort under the covers and is more performant than the built in alternative.

    Declaration

    Swift

    public func sort(by comparator: (Value, Value) -> Bool)

    Parameters

    comparator

    a closure that takes in 2 concrete types and indicates how they should be sorted.

  • Returns a new version of the LinkedList with all elements reversed.

    Declaration

    Swift

    public func reversed() -> LinkedList<Value>

  • Returns a new version of the linked list with a specific element replaced.

    Declaration

    Swift

    public func replacing(atIndex index: Int, withItem newItem: Value) -> LinkedList<Value>

    Parameters

    index

    the index of the node whose concrete value should be replaced.
    newItem

    the concrete value to replace.

  • Returns a new, sorted version of the linked list.

    Complexity

    O(n log(n)) This uses Merge Sort under the covers and is more performant than the built in alternative.

    Declaration

    Swift

    public func sorted(by comparator: (Value, Value) -> Bool) -> LinkedList<Value>

    Parameters

    comparator

    a closure that takes in 2 concrete types and indicates how they should be sorted.

  • Returns a new version of the linked list without the first n items.

    Important

    If you pass in an index that is out of the range of the linked list an empty LinkedList will be returned.

    Declaration

    Swift

    public func dropFirst(_ n: Int = 1) -> SubSequence

    Parameters

    n

    the number of items to drop from the start of the list.

  • Returns a new version of the linked list without the last n items.

    Important

    If you pass in an index that is out of the range of the linked list an empty LinkedList will be returned.

    Declaration

    Swift

    public func dropLast(_ n: Int = 1) -> SubSequence

    Parameters

    n

    the number of items to drop from the end of the list.

  • Returns a linked list by skipping elements while predicate returns true and returning the remaining elements.

    Declaration

    Swift

    public func drop(while predicate: (Value) throws -> Bool) rethrows -> SubSequence

    Parameters

    predicate

    a closure that takes a concrete type of the node as its argument and returns true if the element should be skipped or false if it should be included. Once the predicate returns false it will not be called again.

  • Returns a new version of the linked list with just the first n items.

    Important

    If you pass in an index that is greater than the size of the linked list you’ll get the full list. If you send in an index of 0 or smaller, you’ll get an empty list back.

    Declaration

    Swift

    public func prefix(_ maxLength: Int) -> SubSequence

    Parameters

    maxLength

    the number of items to return.

  • Returns a linked list containing the initial elements until predicate returns false and skipping the remaining elements.

    Declaration

    Swift

    public func prefix(while predicate: (Value) throws -> Bool) rethrows -> SubSequence

    Parameters

    predicate

    a closure that takes a concrete type of the node as its argument and returns true if the element should be included or false if it should be excluded. Once the predicate returns false it will not be called again.

  • Returns a new version of the linked list with just the last n items.

    Declaration

    Swift

    public func suffix(_ maxLength: Int) -> SubSequence

    Parameters

    maxLength

    the number of items to return.

Available where Value: Comparable

  • Sorts the linked list in place using a merge sort.

    Important

    This will not mutate any references to nodes you have, for memory and performance reasons this sorts the LinkedList without modifying original nodes.

    Declaration

    Swift

    public func sort()

  • Returns a sorted version of the linked list.

    Declaration

    Swift

    public func sorted() -> LinkedList<Value>

  • Returns the maximum concrete value in the linked list; nil if there is none.

    Declaration

    Swift

    public func max() -> Value?

  • Returns the minimum concrete value in the linked list; nil if there is none.

    Declaration

    Swift

    public func min() -> Value?

Available where Value: Equatable

  • Returns a boolean indicating whether the given value is present in the linked list.

    Declaration

    Swift

    public func contains(_ element: Element.Value) -> Bool

    Parameters

    element

    the value to check against the linked list.