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,
![](https://cdn.wiki-base.com/1894870/linkedlist_data_structure.png.webp)
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.
![](https://cdn.wiki-base.com/1894870/linkedlist_data_structure_2.png.webp)
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; ) )
Linkitetyn luettelon monimutkaisuus
Ajan monimutkaisuus
Pahimmassa tapauksessa | Keskimääräinen tapaus | |
---|---|---|
Hae | Päällä) | Päällä) |
Lisää | O (1) | O (1) |
Poistaminen | O (1) | O (1) |
Avaruuden monimutkaisuus: O (n)
Linkitetyt luettelosovellukset
- Dynaaminen muistin allokointi
- Toteutettu pinossa ja jonossa
- Vuonna kumoa toiminnallisuus ohjelmistot
- Hash-taulukot, kaaviot
Suositeltavat lukemat
1. Oppaat
- LinkedList-toiminnot (siirto, lisäys, poisto)
- LinkedList-tyypit
- Java LinkedList
2. Esimerkkejä
- Hanki LinkedListin keskiosa yhdellä iteraatiolla
- Muunna LinkedList taulukoksi ja päinvastoin
- Tunnista silmukka LinkedList-luettelossa