Struktura podataka LinkedList

U ovom vodiču naučit ćete o strukturi podataka povezanih popisa i njenoj implementaciji u Pythonu, Java, C i C ++.

Povezana struktura podataka popisa uključuje niz povezanih čvorova. Ovdje svaki čvor pohranjuje podatke i adresu sljedećeg čvora. Na primjer,

Struktura podataka LinkedList

Morate negdje započeti, pa adresi prvog čvora dajemo poseban naziv pod nazivom HEAD.

Također, zadnji čvor na povezanom popisu može se identificirati jer njegov sljedeći dio usmjerava na NULL.

Možda ste igrali igru ​​Treasure Hunt, gdje svaki trag uključuje informacije o sljedećem tragu. Tako funkcionira povezani popis.

Predstavljanje LinkedList-a

Pogledajmo kako je predstavljen svaki čvor LinkedList-a. Svaki čvor sastoji se od:

  • Stavka podataka
  • Adresa drugog čvora

Stavku podataka i sljedeću referencu čvora umotavamo u strukturu kao:

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

Razumijevanje strukture povezanog čvornog popisa ključno je za razumijevanje.

Svaki strukturni čvor ima stavku podataka i pokazivač na drugi strukturni čvor. Stvorimo jednostavan povezani popis s tri stavke kako bismo razumjeli kako ovo funkcionira.

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

Ako niste razumjeli nijedan gornji redak, sve što vam treba je osvježavanje pokazivača i uputa.

U samo nekoliko koraka stvorili smo jednostavan povezani popis s tri čvora.

Zastupljenost na LinkedListu

Snaga LinkedList-a dolazi iz sposobnosti prekida lanca i ponovnog pridruživanja. Npr. Ako želite staviti element 4 između 1 i 2, koraci bi bili:

  • Stvorite novi strukturni čvor i dodijelite mu memoriju.
  • Dodajte vrijednost podataka kao 4
  • Usmjerite njegov sljedeći pokazivač na strukturni čvor koji sadrži 2 kao vrijednost podataka
  • Promijenite sljedeći pokazivač "1" na čvor koji smo upravo stvorili.

Da bi se učinilo nešto slično u nizu, bilo bi potrebno pomicanje položaja svih sljedećih elemenata.

U pythonu i Javi, povezani se popis može implementirati pomoću klasa kao što je prikazano u donjim kodovima.

Uslužni program s povezanim popisom

Popisi su jedna od najpopularnijih i najučinkovitijih struktura podataka, s implementacijom u svaki programski jezik poput C, C ++, Python, Java i C #.

Osim toga, povezani su popisi sjajan način da naučite kako rade pokazivači. Vježbajući kako manipulirati povezanim popisima, možete se pripremiti za učenje naprednijih struktura podataka poput grafikona i stabala.

Implementacije povezanih popisa u primjerima Pythona, Java, C i 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; ) )

Složenost povezanog popisa

Složenost vremena

Najgori slučaj Prosječni slučaj
traži Na) Na)
Umetnuti O (1) O (1)
Brisanje O (1) O (1)

Složenost prostora: O (n)

Aplikacije s povezanim popisom

  • Dinamička dodjela memorije
  • Implementirano u stogu i redu čekanja
  • U poništavanje funkcionalnosti softver
  • Hash tablice, grafikoni

Preporučena čitanja

1. Vodiči

  • Operacije LinkedList (prelazak, umetanje, brisanje)
  • Vrste LinkedList-a
  • Java LinkedList

2. Primjeri

  • Nabavite srednji element LinkedList-a u jednoj iteraciji
  • Pretvorite LinkedList u niz i obrnuto
  • Otkrivanje petlje u LinkedListu

Zanimljivi članci...