Spec-Zone.ru › Nim

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

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

Spec-Zone.ru

Настройки Оффлайн Что нового Помощь О нас
Spec-Zone .ru
спецификации, руководства, описания, API