LinkedList Datastruktur

I denne vejledning lærer du om tilknyttet liste datastruktur, og dens implementering i Python, Java, C og C ++.

En sammenkædet liste datastruktur inkluderer en række tilsluttede noder. Her gemmer hver node dataene og adressen på den næste node. For eksempel,

LinkedList Datastruktur

Du skal starte et eller andet sted, så vi giver adressen til den første node et specielt navn kaldet HEAD.

Den sidste knude på den linkede liste kan også identificeres, fordi den næste del peger på NULL.

Du har muligvis spillet spillet Treasure Hunt, hvor hver ledetråd indeholder information om den næste ledetråd. Sådan fungerer den sammenkædede liste.

Repræsentation af LinkedList

Lad os se, hvordan hver knude i LinkedList er repræsenteret. Hver knude består af:

  • Et dataelement
  • En adresse på en anden knude

Vi pakker både dataelementet og den næste nodehenvisning i en struktur som:

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

At forstå strukturen i en linket listeknude er nøglen til at have forståelse for den.

Hver struct-node har et dataelement og en markør til en anden struct-node. Lad os oprette en simpel sammenkædet liste med tre emner for at 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 forstod nogen af ​​linjerne ovenfor, er alt, hvad du behøver, en opdatering af pegepinde og bånd.

På få trin har vi oprettet en simpel sammenkædet liste med tre noder.

LinkedList Repræsentation

Kraften i LinkedList kommer fra evnen til at bryde kæden og slutte sig til den igen. F.eks. Hvis du vil sætte et element 4 mellem 1 og 2, vil trinnene være:

  • Opret en ny strukturknude og tildel hukommelse til den.
  • Tilføj dens dataværdi som 4
  • Peg den næste markør mod struct-noden, der indeholder 2 som dataværdien
  • Skift den næste markør på "1" til den node, vi lige har oprettet.

At gøre noget lignende i en matrix ville have krævet at flytte positionerne for alle de efterfølgende elementer.

I python og Java kan den linkede liste implementeres ved hjælp af klasser som vist i nedenstående koder.

Tilknyttet listeværktøj

Lister er en af ​​de mest populære og effektive datastrukturer med implementering i hvert programmeringssprog som C, C ++, Python, Java og C #.

Bortset fra det er sammenkædede lister en fantastisk måde at lære, hvordan markører fungerer. Ved at øve dig på, hvordan man manipulerer sammenkædede lister, kan du forberede dig på at lære mere avancerede datastrukturer som grafer og træer.

Implementeringer af sammenkædede lister i eksempler på Python, Java, C og C ++

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

Sammenkædet listekompleksitet

Tidskompleksitet

Værste tilfælde Gennemsnitlig sag
Søg På) På)
Indsæt O (1) O (1)
Sletning O (1) O (1)

Rumkompleksitet: O (n)

Tilknyttede listeapplikationer

  • Dynamisk hukommelsesallokering
  • Implementeret i stak og kø
  • I fortryd funktionalitet software
  • Hash-tabeller, grafer

Anbefalede målinger

1. Selvstudier

  • LinkedList-operationer (gennemløb, indsæt, slet)
  • Typer af LinkedList
  • Java LinkedList

2. Eksempler

  • Få det midterste element i LinkedList i en enkelt iteration
  • Konverter LinkedList til en matrix og omvendt
  • Registrer sløjfe i en LinkedList

Interessante artikler...