linked list data structure c with illustration
Podrobná studie propojeného seznamu v C ++.
Propojený seznam je lineární dynamická datová struktura pro ukládání datových položek. Pole jsme již viděli v našich předchozích tématech na základním C ++. Víme také, že pole jsou lineární datová struktura, která ukládá datové položky na sousedních místech.
Na rozdíl od polí propojený seznam neukládá datové položky do souvislých paměťových míst.
Propojený seznam se skládá z položek zvaných „Uzly“, které obsahují dvě části. První část ukládá skutečná data a druhá část má ukazatel, který ukazuje na další uzel. Tato struktura se obvykle nazývá „Singly linked list“.
=> Podívejte se na nejlepší výukové kurzy C ++ zde.
Co se naučíte:
Propojený seznam v C ++
V tomto tutoriálu se podrobně podíváme na jednotlivě propojený seznam.
Následující diagram ukazuje strukturu jednotlivě propojeného seznamu.
Jak je uvedeno výše, první uzel propojeného seznamu se nazývá „hlava“, zatímco poslední uzel se nazývá „Ocas“. Jak vidíme, poslední uzel propojeného seznamu bude mít svůj další ukazatel jako null, protože nebude mít žádnou adresovanou paměť.
Protože každý uzel má ukazatel na další uzel, datové položky v propojeném seznamu nemusí být ukládány na sousedící místa. Uzly mohou být rozptýleny v paměti. K uzlům můžeme přistupovat kdykoli, protože každý uzel bude mít adresu dalšího uzlu.
Můžeme přidat datové položky do propojeného seznamu a také položky ze seznamu snadno odstranit. Je tedy možné propojený seznam dynamicky zvětšit nebo zmenšit. Neexistuje žádný horní limit, kolik datových položek může být v propojeném seznamu. Dokud je k dispozici paměť, můžeme do propojeného seznamu přidat tolik datových položek.
Kromě snadného vložení a odstranění propojený seznam také neztrácí paměťový prostor, protože předem nemusíme určovat, kolik položek v propojeném seznamu potřebujeme. Jediné místo, které zabírá propojený seznam, je pro uložení ukazatele na další uzel, který přidává malou režii.
Dále budeme diskutovat o různých operacích, které lze provést na propojeném seznamu.
Operace
Stejně jako ostatní datové struktury můžeme pro propojený seznam provádět různé operace. Ale na rozdíl od polí, ve kterých můžeme přímo přistupovat k prvku pomocí dolního indexu, i když je někde mezi nimi, nemůžeme provést stejný náhodný přístup s propojeným seznamem.
Abychom mohli získat přístup k jakémukoli uzlu, musíme od začátku procházet propojeným seznamem a teprve potom můžeme přistupovat k požadovanému uzlu. Náhodný přístup k datům z propojeného seznamu se tedy ukazuje jako nákladný.
Na propojeném seznamu můžeme provádět různé operace, jak je uvedeno níže:
# 1) Vložení
Operace vložení propojeného seznamu přidá položku do propojeného seznamu. I když to může znít jednoduše, vzhledem ke struktuře propojeného seznamu víme, že kdykoli je do propojeného seznamu přidána datová položka, musíme změnit další ukazatele předchozího a následujícího uzlu nové položky, kterou jsme vložili.
Druhá věc, kterou musíme vzít v úvahu, je místo, kde má být přidána nová datová položka.
V propojeném seznamu jsou tři pozice, kam lze přidat datovou položku.
# 1) Na začátku propojeného seznamu
Propojený seznam je zobrazen níže 2-> 4-> 6-> 8-> 10. Pokud chceme přidat nový uzel 1, jako první uzel seznamu, pak hlava směřující k uzlu 2 bude nyní ukazovat na 1 a další ukazatel uzlu 1 bude mít adresu paměti uzlu 2, jak je znázorněno níže postava.
jak psát testovací případ v aplikaci Excel
Nový propojený seznam se tak stává 1-> 2-> 4-> 6-> 8-> 10.
# 2) Po daném uzlu
Zde je uveden uzel a za daným uzlem musíme přidat nový uzel. V níže připojeném seznamu a-> b-> c-> d -> e, pokud chceme přidat uzel f za uzel c, bude propojený seznam vypadat takto:
Ve výše uvedeném diagramu tedy zkontrolujeme, zda je daný uzel přítomen. Pokud je přítomen, vytvoříme nový uzel f. Potom nasměrujeme další ukazatel uzlu c tak, aby ukazoval na nový uzel f. Další ukazatel uzlu f nyní ukazuje na uzel d.
# 3) Na konci propojeného seznamu
Ve třetím případě přidáme nový uzel na konec propojeného seznamu. Zvažte, že máme stejný propojený seznam a-> b-> c-> d-> e a na konec seznamu musíme přidat uzel f. Propojený seznam bude po přidání uzlu vypadat níže.
Vytvoříme tedy nový uzel f. Pak ocasový ukazatel směřující k null je namířen na f a další ukazatel uzlu f je nasměrován na null. Implementovali jsme všechny tři typy vkládacích funkcí v níže uvedeném programu C ++.
V C ++ můžeme deklarovat propojený seznam jako strukturu nebo jako třídu. Deklarace propojeného seznamu jako struktury je tradiční deklarace ve stylu C. Propojený seznam jako třída se používá v moderním C ++, většinou při použití standardní knihovny šablon.
V následujícím programu jsme použili strukturu k deklaraci a vytvoření propojeného seznamu. Bude mít data a ukazatel na další prvek jako jeho členy.
#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 Výstup:
Konečný propojený seznam:
30–> 20–> 50–> 10–> 40–> null
Dále implementujeme operaci vloženého propojeného seznamu v Javě. V jazyce Java je propojený seznam implementován jako třída. Níže uvedený program je logicky podobný programu C ++, jediný rozdíl je v tom, že pro propojený seznam používáme třídu.
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 (); } } Výstup:
Konečný propojený seznam:
10–> 20–> 30–> 40–> 50–> null
V obou výše uvedených programech, C ++ i Java, máme samostatné funkce pro přidání uzlu před seznam, na konec seznamu a mezi seznamy uvedené v uzlu. Nakonec vytiskneme obsah seznamu vytvořeného pomocí všech tří metod.
# 2) Smazání
Stejně jako vložení, odstranění uzlu ze spojeného seznamu zahrnuje také různé pozice, ze kterých lze uzel odstranit. Můžeme odstranit první uzel, poslední uzel nebo náhodný k-tý uzel z propojeného seznamu. Po odstranění musíme vhodně upravit další ukazatel a další ukazatele v propojeném seznamu, aby byl zachován neporušený propojený seznam.
V následující implementaci C ++ jsme uvedli dvě metody odstranění, tj. Odstranění prvního uzlu v seznamu a odstranění posledního uzlu v seznamu. Nejprve vytvoříme seznam přidáním uzlů do hlavy. Poté po vložení a každém odstranění zobrazíme obsah seznamu.
#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 ' Výstup:
co je síťový klíč na routeru
Propojený seznam byl vytvořen
10–> 8–> 6–> 4–> 2–
> NULL
Propojený seznam po odstranění hlavního uzlu
8–> 6–> 4–> 2–
> NULL
Propojený seznam po odstranění posledního uzlu
8–> 6–> 4–> NULL
Další je implementace Java pro mazání uzlů z propojeného seznamu. Logika implementace je stejná jako v programu C ++. Jediný rozdíl je v tom, že propojený seznam je deklarován jako třída.
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'); } } Výstup:
Vytvořený propojený seznam:
9–> 7–> 5–> 3–> 1–
> null
Propojený seznam po odstranění hlavního uzlu:
7–> 5–> 3–> 1–
> null
Propojený seznam po odstranění posledního uzlu:
7–> 5–> 3–> null
Spočítat počet uzlů
Operaci spočítající počet uzlů lze provést při procházení propojeným seznamem. Již jsme viděli v implementaci výše, že kdykoli potřebujeme vložit / odstranit uzel nebo zobrazit obsah propojeného seznamu, musíme procházet propojeným seznamem od začátku.
Udržování čítače a jeho zvyšování při procházení každého uzlu nám dá počet počtu uzlů přítomných v propojeném seznamu. Tento program necháme na implementaci čtenářů.
Pole a propojené seznamy
Poté, co jsme viděli operace a implementaci propojeného seznamu, pojďme porovnat, jak jsou pole a propojený seznam spravedlivé ve srovnání s ostatními.
Pole Propojené seznamy Pole mají pevnou velikost Velikost propojeného seznamu je dynamická Vložení nového prvku je drahé Vkládání / mazání je snazší Náhodný přístup je povolen Náhodný přístup není možný Prvky jsou na sousedním místě Prvky mají nesouvislé umístění Pro další ukazatel není potřeba žádný další prostor Pro další ukazatel je potřeba další paměťový prostor
Aplikace
Jelikož se pole a propojené seznamy používají k ukládání položek a jsou to lineární datové struktury, lze obě tyto struktury pro většinu aplikací použít podobným způsobem.
Některé z aplikací pro propojené seznamy jsou následující:
- Propojený seznam lze použít k implementaci zásobníků a front.
- Propojený seznam lze také použít k implementaci grafů, kdykoli musíme grafy reprezentovat jako seznamy sousedství.
- Matematický polynom lze uložit jako propojený seznam.
- V případě hashovací techniky jsou kbelíky použité při hašování implementovány pomocí propojených seznamů.
- Kdykoli program vyžaduje dynamické přidělení paměti, můžeme použít propojený seznam, protože propojené seznamy v tomto případě fungují efektivněji.
Závěr
Propojené seznamy jsou datové struktury, které se používají k ukládání datových položek lineárně, ale nesouvisle. Propojený seznam je kolekce uzlů, které obsahují datovou část a další ukazatel, který obsahuje adresu paměti dalšího prvku v seznamu.
Poslední prvek v seznamu má svůj další ukazatel nastavený na NULL, což označuje konec seznamu. První prvek seznamu se nazývá Head. Propojený seznam podporuje různé operace, jako je vkládání, mazání, procházení atd. V případě dynamického přidělování paměti jsou upřednostňovány propojené seznamy před poli.
Propojené seznamy jsou drahé, pokud jde o jejich procházení, protože nemůžeme náhodně přistupovat k prvkům, jako jsou pole. Operace vložení a odstranění jsou však levnější ve srovnání s poli.
V tomto tutoriálu jsme se naučili vše o lineárně spojených seznamech. Propojené seznamy mohou být také kruhové nebo dvojnásobné. Na tyto seznamy se podíváme podrobně v našich nadcházejících cvičeních.
=> Zkontrolujte zde kompletní sérii školení C ++.
Doporučené čtení
- Datová struktura kruhového propojeného seznamu v C ++ s ilustrací
- Dvojnásobně propojená datová struktura seznamu v C ++ s ilustrací
- Struktura dat fronty v C ++ s ilustrací
- Skládejte datovou strukturu v C ++ s ilustrací
- Struktura dat prioritní fronty v C ++ s ilustrací
- Top 15 nejlepších bezplatných nástrojů pro dolování dat: nejkomplexnější seznam
- 15 nejlepších nástrojů ETL v roce 2021 (úplný aktualizovaný seznam)
- Úvod do datových struktur v C ++