Struktura danych LinkedList

Spisie treści

Reprezentacja LinkedList
Narzędzie listy połączonej
Implementacje list połączonych w przykładach w językach Python, Java, C i C ++
Złożoność listy połączonej
Połączone aplikacje list

W tym samouczku dowiesz się o strukturze danych listy połączonej i jej implementacji w językach Python, Java, C i C ++.

Struktura danych listy połączonej zawiera szereg połączonych węzłów. Tutaj każdy węzeł przechowuje dane i adres następnego węzła. Na przykład,

Struktura danych LinkedList

Musisz gdzieś zacząć, więc nadajemy adresowi pierwszego węzła specjalną nazwę o nazwie HEAD.

Można również zidentyfikować ostatni węzeł na połączonej liście, ponieważ jego następna część wskazuje na NULL.

Mogłeś zagrać w grę Treasure Hunt, w której każda wskazówka zawiera informacje o następnej wskazówce. Tak działa lista połączona.

Reprezentacja LinkedList

Zobaczmy, jak reprezentowany jest każdy węzeł LinkedList. Każdy węzeł składa się z:

Element danych
Adres innego węzła

Zarówno element danych, jak i następne odwołanie do węzła opakowujemy w strukturę jako:

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

Zrozumienie struktury połączonego węzła listy jest kluczem do opanowania go.

Każdy węzeł struktury ma element danych i wskaźnik do innego węzła struktury. Utwórzmy prostą listę połączoną z trzema elementami, aby zrozumieć, jak to działa.

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

Jeśli nie zrozumiałeś żadnej z powyższych linii, potrzebujesz tylko przypomnienia sobie wskaźników i struktur.

W zaledwie kilku krokach utworzyliśmy prostą połączoną listę z trzema węzłami.

Reprezentacja LinkedList

Siła LinkedList polega na możliwości zerwania łańcucha i ponownego dołączenia do niego. Np. Jeśli chciałbyś umieścić element 4 między 1 a 2, kroki byłyby następujące:

Utwórz nowy węzeł struktury i przydziel do niego pamięć.
Dodaj jego wartość jako 4
Wskaż następny wskaźnik na węzeł struktury zawierający 2 jako wartość danych
Zmień następny wskaźnik „1” na węzeł, który właśnie utworzyliśmy.

Zrobienie czegoś podobnego w tablicy wymagałoby przesunięcia pozycji wszystkich kolejnych elementów.

W Pythonie i Javie połączoną listę można zaimplementować za pomocą klas, jak pokazano w kodach poniżej.

Narzędzie listy połączonej

Listy to jedna z najpopularniejszych i najbardziej wydajnych struktur danych, implementowana w każdym języku programowania, takim jak C, C ++, Python, Java i C #.

Poza tym listy połączone to świetny sposób, aby dowiedzieć się, jak działają wskaźniki. Ćwicząc manipulowanie połączonymi listami, możesz przygotować się do nauki bardziej zaawansowanych struktur danych, takich jak wykresy i drzewa.

Implementacje list połączonych w przykładach w językach Python, Java, C i C ++

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