Структура на данните 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 (1) O (1)
Изтриване O (1) O (1)

Сложност на пространството: O (n)

Приложения със свързан списък

  • Динамично разпределение на паметта
  • Внедрено в стека и опашката
  • Възможност за отмяна на софтуера
  • Хеш таблици, графики

Препоръчителни четива

1. Уроци

  • Операции на LinkedList (Преминаване, Вмъкване, Изтриване)
  • Видове LinkedList
  • Java LinkedList

2. Примери

  • Вземете средния елемент на LinkedList в една итерация
  • Преобразувайте LinkedList в масив и обратно
  • Откриване на цикъл в LinkedList

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