Menu

Prepojená dátová štruktúra zoznamu v C ++ s ilustráciou

  • Hlavná
  • Iné
  • Prepojená dátová štruktúra zoznamu v C ++ s ilustráciou

linked list data structure c with illustration

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Podrobná štúdia prepojeného zoznamu v C ++.

Prepojený zoznam je lineárna dynamická dátová štruktúra na ukladanie dátových položiek. Polia sme už videli v našich predchádzajúcich témach o základnom C ++. Vieme tiež, že polia sú lineárnou dátovou štruktúrou, ktorá ukladá dátové položky na susedných miestach.

Na rozdiel od polí prepojený zoznam neukladá dátové položky na susediace pamäťové miesta.

Prepojený zoznam pozostáva z položiek nazývaných „Uzly“, ktoré obsahujú dve časti. Prvá časť ukladá skutočné údaje a druhá časť má ukazovateľ smerujúci na ďalší uzol. Táto štruktúra sa zvyčajne nazýva „Singly linked list“.

=> Vyskúšajte tu najlepšie výukové programy pre C ++.

SPOJENÝ ZOZNAM

Čo sa dozviete:

Prepojený zoznam v C ++

V tomto návode sa podrobne pozrieme na jednotlivo prepojený zoznam.

Nasledujúca schéma zobrazuje štruktúru jednotlivo prepojeného zoznamu.

štruktúra jednotlivo prepojeného zoznamu

Ako je uvedené vyššie, prvý uzol prepojeného zoznamu sa nazýva „hlava“, zatiaľ čo posledný uzol sa nazýva „chvost“. Ako vidíme, posledný uzol prepojeného zoznamu bude mať svoj ďalší ukazovateľ nulový, pretože nebude mať namierenú žiadnu adresu pamäte.

Pretože každý uzol má ukazovateľ na nasledujúci uzol, dátové položky v prepojenom zozname sa nemusia ukladať na susedných miestach. Uzly môžu byť rozptýlené v pamäti. K uzlom môžeme mať prístup kedykoľvek, pretože každý uzol bude mať adresu nasledujúceho uzla.

Do prepojeného zoznamu môžeme pridávať dátové položky, ako aj položky zo zoznamu ľahko mazať. Takto je možné prepojený zoznam dynamicky zväčšiť alebo zmenšiť. V prepojenom zozname nie je žiadny horný limit, koľko údajových položiek môže obsahovať. Pokiaľ je k dispozícii pamäť, môžeme do prepojeného zoznamu pridať toľko dátových položiek.

Okrem ľahkého vloženia a odstránenia prepojený zoznam taktiež nestráca pamäťové miesto, pretože vopred nemusíme určovať, koľko položiek v prepojenom zozname potrebujeme. Jediné miesto, ktoré zaberá prepojený zoznam, je na uloženie ukazovateľa na ďalší uzol, ktorý pridáva malú réžiu.

Ďalej si rozoberieme rôzne operácie, ktoré je možné vykonať na prepojenom zozname.

Operácie

Rovnako ako ostatné dátové štruktúry, aj tu môžeme vykonávať rôzne operácie s prepojeným zoznamom. Ale na rozdiel od polí, v ktorých môžeme k prvku pristupovať pomocou dolného indexu priamo, aj keď je niekde medzi, nemôžeme urobiť rovnaký náhodný prístup s prepojeným zoznamom.

Aby sme mohli získať prístup k ľubovoľnému uzlu, musíme prejsť prepojeným zoznamom od začiatku a až potom môžeme získať prístup k požadovanému uzlu. Náhodný prístup k údajom z prepojeného zoznamu sa preto ukazuje ako nákladný.

Na prepojenom zozname môžeme vykonávať rôzne operácie, ako je uvedené nižšie:

čo je bezpečnostný kľúč pre bezdrôtovú sieť

# 1) Vkladanie

Operácia vloženia prepojeného zoznamu pridá položku do prepojeného zoznamu. Aj keď to môže znieť jednoducho, vzhľadom na štruktúru prepojeného zoznamu vieme, že kedykoľvek je do prepojeného zoznamu pridaná údajová položka, musíme zmeniť ďalšie ukazovatele predchádzajúceho a nasledujúceho uzla novej položky, ktorú sme vložili.

Druhá vec, ktorú musíme vziať do úvahy, je miesto, kde sa má pridať nová údajová položka.

