Docs4dev
Docs
nim / latest / lists.html

std/lists

Source Edit

Implementation of:

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

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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

© 2006–2024 Andreas Rumpf
Licensed under the MIT License.
https://nim-lang.org/docs/lists.html