În acest tutorial, veți afla despre structura de date a listelor legate și implementarea acesteia în Python, Java, C și C ++.
O structură de date a listelor legate include o serie de noduri conectate. Aici, fiecare nod stochează datele și adresa următorului nod. De exemplu,
Structura datelor LinkedList
Trebuie să începeți de undeva, așa că dăm adresei primului nod un nume special numit HEAD.
De asemenea, ultimul nod din lista legată poate fi identificat deoarece următoarea sa porțiune indică NULL.
S-ar putea să fi jucat jocul Treasure Hunt, unde fiecare indiciu include informații despre următorul indiciu. Așa funcționează lista legată.
Reprezentarea LinkedList
Să vedem cum este reprezentat fiecare nod din LinkedList. Fiecare nod constă:
- Un element de date
- O adresă a altui nod
Înfășurăm atât elementul de date, cât și următoarea referință de nod într-o structură ca:
struct node ( int data; struct node *next; );
Înțelegerea structurii unui nod listat este cheia pentru a înțelege.
Fiecare nod struct are un element de date și un pointer către un alt nod struct. Permiteți-ne să creăm o listă simplă cu trei elemente pentru a înțelege cum funcționează acest lucru.
/* 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;
Dacă nu ați înțeles niciuna dintre liniile de mai sus, tot ce aveți nevoie este o reîmprospătare a indicatorilor și structurilor.
În doar câțiva pași, am creat o listă simplă legată cu trei noduri.
Reprezentare LinkedList
Puterea LinkedList vine din abilitatea de a sparge lanțul și de a-l reintegra. De exemplu, dacă doriți să puneți un element 4 între 1 și 2, pașii ar fi:
- Creați un nou nod struct și alocați-i memoria.
- Adăugați valoarea de date ca 4
- Îndreptați următorul său indicator către nodul struct care conține 2 ca valoare a datelor
- Schimbați următorul indicator al „1” cu nodul pe care tocmai l-am creat.
A face ceva similar într-o matrice ar fi necesitat schimbarea pozițiilor tuturor elementelor ulterioare.
În Python și Java, lista legată poate fi implementată folosind clase așa cum se arată în codurile de mai jos.
Utilizator Listă legată
Listele sunt una dintre cele mai populare și eficiente structuri de date, cu implementare în fiecare limbaj de programare precum C, C ++, Python, Java și C #.
În afară de asta, listele legate sunt o modalitate excelentă de a afla cum funcționează indicii. Exersând modul de manipulare a listelor conectate, vă puteți pregăti pentru a învăța structuri de date mai avansate, cum ar fi grafice și arbori.
Implementări ale listelor legate în exemplele Python, 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; ) )
Complexitate listă legată
Complexitatea timpului
| Cel mai rău caz | Caz mediu | |
|---|---|---|
| Căutare | Pe) | Pe) |
| Introduce | O (1) | O (1) |
| Ștergere | O (1) | O (1) |
Complexitate spațială: O (n)
Aplicații pentru lista conectată
- Alocare dinamică a memoriei
- Implementat în stivă și în coadă
- În anularea funcționalității software-urilor
- Hash tabele, Grafice
Lecturi recomandate
1. Tutoriale
- Operațiuni LinkedList (traversare, inserare, ștergere)
- Tipuri de LinkedList
- Java LinkedList
2. Exemple
- Obțineți elementul de mijloc al LinkedList într-o singură iterație
- Convertiți LinkedList într-o matrice și invers
- Detectați bucla într-o LinkedList
