Список — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вставка)
Строка 1: Строка 1:
Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]]. Вставка и удаление в списке работают за O(1).
+
Связный список - структура данных, состоящая из узлов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий узел списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]].  
  
 
__TOC__
 
__TOC__
Строка 15: Строка 15:
 
==Операции в связном списке==
 
==Операции в связном списке==
 
===Поиск===
 
===Поиск===
find(k)
+
find(k)
 
     {
 
     {
 
         x = head;
 
         x = head;
         while ((x->key != k)&&(x != NULL))
+
         while ((x.key != k)&&(x != NULL))
             x = x -> next;
+
             x = x.next;
 
         return x;
 
         return x;
 
     }
 
     }
Строка 26: Строка 26:
  
 
===Вставка===
 
===Вставка===
insert(k)
+
insert(k)
 
     {
 
     {
 
         tmp = head;
 
         tmp = head;
         x->key = k;
+
         x.key = k;
         x->next = tmp;
+
         x.next = tmp;
 
         head = x;
 
         head = x;
 
     }  
 
     }  
Строка 36: Строка 36:
  
 
===Удаление===
 
===Удаление===
delete(k)
+
delete(k)
 
     {
 
     {
 
         tmp = find(k);
 
         tmp = find(k);
Строка 42: Строка 42:
 
             {
 
             {
 
                 //освобождаем память  
 
                 //освобождаем память  
                 tmp = tmp->next;
+
                 tmp = tmp.next;
 
             }     
 
             }     
 
     }
 
     }

Версия 00:31, 4 мая 2011

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

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

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

Single linked list-1-.png

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

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

Doubly linked list.png

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

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

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

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

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

Операции в связном списке

Поиск

find(k)
   {
       x = head;
       while ((x.key != k)&&(x != NULL))
           x = x.next;
       return x;
   }

Поиск в худшем случае выполняется за [math]\Theta(n)[/math], так как может понадобиться просмотреть весь список.

Вставка

insert(k)
   {
        tmp = head;
        x.key = k;
        x.next = tmp;
        head = x;
   } 

Время работы вставки O(1).

Удаление

delete(k)
   {
       tmp = find(k);
       if (tmp != NULL)
           {
               //освобождаем память 
               tmp = tmp.next;
           }     
   }

Само удаление работает за O(1), но если требуется сначала найти удаляемый элемент, то на поиск + удаление потребуется [math]\Theta(n)[/math] времени.

См.также

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

Ссылки

http://en.wikipedia.org/wiki/Linked_list Linked list

Литература

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