Datová struktura LinkedList

V tomto kurzu se dozvíte o datové struktuře propojeného seznamu a jeho implementaci v Pythonu, Javě, C a C ++.

Datová struktura propojeného seznamu zahrnuje řadu připojených uzlů. Zde každý uzel ukládá data a adresu dalšího uzlu. Například,

Datová struktura LinkedList

Musíte někde začít, takže dáme adrese prvního uzlu speciální název s názvem HEAD.

Také lze identifikovat poslední uzel v propojeném seznamu, protože jeho další část ukazuje na NULL.

Možná jste hráli hru Treasure Hunt, kde každá stopa obsahuje informace o další stopě. Takto funguje propojený seznam.

Reprezentace LinkedList

Podívejme se, jak je znázorněn každý uzel LinkedList. Každý uzel se skládá z:

  • Datová položka
  • Adresa jiného uzlu

Zabalíme datovou položku i odkaz na další uzel do struktury jako:

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

Porozumění struktuře propojeného uzlu seznamu je klíčem k jeho pochopení.

Každý strukturovaný uzel má datovou položku a ukazatel na jiný strukturovaný uzel. Vytvořme jednoduchý propojený seznam se třemi položkami, abychom pochopili, jak to funguje.

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

Pokud jste nerozuměli žádnému z výše uvedených řádků, potřebujete pouze aktualizaci ukazatelů a struktur.

V několika krocích jsme vytvořili jednoduchý propojený seznam se třemi uzly.

Zastoupení LinkedList

Síla LinkedList pochází ze schopnosti rozbít řetězec a znovu se k němu připojit. Například pokud jste chtěli dát prvek 4 mezi 1 a 2, kroky by byly:

  • Vytvořte nový strukturovaný uzel a přidělte mu paměť.
  • Přidejte jeho datovou hodnotu jako 4
  • Namiřte jeho další ukazatel na uzel struktury obsahující 2 jako datovou hodnotu
  • Změňte další ukazatel „1“ na uzel, který jsme právě vytvořili.

Dělat něco podobného v poli by vyžadovalo posunutí pozic všech následujících prvků.

V pythonu a Javě lze propojený seznam implementovat pomocí tříd, jak je uvedeno v níže uvedených kódech.

Propojený seznam Utility

Seznamy jsou jednou z nejpopulárnějších a nejúčinnějších datových struktur s implementací v každém programovacím jazyce, jako jsou C, C ++, Python, Java a C #.

Kromě toho jsou propojené seznamy skvělým způsobem, jak se naučit, jak fungují ukazatele. Procvičováním manipulace s propojenými seznamy se můžete připravit na to, abyste se naučili pokročilejší datové struktury, jako jsou grafy a stromy.

Implementace propojeného seznamu v příkladech Pythonu, Javy, C a 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; ) )

Složitost propojeného seznamu

Časová složitost

Nejhorší případ Průměrný případ
Vyhledávání Na) Na)
Vložit O (1) O (1)
Vymazání O (1) O (1)

Složitost prostoru: O (n)

Propojené aplikace seznamu

  • Dynamické přidělování paměti
  • Implementováno do zásobníku a fronty
  • V undo funkčnost softwarů
  • Hash tabulky, grafy

Doporučené četby

1. Návody

  • Operace LinkedList (procházení, vkládání, mazání)
  • Typy LinkedList
  • Java LinkedList

2. Příklady

  • Získejte prostřední prvek LinkedList v jedné iteraci
  • Převeďte LinkedList na pole a naopak
  • Zjistit smyčku v LinkedList

Zajímavé články...