linked list data structure c with illustration
Szczegółowe badanie listy połączonej w C ++.
Lista połączona to liniowa dynamiczna struktura danych do przechowywania elementów danych. Tablice widzieliśmy już w naszych poprzednich tematach dotyczących podstawowego języka C ++. Wiemy również, że tablice to liniowa struktura danych przechowująca elementy danych w sąsiadujących lokalizacjach.
W przeciwieństwie do tablic połączona lista nie przechowuje elementów danych w ciągłych lokalizacjach pamięci.
Lista połączona składa się z elementów zwanych „węzłami”, które zawierają dwie części. Pierwsza część zawiera rzeczywiste dane, a druga część zawiera wskaźnik wskazujący na następny węzeł. Taka struktura jest zwykle nazywana „Listą pojedynczo połączoną”.
=> Sprawdź najlepsze samouczki szkoleniowe C ++ tutaj.
Czego się nauczysz:
Lista połączona w C ++
W tym samouczku przyjrzymy się szczegółowo liście połączonej pojedynczo.
Poniższy diagram przedstawia strukturę listy połączonej pojedynczo.
Jak pokazano powyżej, pierwszy węzeł połączonej listy nazywany jest „głową”, a ostatni węzeł nazywany jest „końcem”. Jak widzimy, ostatni węzeł połączonej listy będzie miał swój następny wskaźnik jako pusty, ponieważ nie będzie miał wskazanego adresu pamięci.
Ponieważ każdy węzeł ma wskaźnik do następnego węzła, elementy danych na połączonej liście nie muszą być przechowywane w sąsiadujących lokalizacjach. Węzły mogą być rozproszone w pamięci. Możemy uzyskać dostęp do węzłów w dowolnym momencie, ponieważ każdy węzeł będzie miał adres następnego węzła.
Możemy dodawać elementy danych do połączonej listy, a także łatwo usuwać elementy z listy. W ten sposób można dynamicznie powiększać lub zmniejszać połączoną listę. Nie ma górnego limitu liczby elementów danych, które mogą znajdować się na połączonej liście. Tak długo, jak dostępna jest pamięć, możemy dodać dowolną liczbę elementów danych do połączonej listy.
Oprócz łatwego wstawiania i usuwania, połączona lista nie marnuje również miejsca w pamięci, ponieważ nie musimy wcześniej określać, ile elementów potrzebujemy na połączonej liście. Jedyne miejsce zajmowane przez połączoną listę służy do przechowywania wskaźnika do następnego węzła, co dodaje trochę narzutu.
Następnie omówimy różne operacje, które można wykonać na połączonej liście.
Operacje
Podobnie jak w przypadku innych struktur danych, możemy również wykonywać różne operacje dla połączonej listy. Ale w przeciwieństwie do tablic, w których możemy uzyskać dostęp do elementu bezpośrednio za pomocą indeksu dolnego, nawet jeśli znajduje się gdzieś pomiędzy, nie możemy zrobić tego samego losowego dostępu z połączoną listą.
Aby uzyskać dostęp do dowolnego węzła, musimy przejść przez połączoną listę od początku i dopiero wtedy możemy uzyskać dostęp do żądanego węzła. W związku z tym losowy dostęp do danych z połączonej listy okazuje się kosztowny.
Możemy wykonywać różne operacje na połączonej liście, jak podano poniżej:
# 1) Wstawianie
Operacja wstawienia połączonej listy dodaje element do połączonej listy. Chociaż może się to wydawać proste, biorąc pod uwagę strukturę połączonej listy, wiemy, że za każdym razem, gdy element danych jest dodawany do połączonej listy, musimy zmienić następne wskaźniki poprzedniego i następnego węzła nowego elementu, który wstawiliśmy.
Drugą rzeczą, którą musimy wziąć pod uwagę, jest miejsce, w którym ma zostać dodany nowy element danych.
Na połączonej liście znajdują się trzy pozycje, do których można dodać element danych.
# 1) Na początku połączonej listy
Połączona lista jest pokazana poniżej 2-> 4-> 6-> 8-> 10. Jeśli chcemy dodać nowy węzeł 1, jako pierwszy węzeł na liście, wówczas głowa wskazująca na węzeł 2 będzie teraz wskazywała 1, a następny wskaźnik węzła 1 będzie miał adres pamięci węzła 2, jak pokazano poniżej postać.
W ten sposób nowa połączona lista zmieni się na 1-> 2-> 4-> 6-> 8-> 10.
# 2) Po danym Node
Tutaj podany jest węzeł i musimy dodać nowy węzeł po danym węźle. Na liście poniżej połączonej a-> b-> c-> d -> e, jeśli chcemy dodać węzeł f po węźle c, połączona lista będzie wyglądać następująco:
Zatem na powyższym schemacie sprawdzamy, czy dany węzeł jest obecny. Jeśli jest obecny, tworzymy nowy węzeł f. Następnie wskazujemy następny wskaźnik węzła c, aby wskazywał na nowy węzeł f. Następny wskaźnik węzła f wskazuje teraz na węzeł d.
# 3) Na końcu listy połączonej
W trzecim przypadku dodajemy nowy węzeł na końcu połączonej listy. Rozważmy, że mamy tę samą połączoną listę a-> b-> c-> d-> e i musimy dodać węzeł f na końcu listy. Po dodaniu węzła połączona lista będzie wyglądać tak, jak pokazano poniżej.
W ten sposób tworzymy nowy węzeł f. Następnie wskaźnik ogonowy wskazujący na zero jest skierowany na f, a następny wskaźnik węzła f jest skierowany na zero. Zaimplementowaliśmy wszystkie trzy typy funkcji wstawiania w poniższym programie C ++.
W C ++ możemy zadeklarować połączoną listę jako strukturę lub klasę. Deklarowanie listy połączonej jako struktury jest tradycyjną deklaracją w stylu C. Lista połączona jako klasa jest używana w nowoczesnym C ++, głównie podczas korzystania ze standardowej biblioteki szablonów.
W poniższym programie użyliśmy struktury do zadeklarowania i utworzenia połączonej listy. Będzie miał dane i wskaźnik do następnego elementu jako swoich członków.
#include using namespace std; // A linked list node struct Node { int data; struct Node *next; }; //insert a new node in front of the list void push(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; /* 2. assign data to node */ newNode->data = node_data; /* 3. set next of new node as head */ newNode->next = (*head); /* 4. move the head to point to the new node */ (*head) = newNode; } //insert new node after a given node void insertAfter(struct Node* prev_node, int node_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { coutnext = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = newNode; } /* insert new node at the end of the linked list */ void append(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; struct Node *last = *head; /* used in step 5*/ /* 2. assign data to the node */ newNode->data = node_data; /* 3. set next pointer of new node to null as its the last node*/ newNode->next = NULL; /* 4. if list is empty, new node becomes first node */ if (*head == NULL) { *head = newNode; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = newNode; return; } // display linked list contents void displayList(struct Node *node) { //traverse the list to display each node while (node != NULL) { coutnext; } if(node== NULL) cout Wynik:
Ostateczna lista połączona:
30–> 20–> 50–> 10–> 40–> brak
Następnie implementujemy operację wstawiania listy połączonej w Javie. W języku Java połączona lista jest implementowana jako klasa. Poniższy program jest podobny logicznie do programu w C ++, jedyną różnicą jest to, że używamy klasy dla połączonej listy.
class LinkedList { Node head; // head of list //linked list node declaration class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Insert a new node at the front of the list */ public void push(int new_data) { //allocate and assign data to the node Node newNode = new Node(new_data); //new node becomes head of linked list newNode.next = head; //head points to new node head = newNode; } // Given a node,prev_node insert node after prev_node public void insertAfter(Node prev_node, int new_data) { //check if prev_node is null. if (prev_node == null) { System.out.println('The given node is required and cannot be null'); return; } //allocate node and assign data to it Node newNode = new Node(new_data); //next of new Node is next of prev_node newNode.next = prev_node.next; //prev_node->next is the new node. prev_node.next = newNode; } //inserts a new node at the end of the list public void append(intnew_data) { //allocate the node and assign data Node newNode = new Node(new_data); //if linked list is empty, then new node will be the head if (head == null) { head = new Node(new_data); return; } //set next of new node to null as this is the last node newNode.next = null; // if not the head node traverse the list and add it to the last Node last = head; while (last.next != null) last = last.next; //next of last becomes new node last.next = newNode; return; } //display contents of linked list public void displayList() { Node pnode = head; while (pnode != null) { System.out.print(pnode.data+'-->'); pnode = pnode.next; } if(pnode == null) System.out.print('null'); } } //Main class to call linked list class functions and construct a linked list class Main{ public static void main(String() args) { /* create an empty list */ LinkedList lList = new LinkedList(); // Insert 40. lList.append(40); // Insert 20 at the beginning. lList.push(20); // Insert 10 at the beginning. lList.push(10); // Insert 50 at the end. lList.append(50); // Insert 30, after 20. lList.insertAfter(lList.head.next, 30); System.out.println('
Final linked list: '); lList. displayList (); } } Wynik:
ETL pytania i odpowiedzi na rozmowę kwalifikacyjną pdf
Ostateczna lista połączona:
10–> 20–> 30–> 40–> 50–> brak
Zarówno w powyższym programie, C ++, jak iw Javie, mamy oddzielne funkcje dodawania węzła przed listą, na końcu listy oraz między listami podanymi w węźle. Na koniec drukujemy zawartość listy utworzonej wszystkimi trzema metodami.
# 2) Usunięcie
Podobnie jak w przypadku wstawiania, usuwanie węzła z połączonej listy również obejmuje różne pozycje, z których można usunąć węzeł. Możemy usunąć pierwszy węzeł, ostatni węzeł lub losowy węzeł k-ty z połączonej listy. Po usunięciu musimy odpowiednio dostosować następny wskaźnik i inne wskaźniki na połączonej liście, aby zachować połączoną listę nienaruszoną.
W poniższej implementacji C ++ podaliśmy dwie metody usuwania, tj. Usunięcie pierwszego węzła na liście i usunięcie ostatniego węzła na liście. Najpierw tworzymy listę, dodając węzły do głowy. Następnie wyświetlamy zawartość listy po wstawieniu i każdym usunięciu.
#include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; //delete first node in the linked list Node* deleteFirstNode(struct Node* head) { if (head == NULL) return NULL; // Move the head pointer to the next node Node* tempNode = head; head = head->next; delete tempNode; return head; } //delete last node from linked list Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // first find second last node Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete the last node delete (second_last->next); // set next of second_last to null second_last->next = NULL; return head; } // create linked list by adding nodes at head void push(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode; } // main function int main() { /* Start with the empty list */ Node* head = NULL; // create linked list push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<'Linked list created ' Wynik:
Utworzono listę połączoną
10–> 8–> 6–> 4–> 2–
> NULL
Lista połączona po usunięciu węzła głównego
8–> 6–> 4–> 2–
> NULL
Lista połączona po usunięciu ostatniego węzła
8–> 6–> 4–> NULL
Dalej jest implementacja Java do usuwania węzłów z połączonej listy. Logika implementacji jest taka sama, jak w programie C ++. Jedyną różnicą jest to, że połączona lista jest zadeklarowana jako klasa.
class Main { // Linked list node / static class Node { int data; Node next; }; // delete first node of linked list static Node deleteFirstNode(Node head) { if (head == null) return null; // Move the head pointer to the next node Node temp = head; head = head.next; return head; } // Delete the last node in linked list static Node deleteLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // search for second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // set next of second last to null second_last.next = null; return head; } // Add nodes to the head and create linked list static Node push(Node head, int new_data) { Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head; } //main function public static void main(String args()) { // Start with the empty list / Node head = null; //create linked list head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println('Linked list created :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteFirstNode(head); System.out.println('Linked list after deleting head node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteLastNode(head); System.out.println('Linked list after deleting last node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); } } Wynik:
Utworzono połączoną listę:
9–> 7–> 5–> 3–> 1–
> null
Lista połączona po usunięciu węzła głównego:
7–> 5–> 3–> 1–
> null
Lista połączona po usunięciu ostatniego węzła:
7–> 5–> 3–> zero
Policz liczbę węzłów
Operację zliczania liczby węzłów można wykonać podczas przeglądania połączonej listy. W powyższej implementacji widzieliśmy już, że ilekroć musimy wstawić / usunąć węzeł lub wyświetlić zawartość połączonej listy, musimy przejść przez połączoną listę od początku.
Utrzymanie licznika i zwiększanie go podczas przechodzenia przez każdy węzeł da nam liczbę węzłów obecnych na połączonej liście. Pozostawimy ten program czytelnikom do wdrożenia.
Tablice i połączone listy
Po obejrzeniu operacji i implementacji połączonej listy, porównajmy, jak tablice i połączona lista są sprawiedliwe w porównaniu ze sobą.
Tablice Połączone listy Tablice mają stały rozmiar Rozmiar listy połączonej jest dynamiczny Wstawienie nowego elementu jest kosztowne Wstawianie / usuwanie jest łatwiejsze Dostęp losowy jest dozwolony Losowy dostęp nie jest możliwy Elementy są w ciągłym miejscu Elementy mają nieciągłe położenie Nie jest wymagane dodatkowe miejsce na następny wskaźnik Dodatkowa przestrzeń pamięci wymagana dla następnego wskaźnika
Aplikacje
Ponieważ zarówno tablice, jak i połączone listy są używane do przechowywania elementów i są liniowymi strukturami danych, obie te struktury mogą być używane w podobny sposób w większości aplikacji.
Oto niektóre aplikacje do list połączonych:
- Połączona lista może służyć do implementowania stosów i kolejek.
- Lista połączona może być również używana do implementacji wykresów, ilekroć musimy przedstawić wykresy jako listy sąsiedztwa.
- Wielomian matematyczny można przechowywać jako połączoną listę.
- W przypadku techniki mieszania zasobniki używane do mieszania są implementowane przy użyciu połączonych list.
- Zawsze, gdy program wymaga dynamicznej alokacji pamięci, możemy użyć listy połączonej, ponieważ w tym przypadku listy połączone działają wydajniej.
Wniosek
Połączone listy to struktury danych, które są używane do przechowywania elementów danych w sposób liniowy, ale w nieciągłych lokalizacjach. Lista połączona to zbiór węzłów, które zawierają część danych i następny wskaźnik, który zawiera adres pamięci następnego elementu na liście.
Ostatni element na liście ma swój następny wskaźnik ustawiony na NULL, co oznacza koniec listy. Pierwszy element listy to Głowa. Lista połączona obsługuje różne operacje, takie jak wstawianie, usuwanie, przechodzenie, itp. W przypadku dynamicznej alokacji pamięci listy połączone są preferowane zamiast tablic.
Listy połączone są drogie, jeśli chodzi o ich przechodzenie, ponieważ nie możemy uzyskać losowego dostępu do elementów, takich jak tablice. Jednak operacje wstawiania i usuwania są tańsze w porównaniu z tablicami.
W tym samouczku dowiedzieliśmy się wszystkiego o listach połączonych liniowo. Połączone listy mogą być również okrągłe lub podwójne. Dokładnie przyjrzymy się tym listom w naszych nadchodzących samouczkach.
=> Sprawdź tutaj pełną serię szkoleń C ++
rekomendowane lektury
- Struktura danych listy połączonej cyklicznie w C ++ z ilustracją
- Struktura danych listy podwójnie połączonych w C ++ z ilustracjami
- Struktura danych kolejki w C ++ z ilustracjami
- Struktura danych stosu w C ++ z ilustracjami
- Struktura danych kolejki priorytetowej w C ++ z ilustracjami
- 15 najlepszych darmowych narzędzi do wyszukiwania danych: najbardziej kompleksowa lista
- 15 najlepszych narzędzi ETL w 2021 roku (pełna zaktualizowana lista)
- Wprowadzenie do struktur danych w C ++