Spec-Zone.ru › Nim 1

списки

Реализация:

  • односвязных списков
  • двусвязных списков
  • односвязных колец (циклические списки)
  • двусвязных колец (циклические списки)

Основное использование

Поскольку это не имеет смысла делать иначе, указатели next и prev не скрыты от вас и могут быть напрямую использованы для повышения эффективности.

Списки

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

Кольца

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

См. также

  • модуль деков для очередей с двумя концами
  • модуль sharedlist для общих односвязных списков

Типы

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

Узел, из которого состоит двусвязный список.

Он состоит из поля value и указателей на next и prev.

Исходный код Изменить 
DoublyLinkedNode[T] = ref DoublyLinkedNodeObj[T]
Исходный код Изменить 
SinglyLinkedNodeObj[T] = object
  next*: (ref SinglyLinkedNodeObj[T])
  value*: T

Узел, из которого состоит односвязный список.

Он состоит из поля value и указателя на next.

Исходный код Изменить 
SinglyLinkedNode[T] = ref SinglyLinkedNodeObj[T]
Исходный код Изменить 
SinglyLinkedList[T] = object
  head*: (SinglyLinkedNode[T])
  tail* {...}{.cursor.}: SinglyLinkedNode[T]

Односвязный список.

Используйте процедуру initSinglyLinkedList, чтобы создать новый пустой список.

Исходный код Изменить 
DoublyLinkedList[T] = object
  head*: (DoublyLinkedNode[T])
  tail* {...}{.cursor.}: DoublyLinkedNode[T]

Двусвязный список.

Используйте процедуру initDoublyLinkedList, чтобы создать новый пустой список.

Исходный код Изменить 
SinglyLinkedRing[T] = object
  head*: (SinglyLinkedNode[T])
  tail* {...}{.cursor.}: SinglyLinkedNode[T]

Односвязное кольцо.

Используйте процедуру initSinglyLinkedRing, чтобы создать новое пустое кольцо.

Исходный код Изменить 
DoublyLinkedRing[T] = object
  head*: DoublyLinkedNode[T]

Двусвязное кольцо.

Используйте процедуру initDoublyLinkedRing, чтобы создать новое пустое кольцо.

Исходный код Изменить 
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]
Создаёт новый односвязный список, который пуст.

Пример:

var a = initSinglyLinkedList[int]()
Исходный код Редактировать 
proc initDoublyLinkedList[T](): DoublyLinkedList[T]
Создаёт новый двусвязный список, который пуст.

Пример:

var a = initDoublyLinkedList[int]()
Исходный код Редактировать 
proc initSinglyLinkedRing[T](): SinglyLinkedRing[T]
Создаёт новое односвязное кольцо, которое пусто.

Пример:

var a = initSinglyLinkedRing[int]()
Исходный код Редактировать 
proc initDoublyLinkedRing[T](): DoublyLinkedRing[T]
Создаёт новое двусвязное кольцо, которое пусто.

Пример:

var a = initDoublyLinkedRing[int]()
Исходный код Редактировать 
proc newDoublyLinkedNode[T](value: T): (DoublyLinkedNode[T])
Создаёт новый двусвязный узел с заданным value.

Пример:

var n = newDoublyLinkedNode[int](5)
assert n.value == 5
Исходный код Редактировать 
proc newSinglyLinkedNode[T](value: T): (SinglyLinkedNode[T])
Создаёт новый односвязный узел с заданным value.

Пример:

var n = newSinglyLinkedNode[int](5)
assert n.value == 5
Исходный код Редактировать 
proc `$`[T](L: SomeLinkedCollection[T]): string
Преобразует список в его строковое представление для регистрации и вывода. Исходный код Редактировать 
proc find[T](L: SomeLinkedCollection[T]; value: T): SomeLinkedNode[T]

Ищет значение в списке. Возвращает nil если значение не найдено.

См. также:

  • contains proc

Пример:

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

Ищет значение в списке. Возвращает false если значение не найдено, true в противном случае.

