Spec-Zone.ru › Nim 1

lists

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

import lists

var
  l = initDoublyLinkedList[int]()
  a = newDoublyLinkedNode[int](3)
  b = newDoublyLinkedNode[int](7)
  c = newDoublyLinkedNode[int](9)

l.append(a)
l.append(b)
l.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

import lists

var
  l = initSinglyLinkedRing[int]()
  a = newSinglyLinkedNode[int](3)
  b = newSinglyLinkedNode[int](7)
  c = newSinglyLinkedNode[int](9)

l.append(a)
l.append(b)
l.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

DoublyLinkedNodeObj[T] = object
  next*: (ref DoublyLinkedNodeObj[T])
  prev* {...}{.cursor.}: ref DoublyLinkedNodeObj[T]
  value*: T

A node a doubly linked list consists of.

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

Source Edit 
DoublyLinkedNode[T] = ref DoublyLinkedNodeObj[T]
Source Edit 
SinglyLinkedNodeObj[T] = object
  next*: (ref SinglyLinkedNodeObj[T])
  value*: T

A node a singly linked list consists of.

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

Source Edit 
SinglyLinkedNode[T] = ref SinglyLinkedNodeObj[T]
Source Edit 
SinglyLinkedList[T] = object
  head*: (SinglyLinkedNode[T])
  tail* {...}{.cursor.}: SinglyLinkedNode[T]

A singly linked list.

Use initSinglyLinkedList proc to create a new empty list.

Source Edit 
DoublyLinkedList[T] = object
  head*: (DoublyLinkedNode[T])
  tail* {...}{.cursor.}: DoublyLinkedNode[T]

A doubly linked list.

Use initDoublyLinkedList proc to create a new empty list.

Source Edit 
SinglyLinkedRing[T] = object
  head*: (SinglyLinkedNode[T])
  tail* {...}{.cursor.}: SinglyLinkedNode[T]

A singly linked ring.

Use initSinglyLinkedRing proc to create a new empty ring.

Source Edit 
DoublyLinkedRing[T] = object
  head*: DoublyLinkedNode[T]

A doubly linked ring.

Use initDoublyLinkedRing proc to create a new empty ring.

Source Edit 
SomeLinkedList[T] = SinglyLinkedList[T] | DoublyLinkedList[T]
Source Edit 
SomeLinkedRing[T] = SinglyLinkedRing[T] | DoublyLinkedRing[T]
Source Edit 
SomeLinkedCollection[T] = SomeLinkedList[T] | SomeLinkedRing[T]
Source Edit 
SomeLinkedNode[T] = SinglyLinkedNode[T] | DoublyLinkedNode[T]
Source Edit

Procs

proc initSinglyLinkedList[T](): SinglyLinkedList[T]
Creates a new singly linked list that is empty.

Example:

var a = initSinglyLinkedList[int]()
Source Edit 
proc initDoublyLinkedList[T](): DoublyLinkedList[T]
Creates a new doubly linked list that is empty.

Example:

var a = initDoublyLinkedList[int]()
Source Edit 
proc initSinglyLinkedRing[T](): SinglyLinkedRing[T]
Creates a new singly linked ring that is empty.

Example:

var a = initSinglyLinkedRing[int]()
Source Edit 
proc initDoublyLinkedRing[T](): DoublyLinkedRing[T]
Creates a new doubly linked ring that is empty.

Example:

var a = initDoublyLinkedRing[int]()
Source Edit 
proc newDoublyLinkedNode[T](value: T): (DoublyLinkedNode[T])
Creates a new doubly linked node with the given value.

Example:

var 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:

var n = newSinglyLinkedNode[int](5)
assert n.value == 5
Source Edit 
proc `$`[T](L: SomeLinkedCollection[T]): string
Turns a list into its string representation for logging and printing. 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:

var a = initSinglyLinkedList[int]()
a.append(9)
a.append(8)
assert a.find(9).value == 9
assert a.find(1) == nil
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.

See also:

  • find proc

Example:

var a = initSinglyLinkedList[int]()
a.append(9)
a.append(8)
assert a.contains(9)
assert 8 in a
assert(not a.contains(1))
assert 2 notin a
Source Edit 
proc append[T](L: var SinglyLinkedList[T]; n: SinglyLinkedNode[T]) {...}{.inline.}

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

