Module lists

Implementation of singly and doubly linked lists. Because it makes no sense to do so, the 'next' and 'prev' pointers are not hidden from you and can be manipulated directly for efficiency.

Types

DoublyLinkedNodeObj[T] = object
  next*, prev*: ref DoublyLinkedNodeObj[T]
  value*: T

a node a doubly linked list consists of

DoublyLinkedNode[T] = ref DoublyLinkedNodeObj[T]

SinglyLinkedNodeObj[T] = object
  next*: ref SinglyLinkedNodeObj[T]
  value*: T

a node a singly linked list consists of

SinglyLinkedNode[T] = ref SinglyLinkedNodeObj[T]

SinglyLinkedList[T] = object
  head*, tail*: SinglyLinkedNode[T]

a singly linked list

DoublyLinkedList[T] = object
  head*, tail*: DoublyLinkedNode[T]

a doubly linked list

SinglyLinkedRing[T] = object
  head*, tail*: SinglyLinkedNode[T]

a singly linked ring

DoublyLinkedRing[T] = object
  head*: DoublyLinkedNode[T]

a doubly linked ring

SomeLinkedList[T] = SinglyLinkedList[T] | DoublyLinkedList[T]

SomeLinkedRing[T] = SinglyLinkedRing[T] | DoublyLinkedRing[T]

SomeLinkedCollection[T] = SomeLinkedList[T] | SomeLinkedRing[T]

SomeLinkedNode[T] = SinglyLinkedNode[T] | DoublyLinkedNode[T]

Procs

proc initSinglyLinkedList[T](): SinglyLinkedList[T]

creates a new singly linked list that is empty.

proc initDoublyLinkedList[T](): DoublyLinkedList[T]

creates a new doubly linked list that is empty.

proc initSinglyLinkedRing[T](): SinglyLinkedRing[T]

creates a new singly linked ring that is empty.

proc initDoublyLinkedRing[T](): DoublyLinkedRing[T]

creates a new doubly linked ring that is empty.

proc newDoublyLinkedNode[T](value: T): DoublyLinkedNode[T]

creates a new doubly linked node with the given value.

proc newSinglyLinkedNode[T](value: T): SinglyLinkedNode[T]

creates a new singly linked node with the given value.

proc `$`[T](L: SomeLinkedCollection[T]): string

turns a list into its string representation.

proc find[T](L: SomeLinkedCollection[T]; value: T): SomeLinkedNode[T]

searches in the list for a value. Returns nil if the value does not exist.

proc contains[T](L: SomeLinkedCollection[T]; value: T): bool {...}{.inline.}

searches in the list for a value. Returns false if the value does not exist, true otherwise.

proc prepend[T](L: var SinglyLinkedList[T]; n: SinglyLinkedNode[T]) {...}{.inline.}

prepends a node to L. Efficiency: O(1).

proc prepend[T](L: var SinglyLinkedList[T]; value: T) {...}{.inline.}

prepends a node to L. Efficiency: O(1).

proc append[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])

appends a node n to L. Efficiency: O(1).

proc append[T](L: var DoublyLinkedList[T]; value: T)

appends a value to L. Efficiency: O(1).

proc prepend[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])

prepends a node n to L. Efficiency: O(1).

proc prepend[T](L: var DoublyLinkedList[T]; value: T)

prepends a value to L. Efficiency: O(1).

proc remove[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])

removes n from L. Efficiency: O(1).

proc append[T](L: var SinglyLinkedRing[T]; n: SinglyLinkedNode[T])

appends a node n to L. Efficiency: O(1).

proc append[T](L: var SinglyLinkedRing[T]; value: T)

appends a value to L. Efficiency: O(1).

proc prepend[T](L: var SinglyLinkedRing[T]; n: SinglyLinkedNode[T])

prepends a node n to L. Efficiency: O(1).

proc prepend[T](L: var SinglyLinkedRing[T]; value: T)

prepends a value to L. Efficiency: O(1).

proc append[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])

appends a node n to L. Efficiency: O(1).

proc append[T](L: var DoublyLinkedRing[T]; value: T)

appends a value to L. Efficiency: O(1).

proc prepend[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])

prepends a node n to L. Efficiency: O(1).

proc prepend[T](L: var DoublyLinkedRing[T]; value: T)

prepends a value to L. Efficiency: O(1).

proc remove[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])

removes n from L. Efficiency: O(1).

Iterators

iterator items[T](L: SomeLinkedList[T]): T

yields every value of L.

iterator items[T](L: SomeLinkedRing[T]): T

yields every value of L.

iterator mitems[T](L: var SomeLinkedList[T]): var T

yields every value of L so that you can modify it.

iterator mitems[T](L: var SomeLinkedRing[T]): var T

yields every value of L so that you can modify it.

iterator nodes[T](L: SomeLinkedList[T]): SomeLinkedNode[T]

iterates over every node of x. Removing the current node from the list during traversal is supported.

iterator nodes[T](L: SomeLinkedRing[T]): SomeLinkedNode[T]

iterates over every node of x. Removing the current node from the list during traversal is supported.