std/lists

Source Edit

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

Imports

since

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:

• add proc
• add proc
• add proc

Source Edit

proc append[T](a: var (SinglyLinkedList[T] | SinglyLinkedRing[T]);
               b: SinglyLinkedList[T] | SinglyLinkedNode[T] | T)

Alias for a.add(b).

See also:

• add proc
• add proc
• add proc

Source Edit

proc appendMoved[T: SomeLinkedList](a, b: var T)

Alias for a.addMoved(b).

See also:

• addMoved proc
• addMoved proc

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:

• find proc

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:

• contains proc

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 toDoublyLinkedRing[T](elems: openArray[T]): DoublyLinkedRing[T]

Creates a new DoublyLinkedRing from the members of elems.

Example:

from std/sequtils import toSeq
let a = [1, 2, 3, 4, 5].toDoublyLinkedRing
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

func toSinglyLinkedRing[T](elems: openArray[T]): SinglyLinkedRing[T]

Creates a new SinglyLinkedRing from the members of elems.

Example:

from std/sequtils import toSeq
let a = [1, 2, 3, 4, 5].toSinglyLinkedRing
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:

• mitems iterator
• nodes iterator

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:

• mitems iterator
• nodes iterator

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:

• items iterator
• nodes iterator

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:

• items iterator
• nodes iterator

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:

• items iterator
• mitems iterator

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:

• items iterator
• mitems iterator

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