См. также:

  • find proc

Пример:

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

Добавляет (добавляет в конец) узел n к L. Эффективность: O(1).

См. также:

  • append proc для добавления значения
  • prepend proc для добавления узла в начало
  • prepend proc для добавления значения в начало

Пример:

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

Добавляет (добавляет в конец) значение к L. Эффективность: O(1).

См. также:

  • append proc для добавления значения
  • prepend proc для добавления узла в начало
  • prepend proc для добавления значения в начало

Пример:

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

Добавляет в начало (добавляет в начало) узел к L. Эффективность: O(1).

См. также:

  • append proc для добавления узла в конец
  • append proc для добавления значения в конец
  • prepend proc для добавления значения в начало

Пример:

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

Добавляет в начало (добавляет в начало) узел L к 

var a = initSinglyLinkedList[int]()
a.prepend(9)
a.prepend(8)
assert a.contains(9)
. Эффективность: O(1).

См. также:

  • append proc для добавления узла в конец
  • append proc для добавления значения в конец
  • prepend proc для добавления узла в начало

Пример:

var a = initSinglyLinkedList[int]()
a.prepend(9)
a.prepend(8)
assert a.contains(9)
Исходный код Редактировать 
proc append[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])

Добавляет (добавляет в конец) узел n к L. Эффективность: O(1).

См. также:

  • append proc для добавления значения
  • prepend proc для добавления узла в начало
  • prepend proc для добавления значения в начало
  • remove proc для удаления узла

Пример:

var
  a = initDoublyLinkedList[int]()
  n = newDoublyLinkedNode[int](9)
a.append(n)
assert a.contains(9)
Исходный код Редактировать 
proc append[T](L: var DoublyLinkedList[T]; value: T)

Добавляет (добавляет в конец) значение к L. Эффективность: O(1).

См. также:

  • append proc для добавления узла
  • prepend proc для добавления узла в начало
  • prepend proc для добавления значения в начало
  • remove proc для удаления узла

Пример:

var a = initDoublyLinkedList[int]()
a.append(9)
a.append(8)
assert a.contains(9)
Исходный код Редактировать 
proc prepend[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])

Добавляет в начало (добавляет в начало) узел n к L. Эффективность: O(1).

См. также:

  • append proc для добавления узла в конец
  • append proc для добавления значения в конец
  • prepend proc для добавления значения в начало
  • remove proc для удаления узла

Пример:

var
  a = initDoublyLinkedList[int]()
  n = newDoublyLinkedNode[int](9)
a.prepend(n)
assert a.contains(9)
Исходный код Редактировать 
proc prepend[T](L: var DoublyLinkedList[T]; value: T)

Добавляет в начало (добавляет в начало) значение к L. Эффективность: O(1).

См. также:

  • append proc для добавления узла в конец
  • append proc для добавления значения в конец
  • prepend proc для добавления узла в начало
  • remove proc для удаления узла

Пример:

var a = initDoublyLinkedList[int]()
a.prepend(9)
a.prepend(8)
assert a.contains(9)
Исходный код Редактировать 
proc remove[T](L: var DoublyLinkedList[T]; n: DoublyLinkedNode[T])
Удаляет узел n из L. Эффективность: 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])

Добавляет (добавляет в конец) узел n в L. Эффективность: O(1).

См. также:

  • процедура добавления значения для добавления значения
  • процедура добавления в начало для добавления узла в начало
  • процедура добавления в начало для добавления значения в начало

Пример:

var
  a = initSinglyLinkedRing[int]()
  n = newSinglyLinkedNode[int](9)
a.append(n)
assert a.contains(9)
Исходный код Изменить 
proc append[T](L: var SinglyLinkedRing[T]; value: T)

Добавляет (добавляет в конец) значение в L. Эффективность: O(1).

См. также:

  • процедура добавления узла для добавления узла
  • процедура добавления в начало для добавления узла в начало
  • процедура добавления в начало для добавления значения в начало

Пример:

