Dátová štruktúra LinkedList

V tomto výučbe sa dozviete o štruktúre údajov prepojeného zoznamu a jej implementácii v jazykoch Python, Java, C a C ++.

Prepojená dátová štruktúra zoznamu obsahuje sériu spojených uzlov. Tu každý uzol ukladá údaje a adresu nasledujúceho uzla. Napríklad,

Dátová štruktúra LinkedList

Musíte niekde začať, takže adrese prvého uzla dáme špeciálny názov s názvom HLAVA.

Môže byť identifikovaný aj posledný uzol v prepojenom zozname, pretože jeho ďalšia časť ukazuje na NULL.

Možno ste hrali hru Treasure Hunt, kde každá stopa obsahuje informácie o nasledujúcej stope. Takto funguje prepojený zoznam.

Zastúpenie LinkedList

Pozrime sa, ako je znázornený každý uzol LinkedList. Každý uzol pozostáva:

  • Dátová položka
  • Adresa iného uzla

Dátovú položku aj odkaz na ďalší uzol zabalíme do štruktúry ako:

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

Pochopenie štruktúry uzla prepojeného zoznamu je kľúčom k jeho pochopeniu.

Každý štruktúrovaný uzol má údajovú položku a ukazovateľ na iný štruktúrny uzol. Vytvorme jednoduchý prepojený zoznam s tromi položkami, aby sme pochopili, ako to funguje.

 /* 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;

Ak ste nepochopili žiadny z riadkov vyššie, potrebujete iba aktualizáciu ukazovateľov a štruktúr.

Iba v niekoľkých krokoch sme vytvorili jednoduchý prepojený zoznam s tromi uzlami.

Zastúpenie LinkedList

Sila LinkedList pochádza zo schopnosti prelomiť reťaz a znovu sa k nej pripojiť. Ak by ste napríklad chceli vložiť prvok 4 medzi 1 a 2, boli by to kroky:

  • Vytvorte nový štruktúrovaný uzol a pridelte mu pamäť.
  • Pridajte jeho údajovú hodnotu ako 4
  • Nasmerujte ďalší ukazovateľ na štruktúrovaný uzol obsahujúci ako údajovú hodnotu 2
  • Zmeňte nasledujúci ukazovateľ „1“ na uzol, ktorý sme práve vytvorili.

Urobiť niečo podobné v poli by si vyžadovalo posunutie pozícií všetkých nasledujúcich prvkov.

V jazykoch python a Java je možné prepojený zoznam implementovať pomocou tried, ako je uvedené v nižšie uvedených kódoch.

Prepojený zoznam Utility

Zoznamy sú jednou z najpopulárnejších a najefektívnejších dátových štruktúr s implementáciou v každom programovacom jazyku, ako sú C, C ++, Python, Java a C #.

Okrem toho sú prepojené zoznamy skvelým spôsobom, ako sa naučiť, ako fungujú ukazovatele. Precvičením manipulácie s prepojenými zoznamami sa môžete pripraviť na to, aby ste sa naučili pokročilejšie dátové štruktúry, ako sú grafy a stromy.

Implementácie prepojeného zoznamu v príkladoch Python, Java, C a 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; ) )

Zložitosť prepojeného zoznamu

Časová zložitosť

V najhoršom prípade Priemerný prípad
Vyhľadávanie O (n) O (n)
Vložte O (1) O (1)
Vymazanie O (1) O (1)

Zložitosť vesmíru: O (n)

Prepojené aplikácie zoznamu

  • Dynamické prideľovanie pamäte
  • Implementované v zásobníku a fronte
  • V undo funkčnosť softvérov
  • Hašovacie tabuľky, grafy

Odporúčané čítania

1. Výukové programy

  • Operácie LinkedList (posúvanie, vkladanie, mazanie)
  • Typy LinkedList
  • Java LinkedList

2. Príklady

  • Získajte prostredný prvok LinkedList v jednej iterácii
  • Preveďte LinkedList na pole a naopak
  • Zistiť slučku v zozname LinkedList

Zaujímavé články...