LinkedList andmestruktuur

Lang L: none (table-of-contents)

LinkedListi esindus
Lingitud loendi utiliit
Lingitud loendite rakendused Pythoni, Java, C ja C ++ näidetes
Lingitud loendi keerukus
Lingitud loendirakendused

Selles õpetuses saate teada lingitud loendi andmestruktuurist ja selle rakendamisest Pythonis, Java-s, C-s ja C ++ -is.

Lingitud loendi andmestruktuur sisaldab ühendatud sõlmede rida. Siin salvestavad kõik sõlmed järgmise sõlme andmed ja aadressi. Näiteks,

LinkedList andmestruktuur

Kusagilt peate alustama, seega anname esimese sõlme aadressile spetsiaalse nime HEAD.

Samuti saab lingitud loendi viimase sõlme tuvastada, kuna selle järgmine osa osutab NULL-le.

Võimalik, et olete mänginud mängu Aardejaht, kus iga vihje sisaldab teavet järgmise vihje kohta. Nii toimib lingitud loend.

LinkedListi esindus

Vaatame, kuidas on kõik LinkedListi sõlmed esindatud. Iga sõlm koosneb:

Andmeüksus
Teise sõlme aadress

Pakime nii andmeüksuse kui ka järgmise sõlme viite struktuuri järgmiselt:

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

Lingitud loendisõlme struktuuri mõistmine on võti selle mõistmiseks.

Igal struktuurisõlmel on andmeüksus ja osuti teisele struktuurisõlmele. Selle toimimise mõistmiseks koostame kolme elemendiga lihtsa lingitud loendi.

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

Kui te ei saanud aru ühestki ülalolevast joonest, on vaja ainult näpunäidete ja joonte värskendamist.

Mõne sammuga oleme loonud lihtsa kolme sõlmega lingitud loendi.

LinkedList'i esindus

LinkedListi jõud tuleneb võimest ahel katkestada ja sellega uuesti liituda. Näiteks kui soovite panna elemendi 4 vahemikku 1 kuni 2, toimige järgmiselt.

Looge uus strukturisõlm ja eraldage sellele mälu.
Lisage selle andmeväärtus väärtuseks 4
Suunake oma järgmine osuti struktuurisõlmele, mis sisaldab andmeväärtusena 2
Muutke "1" järgmine osuti äsja loodud sõlme vastu.

Massiivis midagi sarnast tehes oleks vaja olnud kõigi järgnevate elementide positsioone nihutada.

Pythonis ja Java-s saab lingitud loendi rakendada klasside abil, nagu on näidatud allpool toodud koodides.

Lingitud loendi utiliit

Loendid on üks populaarsemaid ja tõhusamaid andmestruktuure, mida saab rakendada igas programmeerimiskeeles, nagu C, C ++, Python, Java ja C #.

Peale selle on lingitud loendid suurepärane võimalus õppida, kuidas osutajad töötavad. Harjutades lingitud loenditega manipuleerimist, saate end ette valmistada õppima täpsemaid andmestruktuure nagu graafikud ja puud.

Lingitud loendite rakendused Pythoni, Java, C ja C ++ näidetes

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