LinkedList adatstruktúra

Tartalomjegyzék

A LinkedList ábrázolása
Összekapcsolt lista segédprogram
Összekapcsolt lista megvalósítások Python, Java, C és C ++ példákban
Összekapcsolt lista összetettsége
Összekapcsolt listás alkalmazások

Ebben az oktatóanyagban megismerheti a csatolt lista adatszerkezetét és annak megvalósítását Pythonban, Java-ban, C-ben és C ++ -on.

A csatolt lista adatstruktúrája összekapcsolt csomópontok sorozatát tartalmazza. Itt minden csomópont tárolja a következő csomópont adatait és címét. Például,

LinkedList adatstruktúra

Valahol el kell kezdened, ezért az első csomópont címének egy speciális nevet adunk, amelyet HEAD-nek hívunk.

Emellett a csatolt lista utolsó csomópontja azonosítható, mert annak következő része a NULL-re mutat.

Lehet, hogy játszottad a Kincsvadászat játékot, ahol minden nyom a következő nyomra vonatkozó információkat tartalmazza. Így működik a linkelt lista.

A LinkedList ábrázolása

Lássuk, hogyan vannak ábrázolva a LinkedList minden csomópontja. Minden csomópont áll:

Adatelem
Egy másik csomópont címe

Az adatelemet és a következő csomópont hivatkozást is egy struktúrába csomagoljuk:

 struct node ( int data; struct node *next; );

A csatolt listacsomópont felépítésének megértése kulcsfontosságú annak megértéséhez.

Minden struktúra csomópontnak van egy adateleme és egy másik struktúra csomópontra mutató mutató. Hozzunk létre egy egyszerű összekapcsolt listát három elemből, hogy megértsük ennek működését.

 /* 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;

Ha a fenti sorok egyikét sem értette, akkor csak a mutatók és a struktúrák frissítésére van szüksége.

Néhány lépésben létrehoztunk egy egyszerű csatolt listát, három csomópontból.

LinkedList képviselet

A LinkedList ereje abban rejlik, hogy képes megszakítani a láncot és újra csatlakozni hozzá. Például, ha a 4 elemet 1 és 2 közé szeretné tenni, a következő lépések lennének:

Hozzon létre egy új struktúra csomópontot, és rendeljen hozzá memóriát.
Adja hozzá adatértékét 4-ként
Mutassa a következő mutatóját a struktúra csomópontra, amely 2-t tartalmaz adatértékként
Változtassa az "1" következő mutatóját az imént létrehozott csomópontra.

Ha valami hasonlót csinál egy tömbben, akkor az összes következő elem helyzetét el kellett volna tolnia.

Pythonban és Java-ban a csatolt lista osztályok segítségével valósítható meg, az alábbi kódok szerint.

Összekapcsolt lista segédprogram

A listák az egyik legnépszerűbb és leghatékonyabb adatstruktúra, amelyet minden programozási nyelven megvalósítanak, például C, C ++, Python, Java és C #.

Ezen kívül a linkelt listák remekül megismerhetik a mutatók működését. A kapcsolt listák kezelésének gyakorlásával felkészülhet arra, hogy fejlettebb adatstruktúrákat, például grafikonokat és fákat tanuljon meg.

Összekapcsolt lista megvalósítások Python, Java, C és C ++ példákban

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; ) )