Структура даних LinkedList

У цьому підручнику ви дізнаєтесь про структуру даних зв'язаних списків та її реалізацію в Python, Java, C та C ++.

Структура даних зв’язаного списку включає ряд підключених вузлів. Тут кожен вузол зберігає дані та адресу наступного вузла. Наприклад,

Структура даних LinkedList

Ви повинні десь починати, тому ми надаємо адресі першого вузла спеціальне ім’я HEAD.

Крім того, останній вузол у зв’язаному списку може бути ідентифікований, оскільки його наступна частина вказує на NULL.

Можливо, ви грали у гру Полювання на скарби, де кожна підказка містить інформацію про наступну підказку. Ось як працює зв’язаний список.

Представлення LinkedList

Давайте подивимося, як представлений кожен вузол LinkedList. Кожен вузол складається:

  • Елемент даних
  • Адреса іншого вузла

Ми обертаємо як елемент даних, так і посилання на наступний вузол у структуру як:

 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;

Якщо ви не зрозуміли жодного з наведених вище рядків, вам знадобиться лише оновлення покажчиків та конструкцій.

Всього за кілька кроків ми створили простий пов'язаний список із трьома вузлами.

Представлення LinkedList

Потужність LinkedList походить від здатності розірвати ланцюг і знову приєднатися до нього. Наприклад, якщо ви хочете поставити елемент 4 між 1 і 2, кроки будуть такими:

  • Створіть новий структурний вузол і виділіть на нього пам’ять.
  • Додайте значення даних як 4
  • Наведіть його наступний вказівник на вузол структури, що містить 2 як значення даних
  • Змініть наступний покажчик "1" на вузол, який ми щойно створили.

Виконання чогось подібного в масиві зажадало б зміщення позицій усіх наступних елементів.

У python та Java пов'язаний список може бути реалізований за допомогою класів, як показано в кодах нижче.

Утиліта зв’язаного списку

Списки - це одна з найпопулярніших та найефективніших структур даних, що реалізується на всіх мовах програмування, таких як C, C ++, Python, Java і C #

Окрім цього, зв’язані списки - чудовий спосіб дізнатись, як працюють покажчики. Практикуючись у маніпулюванні зв’язаними списками, ви можете підготуватися до вивчення більш досконалих структур даних, таких як графіки та дерева.

Реалізації зв’язаного списку в прикладах Python, Java, C та C ++

Python Java C C + 
 # Linked list implementation in Python class Node: # Creating a node def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None if __name__ == '__main__': linked_list = LinkedList() # Assign item values linked_list.head = Node(1) second = Node(2) third = Node(3) # Connect nodes linked_list.head.next = second second.next = third # Print the linked list item while linked_list.head != None: print(linked_list.head.item, end=" ") linked_list.head = linked_list.head.next 
 // Linked list implementation in Java class LinkedList ( // Creating a node Node head; static class Node ( int value; Node next; Node(int d) ( value = d; next = null; ) ) public static void main(String() args) ( LinkedList linkedList = new LinkedList(); // Assign value values linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // Connect nodess linkedList.head.next = second; second.next = third; // printing node-value while (linkedList.head != null) ( System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; ) ) )
 // Linked list implementation in C #include #include // Creating a node struct node ( int value; struct node *next; ); // print the linked list value void printLinkedlist(struct node *p) ( while (p != NULL) ( printf("%d ", p->value); p = p->next; ) ) int main() ( // 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 value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist(head); )
 // Linked list implementation in C++ #include using namespace std; // Creating a node class Node ( public: int value; Node* next; ); int main() ( Node* head; Node* one = NULL; Node* two = NULL; Node* three = NULL; // allocate 3 nodes in the heap one = new Node(); two = new Node(); three = new Node(); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // print the linked list value head = one; while (head != NULL) ( printf("%d ", head->value); head = head->next; ) )

Складність пов’язаного списку

Складність часу

Найгірший випадок Середній випадок
Пошук O (n) O (n)
Вставити O (1) O (1)
Видалення O (1) O (1)

Складність простору: O (n)

Додатки зі зв’язаним списком

  • Динамічне виділення пам'яті
  • Реалізовано в стеку та черзі
  • У відмін функціональності програмного забезпечення
  • Хеш-таблиці, графіки

Рекомендовані читання

1. Підручники

  • Операції LinkedList (обхід, вставка, видалення)
  • Типи LinkedList
  • Java LinkedList

2. Приклади

  • Отримайте середній елемент LinkedList за одну ітерацію
  • Перетворіть LinkedList в масив і навпаки
  • Виявити цикл у LinkedList

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