Struktura podatkov LinkedList

Kazalo

Predstavitev LinkedList
Pripomoček za povezani seznam
Implementacije povezanih seznamov v primerih Python, Java, C in C ++
Zapletenost povezanega seznama
Aplikacije s povezanim seznamom

V tej vadnici boste izvedeli več o strukturi podatkov povezanega seznama in njeni implementaciji v Python, Java, C in C ++.

Povezana podatkovna struktura seznama vključuje vrsto povezanih vozlišč. Tu vsako vozlišče shrani podatke in naslov naslednjega vozlišča. Na primer

Struktura podatkov LinkedList

Nekje morate začeti, zato naslovu prvega vozlišča damo posebno ime, imenovano HEAD.

Prav tako je mogoče prepoznati zadnje vozlišče na povezanem seznamu, ker njegov naslednji del kaže na NULL.

Morda ste igrali igro Lov na zaklad, kjer vsak namig vsebuje informacije o naslednjem namigu. Tako deluje povezani seznam.

Predstavitev LinkedList

Poglejmo, kako je predstavljeno vsako vozlišče seznama LinkedList. Vsako vozlišče je sestavljeno iz:

Podatkovni element
Naslov drugega vozlišča

Podatkovni element in referenco naslednjega vozlišča zavijemo v strukturo kot:

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

Razumevanje strukture povezanega vozlišča seznama je ključnega pomena za njegovo razumevanje.

Vsako strukturno vozlišče ima podatkovni element in kazalec na drugo strukturno vozlišče. Ustvarimo preprost povezani seznam s tremi elementi, da bomo razumeli, kako to deluje.

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

Če niste razumeli nobene zgornje vrstice, potrebujete samo osvežitev kazalcev in navodil.

V samo nekaj korakih smo ustvarili preprost povezan seznam s tremi vozlišči.

Predstavitev LinkedList

Moč LinkedList izvira iz zmožnosti prekinitve verige in njene ponovne pridružitve. Če bi želeli element 4 postaviti med 1 in 2, bi bili naslednji koraki:

Ustvarite novo strukturno vozlišče in mu dodelite pomnilnik.
Dodajte njegovo podatkovno vrednost kot 4
Naslednji kazalec usmerite na strukturno vozlišče, ki vsebuje 2 kot vrednost podatkov
Spremenite naslednji kazalec "1" na vozlišče, ki smo ga pravkar ustvarili.

Če bi naredili nekaj podobnega v nizu, bi bilo treba premakniti položaje vseh nadaljnjih elementov.

V pythonu in Javi lahko povezani seznam izvedemo z uporabo razredov, kot je prikazano v spodnjih kodah.

Pripomoček za povezani seznam

Seznami so ena najbolj priljubljenih in najučinkovitejših podatkovnih struktur z izvedbo v vseh programskih jezikih, kot so C, C ++, Python, Java in C #.

Poleg tega so povezani seznami odličen način, da se naučite, kako delujejo kazalci. Z vadbo, kako upravljati s povezanimi seznami, se lahko pripravite na učenje naprednejših podatkovnih struktur, kot so grafi in drevesa.

Implementacije povezanih seznamov v primerih Python, Java, C in 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; ) )