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
関連
- deques module for double-ended queues
- sharedlist module for shared singly-linked lists
型
DoublyLinkedNodeObj[T] = object next*: (ref DoublyLinkedNodeObj[T]) prev*: 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.
ソース 編集 DoublyLinkedNode[T] = ref DoublyLinkedNodeObj[T]
- ソース 編集
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.
ソース 編集 SinglyLinkedNode[T] = ref SinglyLinkedNodeObj[T]
- ソース 編集
SinglyLinkedList[T] = object head*: (SinglyLinkedNode[T]) tail*: SinglyLinkedNode[T]
-
A singly linked list.
Use initSinglyLinkedList proc to create a new empty list.
ソース 編集 DoublyLinkedList[T] = object head*: (DoublyLinkedNode[T]) tail*: DoublyLinkedNode[T]
-
A doubly linked list.
Use initDoublyLinkedList proc to create a new empty list.
ソース 編集 SinglyLinkedRing[T] = object head*: (SinglyLinkedNode[T]) tail*: SinglyLinkedNode[T]
-
A singly linked ring.
Use initSinglyLinkedRing proc to create a new empty ring.
ソース 編集 DoublyLinkedRing[T] = object head*: DoublyLinkedNode[T]
-
A doubly linked ring.
Use initDoublyLinkedRing proc to create a new empty ring.
ソース 編集 SomeLinkedList[T] = SinglyLinkedList[T] | DoublyLinkedList[T]
- ソース 編集
SomeLinkedRing[T] = SinglyLinkedRing[T] | DoublyLinkedRing[T]
- ソース 編集
SomeLinkedCollection[T] = SomeLinkedList[T] | SomeLinkedRing[T]
- ソース 編集
SomeLinkedNode[T] = SinglyLinkedNode[T] | DoublyLinkedNode[T]
- ソース 編集
プロシージャ
proc initSinglyLinkedList[T](): SinglyLinkedList[T]
-
Creates a new singly linked list that is empty.
用例:
var a = initSinglyLinkedList[int]()
ソース 編集 proc initDoublyLinkedList[T](): DoublyLinkedList[T]
-
Creates a new doubly linked list that is empty.
用例:
var a = initDoublyLinkedList[int]()
ソース 編集 proc initSinglyLinkedRing[T](): SinglyLinkedRing[T]
-
Creates a new singly linked ring that is empty.
用例:
var a = initSinglyLinkedRing[int]()
ソース 編集 proc initDoublyLinkedRing[T](): DoublyLinkedRing[T]
-
Creates a new doubly linked ring that is empty.
用例:
var a = initDoublyLinkedRing[int]()
ソース 編集 proc newDoublyLinkedNode[T](value: T): (DoublyLinkedNode[T])
-
Creates a new doubly linked node with the given value.
用例:
var n = newDoublyLinkedNode[int](5) assert n.value == 5
ソース 編集 proc newSinglyLinkedNode[T](value: T): (SinglyLinkedNode[T])
-
Creates a new singly linked node with the given value.
用例:
var n = newSinglyLinkedNode[int](5) assert n.value == 5
ソース 編集 proc `$`[T](L: SomeLinkedCollection[T]): string
- Turns a list into its string representation for logging and printing. ソース 編集
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.
関連:
用例:
var a = initSinglyLinkedList[int]() a.append(9) a.append(8) assert a.find(9).value == 9 assert a.find(1) == nil
ソース 編集 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.
関連:
用例:
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
ソース 編集 proc append[T](L: var SinglyLinkedList[T]; n: SinglyLinkedNode[T]) {...}{.inline.}
-
Appends (adds to the end) a node n to L. Efficiency: O(1).
関連:
- append proc for appending a value
- prepend proc for prepending a node
- prepend proc for prepending a value
用例:
var a = initSinglyLinkedList[int]() n = newSinglyLinkedNode[int](9) a.append(n) assert a.contains(9)
ソース 編集 proc append[T](L: var SinglyLinkedList[T]; value: T) {...}{.inline.}
-
Appends (adds to the end) a value to L. Efficiency: O(1).
関連:
- append proc for appending a value
- prepend proc for prepending a node
- prepend proc for prepending a value
用例:
var a = initSinglyLinkedList[int]() a.append(9) a.append(8) assert a.contains(9)
ソース 編集 proc prepend[T](L: var SinglyLinkedList[T]; n: SinglyLinkedNode[T]) {...}{.inline.}
-
Prepends (adds to the beginning) a node to L. Efficiency: O(1).
関連:
- append proc for appending a node
- append proc for appending a value
- prepend proc for prepending a value
用例:
var a = initSinglyLinkedList[int]() n = newSinglyLinkedNode[int](9) a.prepend(n) assert a.contains(9)
ソース 編集 proc prepend[T](L: var SinglyLinkedList[T]; value: T) {...}{.inline.}
-
Prepends (adds to the beginning) a node to L. Efficiency: O(1).
関連:
- append proc for appending a node
- append proc for appending a value
- prepend proc for prepending a node
用例:
var a = initSinglyLinkedList[int]() a.prepend(9) a.prepend(8) assert a.contains(9)
ソース 編集 proc append[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])
-
Appends (adds to the end) a node n to L. Efficiency: O(1).
関連:
- append proc for appending a value
- prepend proc for prepending a node
- prepend proc for prepending a value
- remove proc for removing a node
用例:
var a = initDoublyLinkedList[int]() n = newDoublyLinkedNode[int](9) a.append(n) assert a.contains(9)
ソース 編集 proc append[T](L: var DoublyLinkedList[T]; value: T)
-
Appends (adds to the end) a value to L. Efficiency: O(1).
関連:
- append proc for appending a node
- prepend proc for prepending a node
- prepend proc for prepending a value
- remove proc for removing a node
用例:
var a = initDoublyLinkedList[int]() a.append(9) a.append(8) assert a.contains(9)
ソース 編集 proc prepend[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])
-
Prepends (adds to the beginning) a node n to L. Efficiency: O(1).
関連:
- append proc for appending a node
- append proc for appending a value
- prepend proc for prepending a value
- remove proc for removing a node
用例:
var a = initDoublyLinkedList[int]() n = newDoublyLinkedNode[int](9) a.prepend(n) assert a.contains(9)
ソース 編集 proc prepend[T](L: var DoublyLinkedList[T]; value: T)
-
Prepends (adds to the beginning) a value to L. Efficiency: O(1).
関連:
- append proc for appending a node
- append proc for appending a value
- prepend proc for prepending a node
- remove proc for removing a node
用例:
var a = initDoublyLinkedList[int]() a.prepend(9) a.prepend(8) assert a.contains(9)
ソース 編集 proc remove[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])
-
Removes a node n from L. Efficiency: O(1).
用例:
var a = initDoublyLinkedList[int]() n = newDoublyLinkedNode[int](5) a.append(n) assert 5 in a a.remove(n) assert 5 notin a
ソース 編集 proc append[T](L: var SinglyLinkedRing[T]; n: SinglyLinkedNode[T])
-
Appends (adds to the end) a node n to L. Efficiency: O(1).
関連:
- append proc for appending a value
- prepend proc for prepending a node
- prepend proc for prepending a value
用例:
var a = initSinglyLinkedRing[int]() n = newSinglyLinkedNode[int](9) a.append(n) assert a.contains(9)
ソース 編集 proc append[T](L: var SinglyLinkedRing[T]; value: T)
-
Appends (adds to the end) a value to L. Efficiency: O(1).
関連:
- append proc for appending a node
- prepend proc for prepending a node
- prepend proc for prepending a value
用例:
var a = initSinglyLinkedRing[int]() a.append(9) a.append(8) assert a.contains(9)
ソース 編集 proc prepend[T](L: var SinglyLinkedRing[T]; n: SinglyLinkedNode[T])
-
Prepends (adds to the beginning) a node n to L. Efficiency: O(1).
関連:
- append proc for appending a node
- append proc for appending a value
- prepend proc for prepending a value
用例:
var a = initSinglyLinkedRing[int]() n = newSinglyLinkedNode[int](9) a.prepend(n) assert a.contains(9)
ソース 編集 proc prepend[T](L: var SinglyLinkedRing[T]; value: T)
-
Prepends (adds to the beginning) a value to L. Efficiency: O(1).
関連:
- append proc for appending a node
- append proc for appending a value
- prepend proc for prepending a node
用例:
var a = initSinglyLinkedRing[int]() a.prepend(9) a.prepend(8) assert a.contains(9)
ソース 編集 proc append[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])
-
Appends (adds to the end) a node n to L. Efficiency: O(1).
関連:
- append proc for appending a value
- prepend proc for prepending a node
- prepend proc for prepending a value
- remove proc for removing a node
用例:
var a = initDoublyLinkedRing[int]() n = newDoublyLinkedNode[int](9) a.append(n) assert a.contains(9)
ソース 編集 proc append[T](L: var DoublyLinkedRing[T]; value: T)
-
Appends (adds to the end) a value to L. Efficiency: O(1).
関連:
- append proc for appending a node
- prepend proc for prepending a node
- prepend proc for prepending a value
- remove proc for removing a node
用例:
var a = initDoublyLinkedRing[int]() a.append(9) a.append(8) assert a.contains(9)
ソース 編集 proc prepend[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])
-
Prepends (adds to the beginning) a node n to L. Efficiency: O(1).
関連:
- append proc for appending a node
- append proc for appending a value
- prepend proc for prepending a value
- remove proc for removing a node
用例:
var a = initDoublyLinkedRing[int]() n = newDoublyLinkedNode[int](9) a.prepend(n) assert a.contains(9)
ソース 編集 proc prepend[T](L: var DoublyLinkedRing[T]; value: T)
-
Prepends (adds to the beginning) a value to L. Efficiency: O(1).
関連:
- append proc for appending a node
- append proc for appending a value
- prepend proc for prepending a node
- remove proc for removing a node
用例:
var a = initDoublyLinkedRing[int]() a.prepend(9) a.prepend(8) assert a.contains(9)
ソース 編集 proc remove[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])
-
Removes n from L. Efficiency: O(1).
用例:
var a = initDoublyLinkedRing[int]() n = newDoublyLinkedNode[int](5) a.append(n) assert 5 in a a.remove(n) assert 5 notin a
ソース 編集
イテレータ
iterator items[T](L: SomeLinkedList[T]): T
-
Yields every value of L.
関連:
用例:
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
ソース 編集 iterator items[T](L: SomeLinkedRing[T]): T
-
Yields every value of L.
関連:
用例:
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
ソース 編集 iterator mitems[T](L: var SomeLinkedList[T]): var T
-
Yields every value of L so that you can modify it.
関連:
用例:
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]"
ソース 編集 iterator mitems[T](L: var SomeLinkedRing[T]): var T
-
Yields every value of L so that you can modify it.
関連:
用例:
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]"
ソース 編集 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.
関連:
用例:
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]"
ソース 編集 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.
関連:
用例:
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]"
ソース 編集