Список

Материал из Викиконспекты
Перейти к: навигация, поиск

Связный список — структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.

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

Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.

SimpleSpisok.png

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

Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.

TwiceSpisok.png

XOR-связный список

В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.

Циклический список

Первый элемент является следующим для последнего элемента списка.

CircleSpisok.png

Операции на списке

Рассмотрим базовые операции на примере односвязного списка.

Вставка

Очевиден случай, когда необходимо добавить элемент ([math]newHead[/math]) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.

insert(newHead)
    newHead.next = head;
    head = newHead; 
InsertHead.png

Если же на нужно вставить элемент ([math]thatElement[/math]) в определенную позицию после какого-то другого элемента ([math]thisElement[/math]), то просто изменим соответствующие ссылки.

insertAfter(thisElement, thatElement)
    thatElement.next = thisElement.next; 
    thisElement.next = thatElement;
InsertAfter.png

Поиск

Для того, чтобы найти элемент по значению ([math]value[/math]), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем [math]NULL[/math].

 Node Search(value)
   node = head
   while node != NULL and value != node.value
       node = node.next
   return node

Удаление

Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.

 function removeHead()
   if head != NULL
       tmp = head
       head = head.next
       delete tmp
RemoveHead.png

Удаление элемента после заданного ([math]thisElement[/math]) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.

 function removeAfter(thisElement)
   if thisElement.next != NULL
       tmp = thisElement.next
       thisElement.next = thisElement.next.next
       delete tmp
RemoveAfter.png

См.также

Массив с увеличением/уменьшением размера

Ссылки

Литература

  • Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 11.2
  • Д. Кнут: Искусство программирования том 1 глава 2.2