Линейный список представляет последовательность из n>0 узлов x[1], x[2], ... ,x[n], важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, как будто они находятся на одной линии. Иначе говоря, в такой структуре следует соблюдать условие: если n>0 и x[1] является первым узлом, а x[n] – последним, то k-тый узел x[k] следует за x[k-1] узлом и перед x[k+1] узлом для любого k лежащего в промежутке от 1 до n.

С линейными списками могут выполняться следующие операции:
  1. получение доступа к x[k] элементу списка для проверки и/или изменения содержания его полей.
  2. вставка нового узла сразу до или после x[k] узла.
  3. удаление x[k] узла.
  4. объединение в один список двух или более линейных списков.
  5. разбиение линейного списка на два и более списка.
  6. создание копии линейного списка.
  7. определение количества узлов с списке.
  8. сортировка узлов в порядке возрастания значений в определенных полях этих узлов.
  9. поиск узла с заданным значением некоторого поля.

Линейные списки, в которых операции вставки, удаления и операции доступа к значению чаще всего выполняются в первом и последнем узле получили специальное название: стек – линейный список, в котором операции вставки и удаления (и как правило доступа к данным) выполняются только на одном из концов списка; очередь (односторонняя очередь) – линейный список, в котором все операции вставки выполняются на одном конце списка, а все операции удаления (и доступа, как правило) – на другом; дек (двухсторонняя очередь) – линейный список, в котором все операции вставки, удаления и доступа выполняются с обоих концов. Различают дек с ограниченным вводом и ограниченным выводом, в котором операция удаления и вставки элементов соответственно выполняется только на одном из концов.


Программирование связных списков в C++.

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

struct node{Item item; node *next;};
typedef node* Link;

Соответственно узлы в связном списке ссылаются на узлы и поэтому связный список называется самоссылочным.
Простые линейные списки можно рассматривать как последовательность , в которой принято одно из следующих соглашений для ссылки последнего узла, а именно:
  1. пустая (NULL) ссылка, не указывает ни на какой узел
  2. ссылка, которая указывает на фиктивный узел, который не содержит элемента
  3. ссылка, которая указывает на первый узел, делает список циклическим

В каждом случае отслеживание ссылок от первого элемента до последнего формирует последовательность расположения элементов.
При программировании связных списков как только возникает необходимость использовать новый узел в списке для него необходимо резервировать память.
При объявлении переменной типа node для нее резервируется память во время компиляции. Однако часто приходится организовывать вычисления, связанные с резервирование памяти во время выполнения посредством вызовов системных операторов управления памятью.

Пример 1
link x = new node;

Struct node
{
Item item; 
node *next;
node (Item x; node *t)

iteam = x;

next = t;
};
link t = new(x,t);
 

Если хотим удалить элемент
 
t = x -> next;
x -> next = t -> next;
или
x -> next = x -> next;
x -> next = t;

Если хотим добавить элемент
 
t->next = x -> next;
t ->next = t;

Пример 2
Пример циклического списка (задача Иосифа).

Struct node
{
Item item; 
node *next;
node (Item x; node *t)

item = x;

next = t;
};

typedef node *link;

int main(int argc; char *argv[])
{
int i;
N = atoi(argv[1]);
M = atoi(argv[2]);

link t = new node(1,1);
t -> next = t;
link x = t;

for(i=2; i<=N; i++)

x=(x -> next = new node a,t);
while(x! = x -> next)
{
for(i=1; i<N; i++)
x = x -> next;


x -> next + x -> next -> next;
}
cout << x -> item << endl;
}
}
N=9 M=5
517436928
Соглашение о ведущем и завершающем узлах связных списков.

Список циклический (не бывает пустым)
Таблица 1    
ОперацияРеализация
вставка t после it -> next = x -> next;
удаление после xx-> next = t; x -> next = x -> next -> next;
цикл обходаt = head; do {...t= t -> next;} while(t!= head)
проверка на наличие минимум одного элементаif (head -> next == head)


Ведущий указатель, Null – указатель завершающего узла.
Таблица 2    
инициализацияhead = 0
вставка f после xif ( x==0 || head = t) head -> next =0 else { t -> next = x -> next; x -> next =t; }
удаление после xt = x -> next; x -> next = t -> next;
цикл обходаfor( t= head; t!=; t = t -> next) ...
проверка на пустотуif(head == 0)


Фиктивный ведущий узел, Null – указатель завершающего узла
Таблица 3    
инициализацияhead = new node; head -> next =0;
вставка t после xt -> next = x -> next; x -> next = t;
удаление после xt = x -> next; x -> next = t -> next;
цикл обходаfor( t = head ->next; t!0; t = t-> next)
проверка на пустотуif( head -> next == 0)


Фиктивный ведущий и завершающий узлы.
Таблица 4    
инициализацияhead = new node; z = new node; head -> next = z; z -> next -> z;
вставка t после xt -> next = x -> next; x -> next = t;
удаление после xx -> next = x -> next -> next;
цикл обходаfor (t = head -> next; t!= x; t=t -> next)
проверка на пустотуif( head -> next == x)


Для связных списков наиболее характерны следующие ошибки:
1) ссылка на неопределенный указатель
2) использование указателя, который изменяется неизвестным образом
Причина этих ошибок – возможное присутствие указателей на один и тот же узел.