LinkedList-tietorakenne

Tässä opetusohjelmassa opit linkitetyn luettelon tietorakenteesta ja sen toteuttamisesta Pythonissa, Javassa, C: ssä ja C ++: ssa.

Linkitetyn luettelon tietorakenne sisältää sarjan yhdistettyjä solmuja. Tässä kukin solmu tallentaa seuraavan solmun tiedot ja osoitteen. Esimerkiksi,

Sinun on aloitettava jostakin, joten annamme ensimmäisen solmun osoitteelle erityisnimen nimeltä HEAD.

Myös linkitetyn luettelon viimeinen solmu voidaan tunnistaa, koska sen seuraava osa osoittaa NULL-kohtaan.

Olet ehkä pelannut peliä Treasure Hunt, jossa jokainen vihje sisältää tiedot seuraavasta vihjeestä. Näin linkitetty luettelo toimii.

LinkedListin esitys

Katsotaanpa, miten kukin LinkedList-solmu on esitetty. Jokainen solmu koostuu:

Tieto
Toisen solmun osoite

Kääritämme sekä tietoalueen että seuraavan solmuviitteen rakenteeseen seuraavasti:

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

Linkitetyn luettelosolmun rakenteen ymmärtäminen on avain siihen käsitykseen.

Jokaisella rakennesolmulla on tietoalkio ja osoitin toiseen rakennesolmuun. Luodaan yksinkertainen linkitetty luettelo, jossa on kolme kohdetta, jotta ymmärrämme tämän toiminnan.

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

Jos et ymmärtänyt yhtään yllä olevista viivoista, tarvitset vain päivityksen osoittimiin ja viitteisiin.

Muutamassa vaiheessa olemme luoneet yksinkertaisen linkitetyn luettelon, jossa on kolme solmua.

LinkedList-edustus

LinkedListin voima tulee kyvystä katkaista ketju ja liittyä siihen uudelleen. Esimerkiksi, jos haluat laittaa elementin 4 väliin 1 ja 2, vaiheet ovat:

Luo uusi rakennesolmu ja allokoi sille muisti.
Lisää sen data-arvoksi 4
Osoita seuraava osoitin rakennesolmulle, joka sisältää 2 data-arvona
Vaihda "1" seuraava osoitin juuri luomallemme solmulle.

Jotain samanlaista tekeminen taulukossa olisi edellyttänyt kaikkien seuraavien elementtien sijaintien siirtämistä.

Pythonissa ja Java: ssa linkitetty luettelo voidaan toteuttaa käyttämällä luokkia alla olevien koodien mukaisesti.

Linkitetty luetteloapuohjelma

Luettelot ovat yksi suosituimmista ja tehokkaimmista tietorakenteista, ja ne voidaan toteuttaa kaikilla ohjelmointikielillä, kuten C, C ++, Python, Java ja C #.

Sen lisäksi linkitetyt luettelot ovat loistava tapa oppia, miten osoittimet toimivat. Harjoittelemalla linkitettyjen luetteloiden käsittelyä voit valmistautua oppimaan edistyneempiä tietorakenteita, kuten kaavioita ja puita.

Linkitetyt luettelototeutukset Python-, Java-, C- ja C ++ -esimerkkeissä

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