V prepojenom zozname sú tri pozície, do ktorých je možné pridať údajovú položku.

# 1) Na začiatku prepojeného zoznamu

Prepojený zoznam je uvedený nižšie 2-> 4-> 6-> 8-> 10. Ak chceme pridať nový uzol 1 ako prvý uzol zoznamu, potom hlava smerujúca na uzol 2 bude teraz ukazovať na 1 a ďalší ukazovateľ uzla 1 bude mať pamäťovú adresu uzla 2, ako je uvedené nižšie obrázok.

Vloženie na začiatok

Nový prepojený zoznam sa tak zmení na 1-> 2-> 4-> 6-> 8-> 10.

# 2) Po danom Uzle

Tu je daný uzol a za daným uzlom musíme pridať nový uzol. V zozname nižšie prepojených a-> b-> c-> d -> e, ak chceme pridať uzol f za uzol c, bude prepojený zoznam vyzerať takto:

Vloženie za daný uzol

Vo vyššie uvedenom diagrame teda skontrolujeme, či je daný uzol prítomný. Ak je prítomný, vytvoríme nový uzol f. Potom nasmerujeme ďalší ukazovateľ uzla c tak, aby ukazoval na nový uzol f. Nasledujúci ukazovateľ uzla f teraz ukazuje na uzol d.

# 3) Na konci prepojeného zoznamu

V treťom prípade pridáme nový uzol na koniec prepojeného zoznamu. Uvažujme, že máme rovnaký prepojený zoznam a-> b-> c-> d-> e a na koniec zoznamu musíme pridať uzol f. Prepojený zoznam bude po pridaní uzla vyzerať nasledovne.

Vkladanie na koniec prepojeného zoznamu

Takto vytvoríme nový uzol f. Potom je chvostový ukazovateľ smerujúci na nulu označený na f a ďalší ukazovateľ uzla f je označený na null. Implementovali sme všetky tri typy funkcií vkladania do nižšie uvedeného programu C ++.

V C ++ môžeme prepojený zoznam deklarovať ako štruktúru alebo ako triedu. Deklarovanie prepojeného zoznamu ako štruktúry je tradičnou deklaráciou v štýle C. Prepojený zoznam ako trieda sa používa v modernom C ++, väčšinou pri použití štandardnej knižnice šablón.

V nasledujúcom programe sme použili štruktúru na deklarovanie a vytvorenie prepojeného zoznamu. Bude mať údaje a ukazovateľ na nasledujúci prvok ako svojich členov.

#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ýkon:

Konečný prepojený zoznam:

30–> 20–> 50–> 10–> 40–> nulové

Ďalej implementujeme operáciu vloženého prepojeného zoznamu v Jave. V jazyku Java je prepojený zoznam implementovaný ako trieda. Program uvedený nižšie je logicky podobný programu C ++, jediný rozdiel je v tom, že pre prepojený zoznam používame triedu.

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ýkon:

Konečný prepojený zoznam:

najlepší textový editor pre okná python

10–> 20–> 30–> 40–> 50–> nulové

V obidvoch vyššie uvedených programoch, C ++ aj Java, máme samostatné funkcie na pridanie uzla pred zoznam, na koniec zoznamu a medzi zoznamy uvedené v uzle. Na záver vytlačíme obsah zoznamu vytvoreného pomocou všetkých troch metód.

# 2) Vymazanie

Rovnako ako vkladanie, aj odstránenie uzla z prepojeného zoznamu zahŕňa rôzne polohy, odkiaľ je možné uzol vymazať. Z prepojeného zoznamu môžeme vymazať prvý, posledný uzol alebo náhodný k-tý uzol. Po odstránení musíme nasledujúci ukazovateľ a ďalšie ukazovatele v prepojenom zozname vhodne upraviť, aby bol prepojený zoznam nedotknutý.

V nasledujúcej implementácii C ++ sme uviedli dva spôsoby odstránenia, t. J. Odstránenie prvého uzla v zozname a odstránenia posledného uzla v zozname. Najprv vytvoríme zoznam pridaním uzlov do hlavy. Potom po vložení a každom odstránení zobrazíme obsah zoznamu.

#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ýkon:

program na kopírovanie DVD do počítača

Prepojený zoznam bol vytvorený

10–> 8–> 6–> 4–> 2–
> NULL

