Мени

Повезана структура података листе на Ц ++ са илустрацијом

  • Главни
  • Остало
  • Повезана структура података листе на Ц ++ са илустрацијом

linked list data structure c with illustration

Детаљна студија повезане листе у Ц ++.



Повезана листа је линеарна динамичка структура података за чување података. Већ смо видели низове у нашим претходним темама на основном Ц ++. Такође знамо да су низови линеарна структура података која складишти ставке података на суседним локацијама.



За разлику од низова, повезана листа не складишти ставке података на непрекидним меморијским местима.

Повезана листа састоји се од предмета названих „Чворови“ који садрже два дела. Први део чува стварне податке, а други део има показивач који показује на следећи чвор. Ова структура се обично назива „појединачно повезана листа“.



=> Овде погледајте најбоље туторијале за Ц ++.

б-дрво вс б + дрво

ПОВЕЗАНА ЛИСТА



Шта ћете научити:

Повезана листа у Ц ++

Појединачно повезану листу детаљно ћемо погледати у овом упутству.

Следећи дијаграм приказује структуру појединачно повезане листе.

структура појединачно повезане листе

Као што је горе приказано, први чвор повезане листе назива се „глава“, док се последњи чвор назива „реп“. Као што видимо, последњи чвор повезане листе имаће следећи показивач као нула, јер неће имати указану меморијску адресу.

Будући да сваки чвор има показивач на следећи чвор, ставке података на повезаној листи не морају бити ускладиштене на суседним локацијама. Чворови се могу расути у меморији. Чворовима можемо приступити било када, јер ће сваки чвор имати адресу следећег чвора.

Можемо додати ставке података на повезану листу, као и лако брисати ставке са листе. Стога је могуће динамички повећати или смањити повезану листу. Не постоји горње ограничење броја ставки података које могу бити на повезаној листи. Дакле, све док је меморија на располагању, можемо додати онолико података на повезану листу.

Осим једноставног уметања и брисања, повезана листа такође не троши простор у меморији јер не морамо претходно навести колико ставки треба на повезаној листи. Једини простор који заузима везана листа је за чување показивача на следећи чвор који додаје мало више трошкова.

Даље ћемо разговарати о разним операцијама које се могу извршити на повезаној листи.

Операције

Баш као и друге структуре података, и ми можемо изводити разне операције за повезану листу. Али за разлику од низова, у којима елементу можемо приступити директно користећи индекс, чак и ако је негде између, не можемо да извршимо исти случајни приступ са повезаном листом.

Да бисмо приступили било ком чвору, морамо прећи повезану листу од почетка и тек тада можемо приступити жељеном чвору. Стога се случајни приступ подацима са повезане листе показује скупим.

Можемо изводити разне операције на повезаној листи како је дато у наставку:

# 1) Уметање

Операција уметања повезане листе додаје ставку на повезану листу. Иако може звучати једноставно, с обзиром на структуру повезане листе, знамо да кад год се ставка података дода на повезану листу, морамо да променимо следеће показиваче на претходни и следећи чвор нове ставке коју смо убацили.

Друга ствар коју морамо узети у обзир је место на којем треба додати нову ставку података.

На повезаној листи постоје три места на која се може додати ставка података.

# 1) На почетку повезане листе

Повезана листа приказана је испод 2-> 4-> 6-> 8-> 10. Ако желимо да додамо нови чвор 1, као први чвор листе, тада ће глава која показује на чвор 2 сада показивати на 1, а следећи показивач на чвор 1 ће имати меморијску адресу чвора 2 као што је приказано у наставку фигура.

Уметање на почетку

Тако нова повезана листа постаје 1-> 2-> 4-> 6-> 8-> 10.

# 2) После датог чвора

Овде је дат чвор и морамо додати нови чвор након датог чвора. На доњој повезаној листи а-> б-> ц-> д -> е, ако желимо да додамо чвор ф иза чвора ц, онда ће повезана листа изгледати на следећи начин:

имплементација хеш табеле у ц ++ коду

Уметање након датог чвора

Тако у горњем дијаграму проверавамо да ли је дати чвор присутан. Ако је присутан, креирамо нови чвор ф. Затим усмеравамо следећи показивач чвора ц на нови чвор ф. Следећи показивач чвора ф сада показује на чвор д.

# 3) На крају повезане листе

У трећем случају додајемо нови чвор на крају повезане листе. Узмимо у обзир да имамо исту повезану листу а-> б-> ц-> д-> е и треба да додамо чвор ф на крај листе. Повезана листа ће изгледати као што је приказано доле након додавања чвора.

Уметак на крају повезане листе

Тако креирамо нови чвор ф. Затим се репни показивач који показује на нулу показује на ф, а следећи показивач на чвор ф показује на нулу. Имплементирали смо све три врсте функција уметања у доле наведени програм Ц ++.

У Ц ++-у можемо повезану листу декларирати као структуру или као класу. Декларисање повезане листе као структуре је традиционална декларација у стилу Ц. Повезана листа као класа користи се у савременом Ц ++, углавном док се користи стандардна библиотека шаблона.

