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

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

Прежде чем узнать о типе связанного списка, убедитесь, что вы знаете о структуре данных LinkedList.

Существует три распространенных типа связанных списков.

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

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

Это самый распространенный. Каждый узел имеет данные и указатель на следующий узел.

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

Узел представлен как:

 struct node ( int data; struct node *next; )

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

 /* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;

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

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

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

Узел представлен как

 struct node ( int data; struct node *next; struct node *prev; )

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

 /* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; one->prev = NULL; two->next = three; two->prev = one; three->next = NULL; three->prev = two; /* Save address of first node in head */ head = one;

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

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

Циклический связанный список

Циклический связанный список может быть односвязным или двусвязным.

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

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

 /* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = one; /* Save address of first node in head */ head = one;

Интересные статьи...