LinkedList Datastruktur

Innholdsfortegnelse

Representasjon av LinkedList
Koblet listeverktøy
Koblede listeimplementasjoner i Python, Java, C og C ++ eksempler
Sammenkoblet listekompleksitet
Søknader om koblede lister

I denne opplæringen vil du lære om koblet listedatastruktur og implementeringen i Python, Java, C og C ++.

En datastruktur for en koblet liste inkluderer en rekke tilkoblede noder. Her lagrer hver node dataene og adressen til neste node. For eksempel,

LinkedList Datastruktur

Du må begynne et sted, så vi gir adressen til den første noden et spesielt navn som heter HEAD.

Også den siste noden i den koblede listen kan identifiseres fordi den neste delen peker mot NULL.

Du har kanskje spilt spillet Treasure Hunt, hvor hver ledetråd inneholder informasjon om neste ledetråd. Slik fungerer den koblede listen.

Representasjon av LinkedList

La oss se hvordan hver node i LinkedList er representert. Hver node består av:

Et dataelement
En adresse til en annen node

Vi vikler både dataelementet og neste nodehenvisning i en struktur som:

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

Å forstå strukturen til en koblet listenode er nøkkelen til å ha tak i den.

Hver struct-node har et dataelement og en peker til en annen struct-node. La oss lage en enkel koblet liste med tre elementer for å forstå hvordan dette fungerer.

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

Hvis du ikke forsto noen av linjene ovenfor, er alt du trenger en forfriskning på pekere og bånd.

På bare noen få trinn har vi opprettet en enkel koblet liste med tre noder.

LinkedList Representasjon

Kraften til LinkedList kommer fra evnen til å bryte kjeden og bli med i den. Hvis du f.eks. Vil sette et element 4 mellom 1 og 2, vil trinnene være:

Opprett en ny strukturknute og tildel minne til den.
Legg til dataverdien som 4
Pek neste peker mot strukturenoden som inneholder 2 som dataverdi
Endre neste peker på "1" til noden vi nettopp opprettet.

Å gjøre noe lignende i en matrise ville ha krevd forskyvning av posisjonene til alle de påfølgende elementene.

I python og Java kan den koblede listen implementeres ved hjelp av klasser som vist i kodene nedenfor.

Koblet listeverktøy

Lister er en av de mest populære og effektive datastrukturene, med implementering i alle programmeringsspråk som C, C ++, Python, Java og C #.

Bortsett fra det, er lenkede lister en fin måte å lære hvordan pekere fungerer. Ved å øve deg på å manipulere koblede lister, kan du forberede deg på å lære mer avanserte datastrukturer som grafer og trær.

Koblede listeimplementasjoner i Python, Java, C og C ++ eksempler

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