LinkedList Datastruktur

I denna handledning lär du dig om länkad datastruktur och dess implementering i Python, Java, C och C ++.

En länkad datastruktur för listan innehåller en serie anslutna noder. Här lagrar varje nod data och adressen till nästa nod. Till exempel,

LinkedList Datastruktur

Du måste börja någonstans, så vi ger adressen till den första noden ett särskilt namn som heter HEAD.

Dessutom kan den sista noden i den länkade listan identifieras eftersom dess nästa del pekar på NULL.

Du kanske har spelat spelet Treasure Hunt, där varje ledtråd innehåller information om nästa ledtråd. Så fungerar den länkade listan.

Representation av LinkedList

Låt oss se hur varje nod i LinkedList representeras. Varje nod består:

  • Ett dataobjekt
  • En adress till en annan nod

Vi slår in både dataobjektet och nästa nodreferens i en struktur som:

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

Att förstå strukturen för en länkad listnod är nyckeln till att ha grepp om den.

Varje strukturnod har ett dataobjekt och en pekare till en annan strukturnod. Låt oss skapa en enkel länkad lista med tre objekt för att förstå hur detta fungerar.

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

Om du inte förstod någon av raderna ovan behöver du bara uppdatera pekare och strängar.

På bara några få steg har vi skapat en enkel länkad lista med tre noder.

LinkedList Representation

Kraften i LinkedList kommer från förmågan att bryta kedjan och återansluta den. Om du t.ex. vill sätta ett element 4 mellan 1 och 2 skulle stegen vara:

  • Skapa en ny strukturnod och fördela minne till den.
  • Lägg till dess datavärde som 4
  • Peka sin nästa pekare på strukturnoden som innehåller 2 som datavärde
  • Ändra nästa pekare på "1" till noden vi just skapade.

Att göra något liknande i en array hade krävt att alla efterföljande element flyttades.

I python och Java kan den länkade listan implementeras med hjälp av klasser som visas i koderna nedan.

Länkat listverktyg

Listor är en av de mest populära och effektiva datastrukturerna, med implementering på alla programmeringsspråk som C, C ++, Python, Java och C #.

Bortsett från det är länkade listor ett utmärkt sätt att lära sig hur pekare fungerar. Genom att öva på hur man manipulerar länkade listor kan du förbereda dig för att lära dig mer avancerade datastrukturer som grafer och träd.

Länkade implementeringar i Python, Java, C och C ++ exempel

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

Länkad lista komplexitet

Tidskomplexitet

Värsta fall Genomsnittligt fall
Sök På) På)
Föra in O (1) O (1)
Radering O (1) O (1)

Rymdkomplexitet: O (n)

Länkade applikationer

  • Dynamisk minnestilldelning
  • Implementerad i stack och kö
  • I ångra funktionalitet mjukvaror
  • Hash-tabeller, grafer

Rekommenderade avläsningar

1. Självstudier

  • LinkedList Operations (Travers, Insert, Delete)
  • Typer av LinkedList
  • Java LinkedList

2. Exempel

  • Få mittelementet i LinkedList i en enda iteration
  • Konvertera LinkedList till en Array och vice versa
  • Upptäck slinga i en LinkedList

Intressanta artiklar...