Типы связного списка

Существуют следующие типы связанных списков:

1. Односвязный список
2. Двусвязный список
3. Циркулярный связанный список
4. Двукратно циклический связанный список

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

Односвязный список – это наиболее распространенный тип связного списка, в котором каждый узел состоит из двух частей:

1. Информационная часть или часть данных
2. Указатель на следующий узел.

Если предположить, что односвязный список состоит из четырех (4) узлов, то он будет выглядеть следующим образом,

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

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

Код на языке Си для узла в односвязном списке выглядит следующим образом,

struct node
{
  int data;
  struct node *next;
}

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

В этом типе связного списка каждый узел содержит два указателя, т.е. один указывает на следующий по порядку узел, а другой – на непосредственно предыдущий.

Узел в двусвязном списке содержит три информации,

1. Информация о данных
2. Указатель на следующий узел
3. Указатель на предыдущий узел

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

Первый узел не имеет предыдущего узла, следовательно, указатель на предыдущий узел равен NULL.

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

Код на языке Си для узла в двусвязном списке представлен следующим образом,

struct node
{
  int data;
  struct node *next;
  struct node *prev;
}

Циркулярный связный список :

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

Двойной циклический связный список :

Узел в двойном циклическом связанном списке содержит три информации, а именно

1. Информация о данных
2. Указатель на следующий узел
3. Указатель на предыдущий узел

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

У меня есть сайт www.coderlogs.com, на котором я пишу подобные блоги, так что заходите на этот сайт, чтобы узнать больше подобных статей.