In questo tutorial imparerai a conoscere la struttura dei dati degli elenchi collegati e la sua implementazione in Python, Java, C e C ++.
Una struttura dati di un elenco collegato include una serie di nodi collegati. Qui, ogni nodo memorizza i dati e l'indirizzo del nodo successivo. Per esempio,
Struttura dati LinkedList
Devi iniziare da qualche parte, quindi diamo all'indirizzo del primo nodo un nome speciale chiamato HEAD.
Inoltre, l'ultimo nodo nell'elenco collegato può essere identificato perché la sua parte successiva punta a NULL.
Potresti aver giocato al gioco Treasure Hunt, dove ogni indizio include le informazioni sull'indizio successivo. È così che funziona l'elenco collegato.
Rappresentanza di LinkedList
Vediamo come viene rappresentato ogni nodo della LinkedList. Ogni nodo è composto da:
- Un elemento di dati
- Un indirizzo di un altro nodo
Racchiudiamo sia l'elemento dati che il riferimento al nodo successivo in una struttura come:
struct node ( int data; struct node *next; );
Comprendere la struttura di un nodo di un elenco collegato è la chiave per comprenderlo.
Ogni nodo struct ha un elemento dati e un puntatore a un altro nodo struct. Creiamo un semplice elenco collegato con tre elementi per capire come funziona.
/* 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;
Se non hai capito nessuna delle righe precedenti, tutto ciò di cui hai bisogno è un aggiornamento su puntatori e strutture.
In pochi passaggi, abbiamo creato un semplice elenco collegato con tre nodi.
Rappresentanza LinkedList
Il potere di LinkedList deriva dalla capacità di spezzare la catena e ricongiungersi ad essa. Ad esempio, se volessi mettere un elemento 4 tra 1 e 2, i passaggi sarebbero:
- Crea un nuovo nodo struct e alloca memoria.
- Aggiungi il valore dei dati come 4
- Punta il suo prossimo puntatore al nodo struct contenente 2 come valore di dati
- Cambia il prossimo puntatore di "1" al nodo che abbiamo appena creato.
Fare qualcosa di simile in un array avrebbe richiesto lo spostamento delle posizioni di tutti gli elementi successivi.
In python e Java, l'elenco collegato può essere implementato utilizzando le classi come mostrato nei codici seguenti.
Utilità elenco collegato
Gli elenchi sono una delle strutture dati più popolari ed efficienti, con implementazione in ogni linguaggio di programmazione come C, C ++, Python, Java e C #.
A parte questo, gli elenchi collegati sono un ottimo modo per imparare come funzionano i puntatori. Facendo pratica su come manipolare elenchi collegati, puoi prepararti ad apprendere strutture dati più avanzate come grafici e alberi.
Implementazioni di elenchi collegati in esempi Python, Java, C e 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; ) )
Complessità degli elenchi collegati
Complessità temporale
| Nel peggiore dei casi | Case nella media | |
|---|---|---|
| Ricerca | Su) | Su) |
| Inserire | O (1) | O (1) |
| Cancellazione | O (1) | O (1) |
Complessità spaziale: O (n)
Applicazioni di elenchi collegati
- Allocazione dinamica della memoria
- Implementato in stack e in coda
- In annullamento funzionalità del software
- Tabelle hash, grafici
Letture consigliate
1. Tutorial
- Operazioni LinkedList (Traverse, Inserisci, Elimina)
- Tipi di LinkedList
- Java LinkedList
2. Esempi
- Ottieni l'elemento centrale di LinkedList in una singola iterazione
- Converti la LinkedList in un array e viceversa
- Rileva loop in un LinkedList
