linked list data structure c with illustration
Un estudi detallat de la llista enllaçada en C ++.
Una llista enllaçada és una estructura de dades dinàmica lineal per emmagatzemar elements de dades. Ja hem vist matrius en els nostres temes anteriors sobre C ++ bàsic. També sabem que les matrius són una estructura de dades lineal que emmagatzema elements de dades en ubicacions contigües.
A diferència de les matrius, la llista enllaçada no emmagatzema elements de dades en ubicacions de memòria contigües.
Una llista enllaçada consta d'elements anomenats 'Nodes' que contenen dues parts. La primera part emmagatzema les dades reals i la segona part té un punter que apunta al següent node. Aquesta estructura se sol anomenar 'llista enllaçada individualment'.
=> Consulteu aquí els millors tutorials de formació en C ++.
preguntes d’entrevistes de programació java per a experimentats
Què aprendreu:
Llista enllaçada a C ++
Vegem detalladament la llista enllaçada individualment en aquest tutorial.
El diagrama següent mostra l'estructura d'una llista enllaçada individualment.
Com es mostra més amunt, el primer node de la llista enllaçada s'anomena 'cap' mentre que l'últim node es diu 'Cua'. Com veiem, l’últim node de la llista enllaçada tindrà el següent punter com a nul, ja que no tindrà cap adreça de memòria apuntada.
Com que cada node té un punter al node següent, no cal que els elements de dades de la llista enllaçats s’emmagatzemin a ubicacions contigües. Els nodes es poden dispersar a la memòria. Podem accedir als nodes en qualsevol moment, ja que cada node tindrà una adreça del següent node.
Podem afegir elements de dades a la llista enllaçada i eliminar elements de la llista fàcilment. Per tant, és possible fer créixer o reduir la llista enllaçada dinàmicament. No hi ha cap límit màxim de quants elements de dades hi pot haver a la llista enllaçada. Així, sempre que hi hagi memòria disponible, podem afegir tants elements de dades a la llista enllaçada.
A part de la fàcil inserció i supressió, la llista enllaçada tampoc no malgasta espai de memòria, ja que no cal especificar prèviament quants elements necessitem a la llista enllaçada. L'únic espai que ocupa la llista enllaçada és per emmagatzemar el punter al següent node que afegeix una mica de sobrecàrrega.
A continuació, parlarem de les diverses operacions que es poden realitzar en una llista enllaçada.
Operacions
Igual que les altres estructures de dades, també podem realitzar diverses operacions per a la llista enllaçada. Però, a diferència de les matrius, en les quals podem accedir a l'element mitjançant subíndex directament, fins i tot si es troba en algun lloc intermedi, no podem fer el mateix accés aleatori amb una llista enllaçada.
Per accedir a qualsevol node, hem de recórrer la llista enllaçada des del principi i només llavors podem accedir al node desitjat. Per tant, accedir a les dades de manera aleatòria des de la llista enllaçada resulta ser car.
Podem realitzar diverses operacions en una llista enllaçada tal i com es mostra a continuació:
# 1) Inserció
L'operació d'inserció de la llista enllaçada afegeix un element a la llista enllaçada. Tot i que pot semblar senzill, donada l’estructura de la llista enllaçada, sabem que cada vegada que s’afegeix un element de dades a la llista enllaçada, hem de canviar els indicadors següents dels nodes anterior i següent del nou element que hem inserit.
El segon que hem de tenir en compte és el lloc on s’ha d’afegir el nou element de dades.
Hi ha tres posicions a la llista enllaçada on es pot afegir un element de dades.
# 1) Al començament de la llista enllaçada
A continuació es mostra una llista enllaçada 2-> 4-> 6-> 8-> 10. Si volem afegir un nou node 1, com a primer node de la llista, el cap que apunta al node 2 ara apuntarà a 1 i el següent punter del node 1 tindrà una adreça de memòria del node 2 tal com es mostra a continuació figura.
Així, la nova llista enllaçada es converteix en 1-> 2-> 4-> 6-> 8-> 10.
# 2) Després del node donat
Aquí es dóna un node i hem d’afegir un nou després del node donat. A la llista enllaçada a continuació, a-> b-> c-> d -> e, si volem afegir un node f després del node c, la llista enllaçada tindrà el següent aspecte:
Així, en el diagrama anterior, comprovem si el node donat és present. Si és present, crearem un nou node f. A continuació, assenyalem el següent punter del node c per assenyalar el nou node f. El següent punter del node f apunta ara al node d.
# 3) Al final de la llista enllaçada
En el tercer cas, afegim un nou node al final de la llista enllaçada. Penseu que tenim la mateixa llista enllaçada a-> b-> c-> d-> e i hem d’afegir un node f al final de la llista. La llista enllaçada es mostrarà com es mostra a continuació després d'afegir el node.
Així creem un nou node f. Aleshores, el punter de la cua que apunta a nul és apuntat a f i el següent punter del node f és a nul. Hem implementat els tres tipus de funcions d'inserció al programa C ++ següent.
A C ++, podem declarar una llista enllaçada com a estructura o com a classe. Declarar una llista enllaçada com a estructura és una declaració tradicional a l’estil C. Una llista enllaçada com a classe s’utilitza en C ++ modern, principalment mentre s’utilitza la biblioteca de plantilles estàndard.
Al programa següent, hem utilitzat l’estructura per declarar i crear una llista enllaçada. Tindrà dades i punter cap al següent element com a membres.
#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 Sortida:
Llista final enllaçada:
30–> 20–> 50–> 10–> 40–> nul
A continuació, implementem l'operació d'inserció de llista enllaçada a Java. En llenguatge Java, la llista enllaçada s’implementa com a classe. El programa següent és similar en lògica al programa C ++, l’única diferència és que fem servir una classe per a la llista enllaçada.
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 (); } } Sortida:
Llista final enllaçada:
10–> 20–> 30–> 40–> 50–> nul
Tant al programa anterior, C ++ com a Java, tenim funcions separades per afegir un node davant de la llista, al final de la llista i entre les llistes donades en un node. Al final, imprimim el contingut de la llista creada utilitzant els tres mètodes.
# 2) Supressió
Igual que la inserció, suprimir un node d'una llista enllaçada també implica diverses posicions des d'on es pot suprimir el node. Podem suprimir el primer node, l’últim node o un kth node aleatori de la llista enllaçada. Després de la supressió, hem d’ajustar el següent punter i els altres indicadors de la llista enllaçada de manera adequada per mantenir intacta la llista enllaçada.
A la següent implementació de C ++, hem donat dos mètodes de supressió, és a dir, suprimir el primer node de la llista i suprimir l’últim node de la llista. Primer creem una llista afegint nodes al cap. A continuació, mostrem el contingut de la llista després de la inserció i de cada supressió.
#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 ' Sortida:
S'ha creat la llista enllaçada
10-> 8-> 6-> 4-> 2-
> NUL
Llista enllaçada després de suprimir el node principal
8-> 6-> 4-> 2-
> NUL
Llista enllaçada després de suprimir l'últim node
8–> 6–> 4–> NUL
El següent és la implementació de Java per suprimir nodes de la llista enllaçada. La lògica d’implementació és la mateixa que s’utilitza al programa C ++. L'única diferència és que la llista enllaçada es declara com a classe.
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'); } } Sortida:
Llista enllaçada creada:
9-> 7-> 5-> 3-> 1-
> nul
Llista enllaçada després de suprimir el node principal:
7-> 5-> 3-> 1-
> nul
Llista enllaçada després de suprimir l'últim node:
7–> 5–> 3–> nul
Compteu el nombre de nodes
L'operació per comptar el nombre de nodes es pot realitzar mentre es recorre la llista enllaçada. Ja hem vist a la implementació anterior que sempre que necessitem inserir / eliminar un node o mostrar el contingut de la llista enllaçada, hem de recórrer la llista enllaçada des del principi.
Mantenir un comptador i incrementar-lo mentre recorrem cada node ens donarà el recompte del nombre de nodes presents a la llista enllaçada. Deixarem aquest programa perquè els lectors l’implementin.
Matrius i llistes enllaçades
Després d'haver vist les operacions i la implementació de la llista enllaçada, comparem com són justes les matrius i la llista enllaçada en comparació entre si.
Matrius Llistes enllaçades Les matrius tenen una mida fixa La mida de la llista enllaçada és dinàmica La inserció d'un element nou és cara La inserció / supressió és més fàcil Es permet l'accés aleatori No és possible l'accés aleatori Els elements es troben en una ubicació contigua Els elements tenen una ubicació no contigua No es requereix espai addicional per al següent punter Es requereix espai de memòria addicional per al següent punter
Aplicacions
Com que les matrius i les llistes enllaçades s'utilitzen per emmagatzemar elements i són estructures de dades lineals, ambdues estructures es poden utilitzar de maneres similars per a la majoria de les aplicacions.
Algunes de les aplicacions per a llistes enllaçades són les següents:
- Es pot utilitzar una llista enllaçada per implementar piles i cues.
- També es pot utilitzar una llista enllaçada per implementar gràfics sempre que haguem de representar gràfics com a llistes d’adjacència.
- Un polinomi matemàtic es pot emmagatzemar com a llista enllaçada.
- En el cas de la tècnica de hash, els cubs utilitzats en el hash s’implementen mitjançant les llistes enllaçades.
- Sempre que un programa requereix assignació dinàmica de memòria, podem utilitzar una llista enllaçada, ja que les llistes enllaçades funcionen de manera més eficient en aquest cas.
Conclusió
Les llistes enllaçades són les estructures de dades que s’utilitzen per emmagatzemar elements de dades de manera lineal però ubicacions no contigües. Una llista enllaçada és una col·lecció de nodes que contenen una part de dades i un següent punter que conté l'adreça de memòria del següent element de la llista.
L'últim element de la llista té el següent punter establert a NULL, indicant així el final de la llista. El primer element de la llista s’anomena Cap. La llista enllaçada admet diverses operacions com ara inserció, supressió, recorregut, etc. En cas d'assignació dinàmica de memòria, es prefereixen les llistes enllaçades sobre les matrius.
Les llistes enllaçades són costoses pel que fa al seu recorregut, ja que no podem accedir a l'atzar a elements com ara matrius. Tot i això, les operacions d’inserció-supressió són menys costoses si es comparen matrius.
Hem après tot sobre llistes enllaçades lineals en aquest tutorial. Les llistes enllaçades també poden ser circulars o doblement. Veurem aquestes llistes en profunditat als nostres propers tutorials.
=> Consulteu aquí la sèrie completa d'entrenaments de C ++.
Lectura recomanada
- Estructura de dades de llistes enllaçades circulars en C ++ amb il·lustració
- Estructura de dades de llistes doblement enllaçades en C ++ amb il·lustració
- Estructura de dades de la cua en C ++ amb il·lustració
- Estructura de dades de pila en C ++ amb il·lustració
- Estructura de dades de la cua de prioritat en C ++ amb il·lustració
- Top 15 de les millors eines gratuïtes de mineria de dades: la llista més completa
- 15 millors eines ETL el 2021 (llista completa actualitzada)
- Introducció a les estructures de dades en C ++