LinkedList-gegevensstructuur

Inhoudsopgave

Vertegenwoordiging van LinkedList
Hulpprogramma voor gekoppelde lijsten
Linked List-implementaties in Python-, Java-, C- en C ++ -voorbeelden
Complexiteit van gekoppelde lijsten
Linked List-applicaties

In deze tutorial leer je over de datastructuur van gekoppelde lijsten en de implementatie ervan in Python, Java, C en C ++.

Een datastructuur van een gekoppelde lijst bevat een reeks verbonden knooppunten. Hier slaat elk knooppunt de gegevens en het adres van het volgende knooppunt op. Bijvoorbeeld,

LinkedList-gegevensstructuur

Je moet ergens beginnen, dus we geven het adres van het eerste knooppunt een speciale naam genaamd HEAD.

Ook kan het laatste knooppunt in de gekoppelde lijst worden geïdentificeerd omdat het volgende deel naar NULL verwijst.

Je hebt misschien het spel Treasure Hunt gespeeld, waarbij elke aanwijzing de informatie over de volgende aanwijzing bevat. Dat is hoe de gekoppelde lijst werkt.

Vertegenwoordiging van LinkedList

Laten we eens kijken hoe elk knooppunt van de LinkedList wordt weergegeven. Elk knooppunt bestaat uit:

Een data-item
Een adres van een ander knooppunt

We verpakken zowel het gegevensitem als de volgende knooppuntverwijzing in een structuur als:

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

Het begrijpen van de structuur van een verbonden lijstknooppunt is de sleutel om het te begrijpen.

Elk struct-knooppunt heeft een data-item en een pointer naar een ander struct-knooppunt. Laten we een eenvoudige gekoppelde lijst maken met drie items om te begrijpen hoe dit werkt.

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

Als je een van de bovenstaande regels niet hebt begrepen, heb je alleen een opfriscursus nodig over pointers en structs.

In slechts een paar stappen hebben we een eenvoudige gekoppelde lijst gemaakt met drie knooppunten.

LinkedList-vertegenwoordiging

De kracht van LinkedList komt van het vermogen om de ketting te doorbreken en er weer aan deel te nemen. Als u bijvoorbeeld een element 4 tussen 1 en 2 wilt plaatsen, zijn de stappen:

Maak een nieuw struct-knooppunt en wijs er geheugen aan toe.
Voeg de gegevenswaarde toe als 4
Wijs de volgende aanwijzer naar het struct-knooppunt met 2 als de gegevenswaarde
Verander de volgende pointer van "1" naar het knooppunt dat we zojuist hebben gemaakt.

Om iets soortgelijks in een array te doen, zouden de posities van alle volgende elementen moeten worden verschoven.

In Python en Java kan de gekoppelde lijst worden geïmplementeerd met behulp van klassen zoals weergegeven in de onderstaande codes.

Hulpprogramma voor gekoppelde lijsten

Lijsten zijn een van de meest populaire en efficiënte datastructuren, met implementatie in elke programmeertaal zoals C, C ++, Python, Java en C #.

Afgezien daarvan zijn gekoppelde lijsten een geweldige manier om te leren hoe pointers werken. Door te oefenen met het manipuleren van gekoppelde lijsten, kunt u uzelf voorbereiden op het leren van meer geavanceerde datastructuren zoals grafieken en bomen.

Linked List-implementaties in Python-, Java-, C- en C ++ -voorbeelden

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