See also:

  • append proc for appending a value
  • prepend proc for prepending a node
  • prepend proc for prepending a value

Example:

var
  a = initSinglyLinkedList[int]()
  n = newSinglyLinkedNode[int](9)
a.append(n)
assert a.contains(9)
Source Edit 
proc append[T](L: var SinglyLinkedList[T]; value: T) {...}{.inline.}

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

See also:

  • append proc for appending a value
  • prepend proc for prepending a node
  • prepend proc for prepending a value

Example:

var a = initSinglyLinkedList[int]()
a.append(9)
a.append(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:

  • append proc for appending a node
  • append proc for appending a value
  • prepend proc for prepending a value

Example:

var
  a = initSinglyLinkedList[int]()
  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:

  • append proc for appending a node
  • append 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 append[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])

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

See also:

  • append 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]()
  n = newDoublyLinkedNode[int](9)
a.append(n)
assert a.contains(9)
Source Edit 
proc append[T](L: var DoublyLinkedList[T]; value: T)

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

See also:

  • append 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.append(9)
a.append(8)
assert a.contains(9)
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:

  • append proc for appending a node
  • append proc for appending a value
  • prepend proc for prepending a value
  • remove proc for removing a node

Example:

var
  a = initDoublyLinkedList[int]()
  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:

  • append proc for appending a node
  • append 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 remove[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])
Removes a node n from L. Efficiency: O(1).

Example:

var
  a = initDoublyLinkedList[int]()
  n = newDoublyLinkedNode[int](5)
a.append(n)
assert 5 in a
a.remove(n)
assert 5 notin a
Source Edit 
proc append[T](L: var SinglyLinkedRing[T]; n: SinglyLinkedNode[T])

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

See also:

  • append proc for appending a value
  • prepend proc for prepending a node
  • prepend proc for prepending a value

Example:

var
  a = initSinglyLinkedRing[int]()
  n = newSinglyLinkedNode[int](9)
a.append(n)
assert a.contains(9)
Source Edit 
proc append[T](L: var SinglyLinkedRing[T]; value: T)

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

See also:

  • append proc for appending a node
  • prepend proc for prepending a node
  • prepend proc for prepending a value

Example:

var a = initSinglyLinkedRing[int]()
a.append(9)
a.append(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:

  • append proc for appending a node
  • append proc for appending a value
  • prepend proc for prepending a value

Example:

var
  a = initSinglyLinkedRing[int]()
  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:

  • append proc for appending a node
  • append 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 append[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])

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

See also:

  • append 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]()
  n = newDoublyLinkedNode[int](9)
a.append(n)
assert a.contains(9)
Source Edit 
proc append[T](L: var DoublyLinkedRing[T]; value: T)

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

See also:

  • append 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.append(9)
a.append(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:

  • append proc for appending a node
  • append proc for appending a value
  • prepend proc for prepending a value
  • remove proc for removing a node

Example:

var
  a = initDoublyLinkedRing[int]()
  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:

  • append proc for appending a node
  • append 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 remove[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])
Removes n from L. Efficiency: O(1).

Example:

var
  a = initDoublyLinkedRing[int]()
  n = newDoublyLinkedNode[int](5)
a.append(n)
assert 5 in a
a.remove(n)
assert 5 notin a
Source Edit

Iterators

iterator items[T](L: SomeLinkedList[T]): T

Yields every value of L.

See also:

  • mitems iterator
  • nodes iterator

Examples:

var a = initSinglyLinkedList[int]()
for i in 1 .. 3:
  a.append(10*i)

for x in a:  # the same as: for x in items(a):
  echo x

# 10
# 20
# 30
Source Edit 
iterator items[T](L: SomeLinkedRing[T]): T

Yields every value of L.

See also:

  • mitems iterator
  • nodes iterator

Examples:

var a = initSinglyLinkedRing[int]()
for i in 1 .. 3:
  a.append(10*i)

for x in a:  # the same as: for x in items(a):
  echo x

# 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.append(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.append(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.append(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.append(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–2021 Andreas Rumpf
Licensed under the MIT License.
https://nim-lang.org/docs/lists.html

Spec-Zone.ru

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