Список

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

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

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

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

Single linked list-1-.png

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

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

Doubly linked list.png

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

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

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

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

Circurlar linked list.png (872×241).png

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

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

Вставка

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

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

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

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

Поиск

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

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

Удаление

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

removeHead()//удаление головы
    if head != NULL
        tmp = head;
        head = head.next;
        delete tmp;

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

removeAfter(thisElement)
    if thisElement.next != NULL
        tmp = thisElement.next;
        thisElement.next = thisElement.next.next;
        delete tmp;

См.также

Ссылки

Литература

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