linked list data structure c with illustration
Uno studio dettagliato della lista collegata in C ++.
Un elenco collegato è una struttura dati dinamica lineare per memorizzare elementi di dati. Abbiamo già visto gli array nei nostri argomenti precedenti sul C ++ di base. Sappiamo anche che gli array sono una struttura di dati lineare che memorizza elementi di dati in posizioni contigue.
A differenza degli array, l'elenco collegato non memorizza gli elementi di dati in posizioni di memoria contigue.
Un elenco collegato è costituito da elementi chiamati 'Nodi' che contengono due parti. La prima parte memorizza i dati effettivi e la seconda parte ha un puntatore che punta al nodo successivo. Questa struttura è solitamente chiamata 'Lista collegata singolarmente'.
=> Dai un'occhiata ai migliori tutorial di formazione C ++ qui.
Cosa imparerai:
Elenco collegato in C ++
In questo tutorial daremo un'occhiata in dettaglio alla lista collegata singolarmente.
Il diagramma seguente mostra la struttura di un elenco collegato singolarmente.
Come mostrato sopra, il primo nodo della lista collegata è chiamato 'testa' mentre l'ultimo nodo è chiamato 'coda'. Come si vede, l'ultimo nodo della lista collegata avrà il suo prossimo puntatore come nullo poiché non avrà puntato alcun indirizzo di memoria.
Poiché ogni nodo ha un puntatore al nodo successivo, gli elementi di dati nell'elenco collegato non devono essere archiviati in posizioni contigue. I nodi possono essere sparsi nella memoria. Possiamo accedere ai nodi in qualsiasi momento poiché ogni nodo avrà un indirizzo del nodo successivo.
Possiamo aggiungere elementi di dati all'elenco collegato così come eliminare facilmente elementi dall'elenco. In questo modo è possibile aumentare o ridurre dinamicamente l'elenco collegato. Non esiste un limite massimo al numero di elementi di dati che possono essere presenti nell'elenco collegato. Quindi, finché la memoria è disponibile, possiamo aggiungere tanti elementi di dati all'elenco collegato.
A parte il facile inserimento ed eliminazione, l'elenco collegato non spreca spazio di memoria poiché non è necessario specificare in anticipo quanti elementi abbiamo bisogno nell'elenco collegato. L'unico spazio occupato dalla lista collegata è per memorizzare il puntatore al nodo successivo che aggiunge un piccolo sovraccarico.
Successivamente, discuteremo le varie operazioni che possono essere eseguite su un elenco collegato.
Operazioni
Proprio come le altre strutture dati, possiamo eseguire varie operazioni anche per l'elenco collegato. Ma a differenza degli array, in cui possiamo accedere direttamente all'elemento utilizzando l'indice anche se si trova da qualche parte nel mezzo, non possiamo eseguire lo stesso accesso casuale con un elenco collegato.
Per accedere a qualsiasi nodo, dobbiamo attraversare l'elenco collegato dall'inizio e solo allora possiamo accedere al nodo desiderato. Pertanto, l'accesso casuale ai dati dalla lista collegata si rivela costoso.
Possiamo eseguire varie operazioni su un elenco collegato come indicato di seguito:
# 1) Inserimento
L'operazione di inserimento dell'elenco collegato aggiunge un elemento all'elenco collegato. Anche se può sembrare semplice, data la struttura della lista collegata, sappiamo che ogni volta che un elemento di dati viene aggiunto alla lista collegata, dobbiamo cambiare i puntatori successivi dei nodi precedenti e successivi del nuovo elemento che abbiamo inserito.
La seconda cosa che dobbiamo considerare è il luogo in cui aggiungere il nuovo elemento di dati.
Ci sono tre posizioni nell'elenco collegato in cui è possibile aggiungere un elemento di dati.
come aggiungere elementi di array in java
# 1) All'inizio della lista collegata
Di seguito viene mostrato un elenco collegato 2-> 4-> 6-> 8-> 10. Se vogliamo aggiungere un nuovo nodo 1, come primo nodo dell'elenco, la testina che punta al nodo 2 ora punterà a 1 e il puntatore successivo del nodo 1 avrà un indirizzo di memoria del nodo 2 come mostrato di seguito figura.
Quindi la nuova lista collegata diventa 1-> 2-> 4-> 6-> 8-> 10.
# 2) Dopo il dato Node
Qui viene fornito un nodo e dobbiamo aggiungere un nuovo nodo dopo il nodo specificato. Nell'elenco collegato di seguito a-> b-> c-> d -> e, se vogliamo aggiungere un nodo f dopo il nodo c, l'elenco collegato apparirà come segue:
Quindi nel diagramma sopra, controlliamo se il nodo dato è presente. Se è presente, creiamo un nuovo nodo f. Quindi puntiamo il puntatore successivo del nodo c in modo che punti al nuovo nodo f. Il prossimo puntatore del nodo f ora punta al nodo d.
# 3) Alla fine dell'elenco collegato
Nel terzo caso, aggiungiamo un nuovo nodo alla fine della lista collegata. Considera di avere la stessa lista concatenata a-> b-> c-> d-> e e dobbiamo aggiungere un nodo f alla fine della lista. L'elenco collegato apparirà come mostrato di seguito dopo aver aggiunto il nodo.
Quindi creiamo un nuovo nodo f. Quindi il puntatore di coda che punta a null è puntato a f e il successivo puntatore del nodo f è puntato a null. Abbiamo implementato tutti e tre i tipi di funzioni di inserimento nel seguente programma C ++.
In C ++, possiamo dichiarare una lista collegata come struttura o come classe. La dichiarazione di una lista collegata come una struttura è una tradizionale dichiarazione in stile C. Un elenco collegato come classe viene utilizzato nel moderno C ++, principalmente durante l'utilizzo della libreria di modelli standard.
Nel seguente programma, abbiamo utilizzato la struttura per dichiarare e creare un elenco collegato. Avrà dati e puntatore all'elemento successivo come 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 Produzione:
Elenco collegato finale:
30–> 20–> 50–> 10–> 40–> nullo
Successivamente, implementiamo l'operazione di inserimento dell'elenco collegato in Java. In linguaggio Java, l'elenco collegato è implementato come una classe. Il programma seguente è simile nella logica al programma C ++, l'unica differenza è che usiamo una classe per l'elenco collegato.
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 (); } } Produzione:
Elenco collegato finale:
10–> 20–> 30–> 40–> 50–> nullo
In entrambi i programmi sopra, C ++ e Java, abbiamo funzioni separate per aggiungere un nodo davanti alla lista, alla fine della lista e tra le liste fornite in un nodo. Alla fine, stampiamo il contenuto della lista creata utilizzando tutti e tre i metodi.
# 2) Cancellazione
Come l'inserimento, l'eliminazione di un nodo da un elenco collegato coinvolge anche varie posizioni da cui è possibile eliminare il nodo. Possiamo eliminare il primo nodo, l'ultimo nodo o un k-esimo nodo casuale dall'elenco collegato. Dopo l'eliminazione, è necessario regolare il puntatore successivo e gli altri puntatori nell'elenco collegato in modo appropriato in modo da mantenere intatto l'elenco collegato.
pro e contro di Linux vs Windows
Nella seguente implementazione C ++, abbiamo fornito due metodi di eliminazione, ovvero l'eliminazione del primo nodo nell'elenco e l'eliminazione dell'ultimo nodo nell'elenco. Per prima cosa creiamo un elenco aggiungendo nodi alla testa. Quindi visualizziamo il contenuto della lista dopo l'inserimento e ogni cancellazione.
#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 ' Produzione:
Elenco collegato creato
10–> 8–> 6–> 4–> 2–
> NULL
Elenco collegato dopo l'eliminazione del nodo head
8–> 6–> 4–> 2–
> NULL
Elenco collegato dopo l'eliminazione dell'ultimo nodo
8–> 6–> 4–> NULL
come aprire un file bin Windows 10
La prossima è l'implementazione Java per l'eliminazione dei nodi dall'elenco collegato. La logica di implementazione è la stessa utilizzata nel programma C ++. L'unica differenza è che l'elenco collegato è dichiarato come una 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'); } } Produzione:
Elenco collegato creato:
9–> 7–> 5–> 3–> 1–
> null
Elenco collegato dopo l'eliminazione del nodo head:
7–> 5–> 3–> 1–
> null
Elenco collegato dopo l'eliminazione dell'ultimo nodo:
7–> 5–> 3–> nullo
Contare il numero di nodi
L'operazione per contare il numero di nodi può essere eseguita mentre si attraversa l'elenco collegato. Abbiamo già visto nell'implementazione sopra che ogni volta che dobbiamo inserire / eliminare un nodo o visualizzare il contenuto della lista collegata, dobbiamo attraversare la lista collegata dall'inizio.
Mantenere un contatore e incrementarlo mentre attraversiamo ogni nodo ci darà il conteggio del numero di nodi presenti nell'elenco collegato. Lasceremo questo programma per l'implementazione dei lettori.
Array ed elenchi collegati
Dopo aver visto le operazioni e l'implementazione dell'elenco collegato, confrontiamo il modo in cui gli array e l'elenco collegato sono equi rispetto agli altri.
Array Elenchi collegati Gli array hanno dimensioni fisse La dimensione dell'elenco collegato è dinamica L'inserimento di un nuovo elemento è costoso L'inserimento / cancellazione è più semplice È consentito l'accesso casuale Accesso casuale non possibile Gli elementi sono in posizione contigua Gli elementi hanno una posizione non contigua Non è richiesto spazio aggiuntivo per il puntatore successivo Spazio di memoria aggiuntivo richiesto per il puntatore successivo
Applicazioni
Poiché gli array e gli elenchi collegati sono entrambi utilizzati per memorizzare gli elementi e sono strutture di dati lineari, entrambe queste strutture possono essere utilizzate in modo simile per la maggior parte delle applicazioni.
Alcune delle applicazioni per gli elenchi collegati sono le seguenti:
- Un elenco collegato può essere utilizzato per implementare stack e code.
- Un elenco collegato può essere utilizzato anche per implementare grafici ogni volta che dobbiamo rappresentare grafici come elenchi di adiacenza.
- Un polinomio matematico può essere memorizzato come elenco collegato.
- Nel caso della tecnica di hashing, i bucket utilizzati nell'hashing vengono implementati utilizzando gli elenchi collegati.
- Ogni volta che un programma richiede un'allocazione dinamica della memoria, possiamo utilizzare un elenco collegato poiché gli elenchi collegati funzionano in modo più efficiente in questo caso.
Conclusione
Gli elenchi collegati sono le strutture di dati utilizzate per memorizzare gli elementi di dati in modo lineare ma in posizioni non contigue. Un elenco collegato è una raccolta di nodi che contengono una parte dati e un puntatore successivo che contiene l'indirizzo di memoria dell'elemento successivo nell'elenco.
L'ultimo elemento della lista ha il suo prossimo puntatore impostato su NULL, indicando così la fine della lista. Il primo elemento della lista si chiama Head. L'elenco collegato supporta varie operazioni come l'inserimento, l'eliminazione, l'attraversamento, ecc. In caso di allocazione dinamica della memoria, gli elenchi collegati sono preferiti agli array.
Gli elenchi collegati sono costosi per quanto riguarda il loro attraversamento poiché non possiamo accedere in modo casuale agli elementi come gli array. Tuttavia, le operazioni di inserimento-eliminazione sono meno costose rispetto agli array.
Abbiamo imparato tutto sugli elenchi collegati lineari in questo tutorial. Gli elenchi collegati possono anche essere circolari o doppi. Daremo uno sguardo approfondito a questi elenchi nei nostri prossimi tutorial.
=> Controlla qui per la serie completa di formazione C ++.
Lettura consigliata
- Struttura Dati Elenco Collegato Circolare In C ++ Con Illustrazione
- Struttura dei dati della lista doppiamente collegata in C ++ con illustrazione
- Struttura dei dati della coda in C ++ con illustrazione
- Stack Struttura Dati In C ++ Con Illustrazione
- Priorità Struttura Dati Coda In C ++ Con Illustrazione
- I 15 migliori strumenti gratuiti per il data mining: l'elenco più completo
- 15 migliori strumenti ETL nel 2021 (un elenco aggiornato completo)
- Introduzione alle strutture dati in C ++