var a = initSinglyLinkedRing[int]()
a.append(9)
a.append(8)
assert a.contains(9)
Исходный код Изменить 
proc prepend[T](L: var SinglyLinkedRing[T]; n: SinglyLinkedNode[T])

Добавляет в начало узел n в L. Эффективность: O(1).

См. также:

  • процедура добавления узла для добавления узла
  • процедура добавления значения для добавления значения
  • процедура добавления в начало для добавления значения в начало

Пример:

var
  a = initSinglyLinkedRing[int]()
  n = newSinglyLinkedNode[int](9)
a.prepend(n)
assert a.contains(9)
Исходный код Изменить 
proc prepend[T](L: var SinglyLinkedRing[T]; value: T)

Добавляет в начало значение в L. Эффективность: O(1).

См. также:

  • процедура добавления узла для добавления узла
  • процедура добавления значения для добавления значения
  • процедура добавления в начало для добавления узла в начало

Пример:

var a = initSinglyLinkedRing[int]()
a.prepend(9)
a.prepend(8)
assert a.contains(9)
Исходный код Изменить 
proc append[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])

Добавляет (добавляет в конец) узел n в L. Эффективность: O(1).

См. также:

  • процедура добавления значения для добавления значения
  • процедура добавления в начало для добавления узла в начало
  • процедура добавления в начало для добавления значения в начало
  • процедура удаления узла для удаления узла

Пример:

var
  a = initDoublyLinkedRing[int]()
  n = newDoublyLinkedNode[int](9)
a.append(n)
assert a.contains(9)
Исходный код Изменить 
proc append[T](L: var DoublyLinkedRing[T]; value: T)

Добавляет (добавляет в конец) значение в L. Эффективность: O(1).

См. также:

  • процедура добавления узла для добавления узла
  • процедура добавления в начало для добавления узла в начало
  • процедура добавления в начало для добавления значения в начало
  • процедура удаления узла для удаления узла

Пример:

var a = initDoublyLinkedRing[int]()
a.append(9)
a.append(8)
assert a.contains(9)
Исходный код Изменить 
proc prepend[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])

Добавляет в начало узел n в L. Эффективность: O(1).

См. также:

  • процедура добавления узла для добавления узла
  • процедура добавления значения для добавления значения
  • процедура добавления в начало для добавления значения в начало
  • процедура удаления узла для удаления узла

Пример:

var
  a = initDoublyLinkedRing[int]()
  n = newDoublyLinkedNode[int](9)
a.prepend(n)
assert a.contains(9)
Исходный код Изменить 
proc prepend[T](L: var DoublyLinkedRing[T]; value: T)

Добавляет в начало значение в L. Эффективность: O(1).

См. также:

  • процедура добавления узла для добавления узла
  • процедура добавления значения для добавления значения
  • процедура добавления в начало для добавления узла в начало
  • процедура удаления узла для удаления узла

Пример:

var a = initDoublyLinkedRing[int]()
a.prepend(9)
a.prepend(8)
assert a.contains(9)
Исходный код Изменить 
proc remove[T](L: var DoublyLinkedRing[T]; n: DoublyLinkedNode[T])
Удаляет n из L. Эффективность: 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

Возвращает каждое значение L.

См. также:

  • итератор mitems
  • итератор nodes

Примеры:

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

Возвращает каждое значение L.

См. также:

  • итератор mitems
  • итератор nodes

Примеры:

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

Возвращает каждое значение L, позволяя его изменить.

См. также:

  • итератор items
  • итератор nodes

Пример:

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

Возвращает каждое значение L, позволяя его изменить.

См. также:

  • итератор items
  • итератор nodes

Пример:

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]

Итерируется по каждому узлу x. Поддерживается удаление текущего узла из списка во время обхода.

См. также:

  • итератор items
  • итератор mitems

Пример:

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]

Итерируется по каждому узлу x. Поддерживается удаление текущего узла из списка во время обхода.

См. также:

  • итератор items
  • итератор mitems

Пример:

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]"
Исходный код Изменить

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

Spec-Zone.ru

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