У следећем програму користили смо структуру за декларисање и стварање повезане листе. Као његови чланови имаће податке и показивач на следећи елемент.

#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

Излаз:

Коначна повезана листа:

30–> 20–> 50–> 10–> 40–> нулл

Даље, имплементирамо операцију уметања повезане листе у Јаву. На језику Јава, повезана листа је примењена као класа. Програм испод је логички сличан програму Ц ++, једина разлика је у томе што за повезану листу користимо класу.

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 (); } }

Излаз:

Коначна повезана листа:

10–> 20–> 30–> 40–> 50–> нулл

У оба горња програма, Ц ++, као и Јава, имамо одвојене функције за додавање чвора испред листе, краја листе и између листа датих у чвору. На крају, исписујемо садржај листе створене помоћу све три методе.

# 2) Брисање

Попут уметања, брисање чвора са повезане листе такође укључује различите позиције одакле чвор може бити избрисан. Можемо избрисати први чвор, последњи чвор или случајни ктх чвор са повезане листе. Након брисања, потребно је да прилагодимо следећи показивач и остале показиваче на повезаној листи како би задржали нетакнуту повезану листу.

У следећој имплементацији Ц ++, дали смо две методе брисања, тј. Брисање првог чвора на листи и брисање последњег чвора на листи. Прво креирамо листу додавањем чворова у главу. Затим приказујемо садржај листе након уметања и сваког брисања.

#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 '

Излаз:

Повезана листа је направљена

10–> 8–> 6–> 4–> 2–
> НУЛЛ

Повезана листа након брисања главног чвора

8–> 6–> 4–> 2–
> НУЛЛ

Повезана листа након брисања последњег чвора

8–> 6–> 4–> НУЛЛ

Следећа је Јава примена за брисање чворова са повезане листе. Логика имплементације је иста она која се користи у програму Ц ++. Једина разлика је у томе што је повезана листа декларисана као класа.

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'); } }

Излаз:

Направљена повезана листа:

9–> 7–> 5–> 3–> 1–
> нулл

Повезана листа након брисања главног чвора:

7–> 5–> 3–> 1–
> нулл

Повезана листа након брисања последњег чвора:

7–> 5–> 3–> нулл

Пребројите број чворова

Операција бројања броја чворова може се извршити током обилажења повезане листе. Већ смо видели у горенаведеној имплементацији да кад год треба да уметнемо / избришемо чвор или прикажемо садржај повезане листе, морамо да пређемо повезану листу од почетка.

Задржавање бројача и његово увећавање док прелазимо сваки чвор даће нам број броја чворова присутних на повезаној листи. Овај програм ћемо оставити читаоцима да га примене.

Низови и повезане листе

Након што смо видели рад и примену повезане листе, упоредимо како се низови и повезана листа поклапају у поређењу са другима.

НизовиПовезане листе
Низови имају фиксну величинуВеличина повезане листе је динамична
Уметање новог елемента је скупоУметање / брисање је лакше
Насумичан приступ је дозвољенНасумични приступ није могућ
Елементи се налазе на суседној локацијиЕлементи се не сметају суседно
За следећи показивач није потребан додатни просторЗа следећи показивач потребан је додатни меморијски простор

Апликације

Како се низови и повезане листе користе за складиштење предмета и представљају линеарне структуре података, обе ове структуре могу се користити на сличне начине за већину апликација.

Неке од апликација за повезане листе су следеће:

како отворити свф са Адобе Фласх Плаиер
  • Повезана листа се може користити за примену слогова и редова.
  • Повезана листа се такође може користити за примену графова кад год морамо да представимо графиконе као листе суседности.
  • Математички полином се може сачувати као повезана листа.
  • У случају технике хеширања, сегменти који се користе у хеширању се примењују помоћу повезаних листа.
  • Кад год програм захтева динамичко додељивање меморије, можемо користити повезану листу јер повезане листе ефикасније раде у овом случају.

Закључак

Повезане листе су структуре података које се користе за линеарно чување ставки података, али на несталним локацијама. Повезана листа је колекција чворова који садрже део података и следећи показивач који садржи меморијску адресу следећег елемента на листи.

Последњи елемент на листи има следећи показивач постављен на НУЛЛ, чиме означава крај листе. Први елемент листе назива се Хеад. Повезана листа подржава разне операције попут уметања, брисања, обртања итд. У случају динамичке алокације меморије, повезане листе су пожељније од низова.

Повезане листе су скупе што се тиче њиховог обилажења, јер не можемо насумично приступити елементима попут низова. Међутим, операције уметања и брисања су јефтиније у поређењу са низовима.

У овом упутству смо сазнали све о линеарно повезаним листама. Повезане листе такође могу бити кружне или двоструке. Детаљно ћемо погледати ове листе у нашим предстојећим водичима.

=> Овде погледајте комплетну серију обука за Ц ++.

Препоручено читање

^