Prepojený zoznam po odstránení hlavného uzla

8–> 6–> 4–> 2–
> NULL

Prepojený zoznam po odstránení posledného uzla

8–> 6–> 4–> NULL

Ďalej nasleduje implementácia Java na odstránenie uzlov z prepojeného zoznamu. Logika implementácie je rovnaká ako v programe C ++. Jediný rozdiel je v tom, že prepojený zoznam je deklarovaný ako trieda.

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ýkon:

Prepojený zoznam bol vytvorený:

9–> 7–> 5–> 3–> 1–
> null

Prepojený zoznam po odstránení hlavného uzla:

7–> 5–> 3–> 1–
> null

Prepojený zoznam po odstránení posledného uzla:

7–> 5–> 3–> nulové

Spočítajte počet uzlov

Operáciu na spočítanie počtu uzlov je možné vykonať pri prechode prepojeným zoznamom. Už v implementácii vyššie sme videli, že kedykoľvek potrebujeme vložiť / vymazať uzol alebo zobraziť obsah prepojeného zoznamu, musíme prechádzať prepojeným zoznamom od začiatku.

Udržiavanie počítadla a jeho zvyšovanie pri prechode každým uzlom nám poskytne počet počtu uzlov prítomných v prepojenom zozname. Tento program necháme na implementáciu čitateľom.

Polia a prepojené zoznamy

Keď sme videli fungovanie a implementáciu prepojeného zoznamu, porovnajme, ako sú polia a prepojený zoznam spravodlivé v porovnaní s ostatnými.

PoliaPrepojené zoznamy
Polia majú pevnú veľkosťVeľkosť prepojeného zoznamu je dynamická
Vloženie nového prvku je drahéVkladanie / mazanie je jednoduchšie
Náhodný prístup je povolenýNáhodný prístup nie je možný
Prvky sú na súvislom miestePrvky majú nesúvislé umiestnenie
Pre ďalší ukazovateľ nie je potrebný žiadny ďalší priestorPre ďalší ukazovateľ je potrebný ďalší priestor v pamäti

Aplikácie

Pretože polia a prepojené zoznamy sa používajú na ukladanie položiek a sú to lineárne dátové štruktúry, obe tieto štruktúry je možné použiť podobným spôsobom pre väčšinu aplikácií.

Niektoré z aplikácií pre prepojené zoznamy:

  • Prepojený zoznam možno použiť na implementáciu zásobníkov a front.
  • Prepojený zoznam sa dá použiť aj na implementáciu grafov, kedykoľvek musíme grafy reprezentovať ako zoznamy susedných vzťahov.
  • Matematický polynóm je možné uložiť ako prepojený zoznam.
  • V prípade hashovacej techniky sa segmenty použité pri hašovaní implementujú pomocou prepojených zoznamov.
  • Kedykoľvek program vyžaduje dynamické pridelenie pamäte, môžeme použiť prepojený zoznam, pretože prepojené zoznamy v tomto prípade fungujú efektívnejšie.

Záver

Prepojené zoznamy sú dátové štruktúry, ktoré sa používajú na lineárne ukladanie dátových položiek, ale nesúvislých umiestnení. Prepojený zoznam je kolekcia uzlov, ktoré obsahujú dátovú časť a ďalší ukazovateľ, ktorý obsahuje adresu pamäte nasledujúceho prvku v zozname.

Posledný prvok v zozname má ďalší ukazovateľ nastavený na hodnotu NULL, čo označuje koniec zoznamu. Prvý prvok zoznamu sa nazýva Hlava. Prepojený zoznam podporuje rôzne operácie, ako je vkladanie, mazanie, prechádzanie atď. V prípade dynamického prideľovania pamäte sú prepojené zoznamy uprednostňované pred poľami.

Prepojené zoznamy sú drahé, pokiaľ ide o ich prechod, pretože nemôžeme náhodne získať prístup k prvkom, ako sú polia. Operácie vloženia a odstránenia sú však v porovnaní s poliami lacnejšie.

V tomto tutoriáli sme sa dozvedeli všetko o lineárne prepojených zoznamoch. Prepojené zoznamy môžu byť tiež kruhové alebo dvojnásobné. Tieto zoznamy sa podrobne pozrieme v našich nadchádzajúcich tutoriáloch.

=> Skontrolujte tu kompletné školiace série C ++.

Odporúčané čítanie

^