Види пов'язаного списку

У цьому посібнику ви дізнаєтесь різні типи пов'язаних списків. Крім того, ви знайдете реалізацію пов'язаного списку в 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;

Цікаві статті...