linked list data structure c with illustration
Un studiu detaliat al listei legate în C ++.
Ripper DVD gratuit pentru Windows 8.1
O listă legată este o structură de date dinamică liniară pentru stocarea articolelor de date. Am văzut deja matrici în subiectele noastre anterioare despre C ++ de bază. Știm, de asemenea, că matricele sunt o structură de date liniară care stochează articole de date în locații adiacente.
Spre deosebire de tablouri, lista legată nu stochează elemente de date în locații de memorie contigue.
O listă legată constă din elemente numite „Noduri” care conțin două părți. Prima parte stochează datele reale, iar a doua parte are un pointer care indică următorul nod. Această structură se numește de obicei „Listă legată individual”.
=> Consultați aici cele mai bune tutoriale de formare C ++.
Ce veți învăța:
Listă legată în C ++
Vom arunca în detaliu lista legată individual în acest tutorial.
Următoarea diagramă arată structura unei liste conectate individual.
Așa cum se arată mai sus, primul nod al listei conectate se numește „cap”, în timp ce ultimul nod se numește „Coadă”. După cum vedem, ultimul nod al listei conectate va avea următorul indicator ca nul, deoarece nu va avea nicio adresă de memorie indicată.
Deoarece fiecare nod are un pointer către următorul nod, elementele de date din lista legată nu trebuie să fie stocate în locații contigue. Nodurile pot fi împrăștiate în memorie. Putem accesa nodurile oricând, deoarece fiecare nod va avea o adresă a nodului următor.
Putem adăuga articole de date la lista conectată, precum și șterge articole din listă cu ușurință. Astfel, este posibil să crească sau să micșoreze dinamic lista legată. Nu există o limită superioară pentru numărul de articole de date care pot fi acolo în lista conectată. Deci, atâta timp cât memoria este disponibilă, putem avea cât mai multe elemente de date adăugate la lista conectată.
În afară de inserarea și ștergerea ușoară, lista conectată nu pierde spațiu de memorie, deoarece nu trebuie să specificăm în prealabil câte articole avem nevoie în lista conectată. Singurul spațiu ocupat de lista legată este pentru stocarea indicatorului la următorul nod care adaugă un pic peste cap.
În continuare, vom discuta despre diferitele operații care pot fi efectuate pe o listă legată.
Operațiuni
La fel ca celelalte structuri de date, putem efectua diverse operații și pentru lista legată. Dar, spre deosebire de matrici, în care putem accesa elementul folosind direct indicele, chiar dacă este undeva între ele, nu putem face același acces aleatoriu cu o listă legată.
Pentru a accesa orice nod, trebuie să parcurgem lista legată de la început și numai atunci putem accesa nodul dorit. Prin urmare, accesarea aleatorie a datelor din lista legată se dovedește a fi costisitoare.
Putem efectua diverse operațiuni pe o listă legată, așa cum este prezentat mai jos:
# 1) Inserare
Operația de inserare a listei conectate adaugă un element la lista legată. Deși poate părea simplu, având în vedere structura listei conectate, știm că ori de câte ori un element de date este adăugat la lista legată, trebuie să schimbăm următorii indicatori ai nodurilor anterioare și următoare ale noului element pe care l-am inserat.
Al doilea lucru pe care trebuie să-l luăm în considerare este locul în care urmează să fie adăugat noul element de date.
Există trei poziții în lista legată în care poate fi adăugat un element de date.
# 1) La începutul listei conectate
O listă legată este prezentată mai jos 2-> 4-> 6-> 8-> 10. Dacă dorim să adăugăm un nou nod 1, ca primul nod al listei, atunci capul care indică nodul 2 va indica acum 1 și următorul indicator al nodului 1 va avea o adresă de memorie a nodului 2, așa cum se arată mai jos figura.
cel mai bun firewall pentru Windows 7 pe 64 de biți
Astfel noua listă legată devine 1-> 2-> 4-> 6-> 8-> 10.
# 2) După nodul dat
Aici, este dat un nod și trebuie să adăugăm un nou nod după nodul dat. În lista de mai jos legată a-> b-> c-> d -> e, dacă dorim să adăugăm un nod f după nodul c, atunci lista legată va arăta după cum urmează:
Astfel, în diagrama de mai sus, verificăm dacă nodul dat este prezent. Dacă este prezent, vom crea un nou nod f. Apoi îndreptăm următorul indicator al nodului c pentru a indica noul nod f. Următorul indicator al nodului f indică acum nodul d.
# 3) La sfârșitul listei conectate
În al treilea caz, adăugăm un nou nod la sfârșitul listei conectate. Luați în considerare că avem aceeași listă legată a-> b-> c-> d-> e și trebuie să adăugăm un nod f la sfârșitul listei. Lista conectată va arăta așa cum se arată mai jos după adăugarea nodului.
Astfel creăm un nou nod f. Apoi, indicatorul cozii care indică spre nul este arătat spre f și următorul indicator al nodului f este arătat spre nul. Am implementat toate cele trei tipuri de funcții de inserare în programul C ++ de mai jos.
În C ++, putem declara o listă legată ca structură sau ca clasă. Declararea listei legate ca structură este o declarație tradițională în stil C. O listă legată ca o clasă este utilizată în C ++ modern, mai ales în timpul utilizării bibliotecii de șabloane standard.
În următorul program, am folosit structura pentru a declara și a crea o listă legată. Va avea date și pointer către următorul element ca membri.
#include using namespace std; // A linked list node struct Node { int data; struct Node *next; }; //insert a new node in front of the list void push(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; /* 2. assign data to node */ newNode->data = node_data; /* 3. set next of new node as head */ newNode->next = (*head); /* 4. move the head to point to the new node */ (*head) = newNode; } //insert new node after a given node void insertAfter(struct Node* prev_node, int node_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { coutnext = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = newNode; } /* insert new node at the end of the linked list */ void append(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; struct Node *last = *head; /* used in step 5*/ /* 2. assign data to the node */ newNode->data = node_data; /* 3. set next pointer of new node to null as its the last node*/ newNode->next = NULL; /* 4. if list is empty, new node becomes first node */ if (*head == NULL) { *head = newNode; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = newNode; return; } // display linked list contents void displayList(struct Node *node) { //traverse the list to display each node while (node != NULL) { coutnext; } if(node== NULL) cout Ieșire:
Lista finală legată:
30–> 20–> 50–> 10–> 40–> nul
Apoi, implementăm operația de inserare a listei legate în Java. În limbajul Java, lista legată este implementată ca o clasă. Programul de mai jos este similar în logică cu programul C ++, singura diferență este că folosim o clasă pentru lista legată.
class LinkedList { Node head; // head of list //linked list node declaration class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Insert a new node at the front of the list */ public void push(int new_data) { //allocate and assign data to the node Node newNode = new Node(new_data); //new node becomes head of linked list newNode.next = head; //head points to new node head = newNode; } // Given a node,prev_node insert node after prev_node public void insertAfter(Node prev_node, int new_data) { //check if prev_node is null. if (prev_node == null) { System.out.println('The given node is required and cannot be null'); return; } //allocate node and assign data to it Node newNode = new Node(new_data); //next of new Node is next of prev_node newNode.next = prev_node.next; //prev_node->next is the new node. prev_node.next = newNode; } //inserts a new node at the end of the list public void append(intnew_data) { //allocate the node and assign data Node newNode = new Node(new_data); //if linked list is empty, then new node will be the head if (head == null) { head = new Node(new_data); return; } //set next of new node to null as this is the last node newNode.next = null; // if not the head node traverse the list and add it to the last Node last = head; while (last.next != null) last = last.next; //next of last becomes new node last.next = newNode; return; } //display contents of linked list public void displayList() { Node pnode = head; while (pnode != null) { System.out.print(pnode.data+'-->'); pnode = pnode.next; } if(pnode == null) System.out.print('null'); } } //Main class to call linked list class functions and construct a linked list class Main{ public static void main(String() args) { /* create an empty list */ LinkedList lList = new LinkedList(); // Insert 40. lList.append(40); // Insert 20 at the beginning. lList.push(20); // Insert 10 at the beginning. lList.push(10); // Insert 50 at the end. lList.append(50); // Insert 30, after 20. lList.insertAfter(lList.head.next, 30); System.out.println('
Final linked list: '); lList. displayList (); } } Ieșire:
Lista finală legată:
10–> 20–> 30–> 40–> 50–> nul
Atât în programul de mai sus, C ++, cât și în Java, avem funcții separate pentru a adăuga un nod în fața listei, la sfârșitul listei și între listele date într-un nod. La final, imprimăm conținutul listei create folosind toate cele trei metode.
# 2) Ștergere
La fel ca inserarea, ștergerea unui nod dintr-o listă legată implică, de asemenea, diferite poziții de unde nodul poate fi șters. Putem șterge primul nod, ultimul nod sau un al zecelea nod din lista conectată. După ștergere, trebuie să ajustăm în mod corespunzător următorul pointer și celelalte pointeri din lista legată, astfel încât să păstrăm intactă lista legată.
În următoarea implementare C ++, am dat două metode de ștergere, adică ștergerea primului nod din listă și ștergerea ultimului nod din listă. Mai întâi creăm o listă adăugând noduri în cap. Apoi afișăm conținutul listei după inserare și fiecare ștergere.
#include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; //delete first node in the linked list Node* deleteFirstNode(struct Node* head) { if (head == NULL) return NULL; // Move the head pointer to the next node Node* tempNode = head; head = head->next; delete tempNode; return head; } //delete last node from linked list Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // first find second last node Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete the last node delete (second_last->next); // set next of second_last to null second_last->next = NULL; return head; } // create linked list by adding nodes at head void push(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode; } // main function int main() { /* Start with the empty list */ Node* head = NULL; // create linked list push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<'Linked list created ' Ieșire:
A fost creată lista conectată
10–> 8–> 6–> 4–> 2–
> NUL
Listă legată după ștergerea nodului principal
8–> 6–> 4–> 2–
> NUL
Listă legată după ștergerea ultimului nod
8–> 6–> 4–> NUL
Urmează implementarea Java pentru ștergerea nodurilor din lista legată. Logica de implementare este aceeași cu cea utilizată în programul C ++. Singura diferență este că lista legată este declarată ca o clasă.
class Main { // Linked list node / static class Node { int data; Node next; }; // delete first node of linked list static Node deleteFirstNode(Node head) { if (head == null) return null; // Move the head pointer to the next node Node temp = head; head = head.next; return head; } // Delete the last node in linked list static Node deleteLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // search for second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // set next of second last to null second_last.next = null; return head; } // Add nodes to the head and create linked list static Node push(Node head, int new_data) { Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head; } //main function public static void main(String args()) { // Start with the empty list / Node head = null; //create linked list head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println('Linked list created :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteFirstNode(head); System.out.println('Linked list after deleting head node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteLastNode(head); System.out.println('Linked list after deleting last node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); } } Ieșire:
Lista legată a fost creată:
9–> 7–> 5–> 3–> 1–
> nul
Listă legată după ștergerea nodului principal:
7–> 5–> 3–> 1–
> nul
cum se creează o listă de obiecte în java
Lista conectată după ștergerea ultimului nod:
7–> 5–> 3–> nul
Numărați numărul de noduri
Operația de numărare a numărului de noduri poate fi efectuată în timp ce parcurgeți lista legată. Am văzut deja în implementarea de mai sus că ori de câte ori trebuie să inserăm / ștergem un nod sau să afișăm conținutul listei legate, trebuie să traversăm lista legată de la început.
Păstrarea unui contor și creșterea acestuia pe măsură ce parcurgem fiecare nod ne va oferi numărul numărului de noduri prezente în lista legată. Vom lăsa acest program pentru cititori să-l implementeze.
Matrice și liste legate
După ce am văzut operațiunile și implementarea listei conectate, haideți să comparăm modul în care sunt corecte matricile și lista legată în comparație.
Matrice Liste legate Tablourile au dimensiuni fixe Dimensiunea listei conectate este dinamică Introducerea unui element nou este costisitoare Inserarea / ștergerea este mai ușoară Accesul aleator este permis Accesul aleatoriu nu este posibil Elementele se află într-o locație contiguă Elementele au locație necontiguă Nu este necesar spațiu suplimentar pentru următorul indicator Spațiu suplimentar de memorie necesar pentru următorul indicator
Aplicații
Deoarece matricile și listele legate sunt utilizate pentru a stoca articole și sunt structuri de date liniare, ambele structuri pot fi utilizate în moduri similare pentru majoritatea aplicațiilor.
Unele dintre aplicațiile pentru listele legate sunt următoarele:
- O listă legată poate fi utilizată pentru a implementa stive și cozi.
- O listă legată poate fi utilizată și pentru a implementa grafice ori de câte ori trebuie să reprezentăm grafice ca liste de adiacență.
- Un polinom matematic poate fi stocat ca o listă legată.
- În cazul tehnicii de hashing, gălețile utilizate în hashing sunt implementate folosind listele legate.
- Ori de câte ori un program necesită alocarea dinamică a memoriei, putem folosi o listă legată, deoarece listele legate funcționează mai eficient în acest caz.
Concluzie
Listele legate sunt structurile de date care sunt utilizate pentru a stoca elementele de date într-un mod liniar, dar locații necontigue. O listă legată este o colecție de noduri care conțin o parte de date și un următor următor care conține adresa de memorie a următorului element din listă.
Ultimul element din listă are următorul indicator setat la NULL, indicând astfel sfârșitul listei. Primul element al listei se numește Cap. Lista legată acceptă diverse operații precum inserarea, ștergerea, traversarea etc. În cazul alocării dinamice a memoriei, listele legate sunt preferate în fața matricelor.
Listele legate sunt costisitoare în ceea ce privește traversarea lor, deoarece nu putem accesa în mod aleatoriu elemente precum matricele. Cu toate acestea, operațiile de inserare-ștergere sunt mai puțin costisitoare atunci când se compară matrici.
Am învățat totul despre listele liniare legate în acest tutorial. Listele legate pot fi, de asemenea, circulare sau dublu. Vom analiza în detaliu aceste liste în tutorialele noastre viitoare.
=> Verificați aici pentru seria completă de formare C ++.
Lectură recomandată
- Structură de date cu listă circulară legată în C ++ cu ilustrație
- Structură de date de listă dublă legată în C ++ cu ilustrare
- Structura datelor în coadă în C ++ cu ilustrație
- Stivați structura datelor în C ++ cu ilustrație
- Structura de date a cozii prioritare în C ++ cu ilustrație
- Top 15 Cele mai bune instrumente gratuite de extragere a datelor: Lista cea mai cuprinzătoare
- Cele mai bune 15 instrumente ETL în 2021 (o listă completă actualizată)
- Introducere în structurile de date în C ++