Implementation of:
- singly linked lists
- doubly linked lists
- singly linked rings (circular lists)
- doubly linked rings (circular lists)
Basic Usage
Because it makes no sense to do otherwise, the next and prev pointers are not hidden from you and can be manipulated directly for efficiency.
Lists
Example:
import std/lists var list = initDoublyLinkedList[int]() let a = newDoublyLinkedNode[int](3) b = newDoublyLinkedNode[int](7) c = newDoublyLinkedNode[int](9) list.add(a) list.add(b) list.prepend(c) assert a.next == b assert a.prev == c assert c.next == a assert c.next.next == b assert c.prev == nil assert b.next == nil
Rings
Example:
import std/lists var ring = initSinglyLinkedRing[int]() let a = newSinglyLinkedNode[int](3) b = newSinglyLinkedNode[int](7) c = newSinglyLinkedNode[int](9) ring.add(a) ring.add(b) ring.prepend(c) assert c.next == a assert a.next == b assert c.next.next == b assert b.next == c assert c.next.next.next == c
See also
- deques module for double-ended queues
- sharedlist module for shared singly-linked lists
Types
DoublyLinkedList[T] = object head*: DoublyLinkedNode[T] tail* {.cursor.}: DoublyLinkedNode[T]
- A doubly linked list. Source Edit
DoublyLinkedNode[T] = ref DoublyLinkedNodeObj[T]
- Source Edit
DoublyLinkedNodeObj[T] = object next*: DoublyLinkedNode[T] prev* {.cursor.}: DoublyLinkedNode[T] value*: T
-
A node of a doubly linked list.
It consists of a value field, and pointers to next and prev.
Source Edit DoublyLinkedRing[T] = object head*: DoublyLinkedNode[T]
- A doubly linked ring. Source Edit
SinglyLinkedList[T] = object head*: SinglyLinkedNode[T] tail* {.cursor.}: SinglyLinkedNode[T]
- A singly linked list. Source Edit
SinglyLinkedNode[T] = ref SinglyLinkedNodeObj[T]
- Source Edit
SinglyLinkedNodeObj[T] = object next*: SinglyLinkedNode[T] value*: T
-
A node of a singly linked list.
It consists of a value field, and a pointer to next.
Source Edit SinglyLinkedRing[T] = object head*: SinglyLinkedNode[T] tail* {.cursor.}: SinglyLinkedNode[T]
- A singly linked ring. Source Edit
SomeLinkedCollection[T] = SomeLinkedList[T] | SomeLinkedRing[T]
- Source Edit
SomeLinkedList[T] = SinglyLinkedList[T] | DoublyLinkedList[T]
- Source Edit
SomeLinkedNode[T] = SinglyLinkedNode[T] | DoublyLinkedNode[T]
- Source Edit
SomeLinkedRing[T] = SinglyLinkedRing[T] | DoublyLinkedRing[T]
- Source Edit
Procs
proc `$`[T](L: SomeLinkedCollection[T]): string
-
Turns a list into its string representation for logging and printing.
Example:
let a = [1, 2, 3, 4].toSinglyLinkedList assert $a == "[1, 2, 3, 4]"
Source Edit proc add[T: SomeLinkedList](a: var T; b: T)
-
Appends a shallow copy of b to the end of a.
See also:
- addMoved proc
- addMoved proc for moving the second list instead of copying
Example:
from std/sequtils import toSeq var a = [1, 2, 3].toSinglyLinkedList let b = [4, 5].toSinglyLinkedList a.add(b) assert a.toSeq == [1, 2, 3, 4, 5] assert b.toSeq == [4, 5] a.add(a) assert a.toSeq == [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
Source Edit proc add[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])
-
Appends (adds to the end) a node n to L. Efficiency: O(1).
See also:
- add proc for appending a value
- prepend proc for prepending a node
- prepend proc for prepending a value
- remove proc for removing a node
Example:
var a = initDoublyLinkedList[int]() let n = newDoublyLinkedNode[int](9) a.add(n) assert a.contains(9)
Source Edit proc add[T](L: var DoublyLinkedList[T]; value: T)
-
Appends (adds to the end) a value to L. Efficiency: O(1).
See also:
- add proc for appending a node
- prepend proc for prepending a node
- prepend proc for prepending a value
- remove proc for removing a node
Example:
var a = initDoublyLinkedList[int]() a.add(9) a.add(8) assert a.contains(9)
Source Edit proc add[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])
-
Appends (adds to the end) a node n to L. Efficiency: O(1).
See also:
- add proc for appending a value
- prepend proc for prepending a node
- prepend proc for prepending a value
- remove proc for removing a node
Example:
var a = initDoublyLinkedRing[int]() let n = newDoublyLinkedNode[int](9) a.add(n) assert a.contains(9)
Source Edit proc add[T](L: var DoublyLinkedRing[T]; value: T)
-
Appends (adds to the end) a value to L. Efficiency: O(1).
See also:
- add proc for appending a node
- prepend proc for prepending a node
- prepend proc for prepending a value
- remove proc for removing a node
Example:
var a = initDoublyLinkedRing[int]() a.add(9) a.add(8) assert a.contains(9)
Source Edit proc add[T](L: var SinglyLinkedList[T]; n: SinglyLinkedNode[T]) {.inline.}
-
Appends (adds to the end) a node n to L. Efficiency: O(1).
See also:
- add proc for appending a value
- prepend proc for prepending a node
- prepend proc for prepending a value
Example:
var a = initSinglyLinkedList[int]() let n = newSinglyLinkedNode[int](9) a.add(n) assert a.contains(9)
Source Edit proc add[T](L: var SinglyLinkedList[T]; value: T) {.inline.}
-
Appends (adds to the end) a value to L. Efficiency: O(1).
See also:
- add proc for appending a value
- prepend proc for prepending a node
- prepend proc for prepending a value
Example:
var a = initSinglyLinkedList[int]() a.add(9) a.add(8) assert a.contains(9)
Source Edit proc add[T](L: var SinglyLinkedRing[T]; n: SinglyLinkedNode[T])
-
Appends (adds to the end) a node n to L. Efficiency: O(1).
See also:
- add proc for appending a value
- prepend proc for prepending a node
- prepend proc for prepending a value
Example:
var a = initSinglyLinkedRing[int]() let n = newSinglyLinkedNode[int](9) a.add(n) assert a.contains(9)
Source Edit proc add[T](L: var SinglyLinkedRing[T]; value: T)
-
Appends (adds to the end) a value to L. Efficiency: O(1).
See also:
- add proc for appending a node
- prepend proc for prepending a node
- prepend proc for prepending a value
Example:
var a = initSinglyLinkedRing[int]() a.add(9) a.add(8) assert a.contains(9)
Source Edit proc addMoved[T](a, b: var DoublyLinkedList[T])
-
Moves b to the end of a. Efficiency: O(1). Note that b becomes empty after the operation unless it has the same address as a. Self-adding results in a cycle.
See also:
- add proc for adding a copy of a list
Example:
import std/[sequtils, enumerate, sugar] var a = [1, 2, 3].toDoublyLinkedList b = [4, 5].toDoublyLinkedList c = [0, 1].toDoublyLinkedList a.addMoved(b) assert a.toSeq == [1, 2, 3, 4, 5] assert b.toSeq == [] c.addMoved(c) let s = collect: for i, ci in enumerate(c): if i == 6: break ci assert s == [0, 1, 0, 1, 0, 1]
Source Edit proc addMoved[T](a, b: var SinglyLinkedList[T])
-
Moves b to the end of a. Efficiency: O(1). Note that b becomes empty after the operation unless it has the same address as a. Self-adding results in a cycle.
See also:
- add proc for adding a copy of a list
Example:
import std/[sequtils, enumerate, sugar] var a = [1, 2, 3].toSinglyLinkedList b = [4, 5].toSinglyLinkedList c = [0, 1].toSinglyLinkedList a.addMoved(b) assert a.toSeq == [1, 2, 3, 4, 5] assert b.toSeq == [] c.addMoved(c) let s = collect: for i, ci in enumerate(c): if i == 6: break ci assert s == [0, 1, 0, 1, 0, 1]
Source Edit proc append[T](a: var (DoublyLinkedList[T] | DoublyLinkedRing[T]); b: DoublyLinkedList[T] | DoublyLinkedNode[T] | T)
-
Alias for a.add(b).
See also:
Source Edit proc append[T](a: var (SinglyLinkedList[T] | SinglyLinkedRing[T]); b: SinglyLinkedList[T] | SinglyLinkedNode[T] | T)
-
Alias for a.add(b).
See also:
Source Edit proc appendMoved[T: SomeLinkedList](a, b: var T)
-
Alias for a.addMoved(b).
See also:
Source Edit 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. This allows the usage of the in and notin operators.
See also:
Example:
let a = [9, 8].toSinglyLinkedList assert a.contains(9) assert 8 in a assert(not a.contains(1)) assert 2 notin a
Source Edit func copy[T](a: DoublyLinkedList[T]): DoublyLinkedList[T]
-
Creates a shallow copy of a.
Example:
from std/sequtils import toSeq type Foo = ref object x: int var f = Foo(x: 1) a = [f].toDoublyLinkedList let b = a.copy a.add([f].toDoublyLinkedList) assert a.toSeq == [f, f] assert b.toSeq == [f] # b isn't modified... f.x = 42 assert a.head.value.x == 42 assert b.head.value.x == 42 # ... but the elements are not deep copied let c = [1, 2, 3].toDoublyLinkedList assert $c == $c.copy
Source Edit func copy[T](a: SinglyLinkedList[T]): SinglyLinkedList[T]
-
Creates a shallow copy of a.
Example:
from std/sequtils import toSeq type Foo = ref object x: int var f = Foo(x: 1) a = [f].toSinglyLinkedList let b = a.copy a.add([f].toSinglyLinkedList) assert a.toSeq == [f, f] assert b.toSeq == [f] # b isn't modified... f.x = 42 assert a.head.value.x == 42 assert b.head.value.x == 42 # ... but the elements are not deep copied let c = [1, 2, 3].toSinglyLinkedList assert $c == $c.copy
Source Edit 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.
See also:
Example:
let a = [9, 8].toSinglyLinkedList assert a.find(9).value == 9 assert a.find(1) == nil
Source Edit proc initDoublyLinkedList[T](): DoublyLinkedList[T]
-
Creates a new doubly linked list that is empty.
Doubly linked lists are initialized by default, so it is not necessary to call this function explicitly.
Example:
let a = initDoublyLinkedList[int]()
Source Edit proc initDoublyLinkedRing[T](): DoublyLinkedRing[T]
-
Creates a new doubly linked ring that is empty.
Doubly linked rings are initialized by default, so it is not necessary to call this function explicitly.
Example:
let a = initDoublyLinkedRing[int]()
Source Edit proc initSinglyLinkedList[T](): SinglyLinkedList[T]
-
Creates a new singly linked list that is empty.
Singly linked lists are initialized by default, so it is not necessary to call this function explicitly.
Example:
let a = initSinglyLinkedList[int]()
Source Edit proc initSinglyLinkedRing[T](): SinglyLinkedRing[T]
-
Creates a new singly linked ring that is empty.
Singly linked rings are initialized by default, so it is not necessary to call this function explicitly.
Example:
let a = initSinglyLinkedRing[int]()
Source Edit proc newDoublyLinkedNode[T](value: T): DoublyLinkedNode[T]
-
Creates a new doubly linked node with the given value.
Example:
let n = newDoublyLinkedNode[int](5) assert n.value == 5
Source Edit proc newSinglyLinkedNode[T](value: T): SinglyLinkedNode[T]
-
Creates a new singly linked node with the given value.
Example:
let n = newSinglyLinkedNode[int](5) assert n.value == 5
Source Edit proc prepend[T: SomeLinkedList](a: var T; b: T)
-
Prepends a shallow copy of b to the beginning of a.
See also:
- prependMoved proc for moving the second list instead of copying
Example:
from std/sequtils import toSeq var a = [4, 5].toSinglyLinkedList let b = [1, 2, 3].toSinglyLinkedList a.prepend(b) assert a.toSeq == [1, 2, 3, 4, 5] assert b.toSeq == [1, 2, 3] a.prepend(a) assert a.toSeq == [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
Source Edit proc prepend[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])
-
Prepends (adds to the beginning) a node n to L. Efficiency: O(1).
See also:
- add proc for appending a node
- add proc for appending a value
- prepend proc for prepending a value
- remove proc for removing a node
Example:
var a = initDoublyLinkedList[int]() let n = newDoublyLinkedNode[int](9) a.prepend(n) assert a.contains(9)
Source Edit proc prepend[T](L: var DoublyLinkedList[T]; value: T)
-
Prepends (adds to the beginning) a value to L. Efficiency: O(1).
See also:
- add proc for appending a node
- add proc for appending a value
- prepend proc for prepending a node
- remove proc for removing a node
Example:
var a = initDoublyLinkedList[int]() a.prepend(9) a.prepend(8) assert a.contains(9)
Source Edit proc prepend[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])
-
Prepends (adds to the beginning) a node n to L. Efficiency: O(1).
See also:
- add proc for appending a node
- add proc for appending a value
- prepend proc for prepending a value
- remove proc for removing a node
Example:
var a = initDoublyLinkedRing[int]() let n = newDoublyLinkedNode[int](9) a.prepend(n) assert a.contains(9)
Source Edit proc prepend[T](L: var DoublyLinkedRing[T]; value: T)
-
Prepends (adds to the beginning) a value to L. Efficiency: O(1).
See also:
- add proc for appending a node
- add proc for appending a value
- prepend proc for prepending a node
- remove proc for removing a node
Example:
var a = initDoublyLinkedRing[int]() a.prepend(9) a.prepend(8) assert a.contains(9)
Source Edit proc prepend[T](L: var SinglyLinkedList[T]; n: SinglyLinkedNode[T]) {.inline.}
-
Prepends (adds to the beginning) a node to L. Efficiency: O(1).
See also:
- add proc for appending a node
- add proc for appending a value
- prepend proc for prepending a value
Example:
var a = initSinglyLinkedList[int]() let n = newSinglyLinkedNode[int](9) a.prepend(n) assert a.contains(9)
Source Edit proc prepend[T](L: var SinglyLinkedList[T]; value: T) {.inline.}
-
Prepends (adds to the beginning) a node to L. Efficiency: O(1).
See also:
- add proc for appending a node
- add proc for appending a value
- prepend proc for prepending a node
Example:
var a = initSinglyLinkedList[int]() a.prepend(9) a.prepend(8) assert a.contains(9)
Source Edit proc prepend[T](L: var SinglyLinkedRing[T]; n: SinglyLinkedNode[T])
-
Prepends (adds to the beginning) a node n to L. Efficiency: O(1).
See also:
- add proc for appending a node
- add proc for appending a value
- prepend proc for prepending a value
Example:
var a = initSinglyLinkedRing[int]() let n = newSinglyLinkedNode[int](9) a.prepend(n) assert a.contains(9)
Source Edit proc prepend[T](L: var SinglyLinkedRing[T]; value: T)
-
Prepends (adds to the beginning) a value to L. Efficiency: O(1).
See also:
- add proc for appending a node
- add proc for appending a value
- prepend proc for prepending a node
Example:
var a = initSinglyLinkedRing[int]() a.prepend(9) a.prepend(8) assert a.contains(9)
Source Edit proc prependMoved[T: SomeLinkedList](a, b: var T)
-
Moves b before the head of a. Efficiency: O(1). Note that b becomes empty after the operation unless it has the same address as a. Self-prepending results in a cycle.
See also:
- prepend proc for prepending a copy of a list
Example:
import std/[sequtils, enumerate, sugar] var a = [4, 5].toSinglyLinkedList b = [1, 2, 3].toSinglyLinkedList c = [0, 1].toSinglyLinkedList a.prependMoved(b) assert a.toSeq == [1, 2, 3, 4, 5] assert b.toSeq == [] c.prependMoved(c) let s = collect: for i, ci in enumerate(c): if i == 6: break ci assert s == [0, 1, 0, 1, 0, 1]
Source Edit proc remove[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])
-
Removes a node n from L. Efficiency: O(1). This function assumes, for the sake of efficiency, that n is contained in L, otherwise the effects are undefined. When the list is cyclic, the cycle is preserved after removal.
Example:
import std/[sequtils, enumerate, sugar] var a = [0, 1, 2].toSinglyLinkedList let n = a.head.next assert n.value == 1 a.remove(n) assert a.toSeq == [0, 2] a.remove(n) assert a.toSeq == [0, 2] a.addMoved(a) # cycle: [0, 2, 0, 2, ...] a.remove(a.head) let s = collect: for i, ai in enumerate(a): if i == 4: break ai assert s == [2, 2, 2, 2]
Source Edit proc remove[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])
-
Removes n from L. Efficiency: O(1). This function assumes, for the sake of efficiency, that n is contained in L, otherwise the effects are undefined.
Example:
var a = initDoublyLinkedRing[int]() let n = newDoublyLinkedNode[int](5) a.add(n) assert 5 in a a.remove(n) assert 5 notin a
Source Edit proc remove[T](L: var SinglyLinkedList[T]; n: SinglyLinkedNode[T]): bool {. discardable.}
-
Removes a node n from L. Returns true if n was found in L. Efficiency: O(n); the list is traversed until n is found. Attempting to remove an element not contained in the list is a no-op. When the list is cyclic, the cycle is preserved after removal.
Example:
import std/[sequtils, enumerate, sugar] var a = [0, 1, 2].toSinglyLinkedList let n = a.head.next assert n.value == 1 assert a.remove(n) == true assert a.toSeq == [0, 2] assert a.remove(n) == false assert a.toSeq == [0, 2] a.addMoved(a) # cycle: [0, 2, 0, 2, ...] a.remove(a.head) let s = collect: for i, ai in enumerate(a): if i == 4: break ai assert s == [2, 2, 2, 2]
Source Edit func toDoublyLinkedList[T](elems: openArray[T]): DoublyLinkedList[T]
-
Creates a new DoublyLinkedList from the members of elems.
Example:
from std/sequtils import toSeq let a = [1, 2, 3, 4, 5].toDoublyLinkedList assert a.toSeq == [1, 2, 3, 4, 5]
Source Edit func toSinglyLinkedList[T](elems: openArray[T]): SinglyLinkedList[T]
-
Creates a new SinglyLinkedList from the members of elems.
Example:
from std/sequtils import toSeq let a = [1, 2, 3, 4, 5].toSinglyLinkedList assert a.toSeq == [1, 2, 3, 4, 5]
Source Edit
Iterators
iterator items[T](L: SomeLinkedList[T]): T
-
Yields every value of L.
See also:
Example:
from std/sugar import collect from std/sequtils import toSeq let a = collect(initSinglyLinkedList): for i in 1..3: 10 * i assert toSeq(items(a)) == toSeq(a) assert toSeq(a) == @[10, 20, 30]
Source Edit iterator items[T](L: SomeLinkedRing[T]): T
-
Yields every value of L.
See also:
Example:
from std/sugar import collect from std/sequtils import toSeq let a = collect(initSinglyLinkedRing): for i in 1..3: 10 * i assert toSeq(items(a)) == toSeq(a) assert toSeq(a) == @[10, 20, 30]
Source Edit iterator mitems[T](L: var SomeLinkedList[T]): var T
-
Yields every value of L so that you can modify it.
See also:
Example:
var a = initSinglyLinkedList[int]() for i in 1..5: a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in mitems(a): x = 5 * x - 1 assert $a == "[49, 99, 149, 199, 249]"
Source Edit iterator mitems[T](L: var SomeLinkedRing[T]): var T
-
Yields every value of L so that you can modify it.
See also:
Example:
var a = initSinglyLinkedRing[int]() for i in 1..5: a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in mitems(a): x = 5 * x - 1 assert $a == "[49, 99, 149, 199, 249]"
Source Edit 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.
See also:
Example:
var a = initDoublyLinkedList[int]() for i in 1..5: a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in nodes(a): if x.value == 30: a.remove(x) else: x.value = 5 * x.value - 1 assert $a == "[49, 99, 199, 249]"
Source Edit 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.
See also:
Example:
var a = initDoublyLinkedRing[int]() for i in 1..5: a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in nodes(a): if x.value == 30: a.remove(x) else: x.value = 5 * x.value - 1 assert $a == "[49, 99, 199, 249]"
Source Edit