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
let

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
let

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

since

Types

A doubly linked list. Source   Edit
value*: T

A node of a doubly linked list.

It consists of a value field, and pointers to next and prev.

Source   Edit
A doubly linked ring. Source   Edit
A singly linked list. Source   Edit
value*: T

A node of a singly linked list.

It consists of a value field, and a pointer to next.

Source   Edit
A singly linked ring. Source   Edit

Procs

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

Appends a shallow copy of b to the end of a.

Example:

from std/sequtils import toSeq
var a = [1, 2, 3].toSinglyLinkedList
assert a.toSeq == [1, 2, 3, 4, 5]
assert b.toSeq == [4, 5]
assert a.toSeq == [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
Source   Edit

Appends (adds to the end) a node n to L. Efficiency: O(1).

Example:

assert a.contains(9)
Source   Edit

Appends (adds to the end) a value to L. Efficiency: O(1).

Example:

assert a.contains(9)
Source   Edit

Appends (adds to the end) a node n to L. Efficiency: O(1).

Example:

assert a.contains(9)
Source   Edit

Appends (adds to the end) a value to L. Efficiency: O(1).

Example:

assert a.contains(9)
Source   Edit

Appends (adds to the end) a node n to L. Efficiency: O(1).

Example:

assert a.contains(9)
Source   Edit

Appends (adds to the end) a value to L. Efficiency: O(1).

Example:

assert a.contains(9)
Source   Edit

Appends (adds to the end) a node n to L. Efficiency: O(1).

Example:

assert a.contains(9)
Source   Edit

Appends (adds to the end) a value to L. Efficiency: O(1).

Example:

assert a.contains(9)
Source   Edit

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.

Example:

import std/[sequtils, enumerate, sugar]
var
assert a.toSeq == [1, 2, 3, 4, 5]
assert b.toSeq == []
let s = collect:
for i, ci in enumerate(c):
if i == 6: break
ci
assert s == [0, 1, 0, 1, 0, 1]
Source   Edit

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.

Example:

import std/[sequtils, enumerate, sugar]
var
assert a.toSeq == [1, 2, 3, 4, 5]
assert b.toSeq == []
let s = collect:
for i, ci in enumerate(c):
if i == 6: break
ci
assert s == [0, 1, 0, 1, 0, 1]
Source   Edit

Source   Edit

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

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.

Example:

assert a.contains(9)
assert 8 in a
assert(not a.contains(1))
assert 2 notin a
Source   Edit
Creates a shallow copy of a.

Example:

from std/sequtils import toSeq
type Foo = ref object
x: int
var
f = Foo(x: 1)
let b = a.copy
assert a.toSeq == [f, f]
assert b.toSeq == [f] # b isn't modified...
f.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
Creates a shallow copy of a.

Example:

from std/sequtils import toSeq
type Foo = ref object
x: int
var
f = Foo(x: 1)
let b = a.copy
assert a.toSeq == [f, f]
assert b.toSeq == [f] # b isn't modified...
f.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

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

Example:

assert a.find(9).value == 9
assert a.find(1) == nil
Source   Edit

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:

Source   Edit

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:

Source   Edit

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:

Source   Edit

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:

Source   Edit
Creates a new doubly linked node with the given value.

Example:

assert n.value == 5
Source   Edit
Creates a new singly linked node with the given value.

Example:

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.

Example:

from std/sequtils import toSeq
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

Prepends (adds to the beginning) a node n to L. Efficiency: O(1).

Example:

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).

Example:

a.prepend(9)
a.prepend(8)
assert a.contains(9)
Source   Edit

Prepends (adds to the beginning) a node n to L. Efficiency: O(1).

Example:

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).

Example:

a.prepend(9)
a.prepend(8)
assert a.contains(9)
Source   Edit

Prepends (adds to the beginning) a node to L. Efficiency: O(1).

Example:

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).

Example:

a.prepend(9)
a.prepend(8)
assert a.contains(9)
Source   Edit

Prepends (adds to the beginning) a node n to L. Efficiency: O(1).

Example:

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).

Example:

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.

Example:

import std/[sequtils, enumerate, sugar]
var
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
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
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, ...]
let s = collect:
for i, ai in enumerate(a):
if i == 4: break
ai
assert s == [2, 2, 2, 2]
Source   Edit
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:

assert 5 in a
a.remove(n)
assert 5 notin a
Source   Edit
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
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, ...]
let s = collect:
for i, ai in enumerate(a):
if i == 4: break
ai
assert s == [2, 2, 2, 2]
Source   Edit
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
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

Yields every value of L.

Example:

from std/sugar import collect
from std/sequtils import toSeq
for i in 1..3: 10 * i
assert toSeq(items(a)) == toSeq(a)
assert toSeq(a) == @[10, 20, 30]
Source   Edit

Yields every value of L.

Example:

from std/sugar import collect
from std/sequtils import toSeq
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.

Example:

for i in 1..5:
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.

Example:

for i in 1..5:
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

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

Example:

for i in 1..5:
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

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

Example: