linked list data structure c with illustration
Подробно проучване на свързан списък в C ++.
Свързаният списък е линейна динамична структура от данни за съхраняване на елементи от данни. Вече видяхме масиви в предишните ни теми за основния C ++. Също така знаем, че масивите са линейна структура от данни, която съхранява елементи от данни в съседни местоположения.
За разлика от масивите, свързаният списък не съхранява елементи от данни в съседни места на паметта.
Свързаният списък се състои от елементи, наречени „Възли“, които съдържат две части. Първата част съхранява действителните данни, а втората част има указател, който сочи към следващия възел. Тази структура обикновено се нарича „Единично свързан списък“.
=> Вижте най-добрите уроци за обучение на C ++ тук.
Какво ще научите:
Свързан списък в C ++
Ще разгледаме подробно единично свързания списък в този урок.
Следващата диаграма показва структурата на единично свързан списък.
какво е добро приложение за изтегляне на mp3 за android
Както е показано по-горе, първият възел от свързания списък се нарича „глава“, докато последният възел се нарича „опашка“. Както виждаме, последният възел от свързания списък ще има следващия указател като нула, тъй като няма да има посочен адрес в паметта.
Тъй като всеки възел има указател към следващия възел, не е необходимо елементите от данни в свързания списък да се съхраняват на съседни места. Възлите могат да бъдат разпръснати в паметта. Можем да имаме достъп до възлите по всяко време, тъй като всеки възел ще има адрес на следващия възел.
Можем да добавяме елементи от данни към свързания списък, както и лесно да изтриваме елементи от списъка. По този начин е възможно динамичното нарастване или свиване на свързания списък. В горния списък няма горно ограничение за броя елементи от данни. Така че, докато паметта е на разположение, можем да добавим толкова елементи от данни към свързания списък.
Освен лесното вмъкване и изтриване, свързаният списък също не губи място в паметта, тъй като не е необходимо предварително да посочваме колко елемента ни трябват в свързания списък. Единственото място, заето от свързания списък, е за съхраняване на показалеца към следващия възел, който добавя малко режийни разходи.
След това ще обсъдим различните операции, които могат да бъдат извършени в свързан списък.
Операции
Подобно на другите структури от данни, ние можем да изпълняваме различни операции и за свързания списък. Но за разлика от масивите, в които можем да осъществим достъп до елемента, като използваме директно индекс, дори ако е някъде между тях, не можем да направим същия произволен достъп със свързан списък.
За да осъществим достъп до който и да е възел, трябва да преминем през свързания списък от самото начало и едва тогава можем да осъществим достъп до желания възел. Следователно достъпът до данните на случаен принцип от свързания списък се оказва скъп.
Можем да извършваме различни операции в свързан списък, както е дадено по-долу:
# 1) Вмъкване
Операцията за вмъкване на свързан списък добавя елемент към свързания списък. Въпреки че може да звучи просто, като се има предвид структурата на свързания списък, ние знаем, че когато елемент от данни се добавя към свързания списък, трябва да променим следващите указатели на предишния и следващия възел на новия елемент, който сме вмъкнали.
Второто нещо, което трябва да вземем предвид, е мястото, където трябва да се добави новият елемент от данни.
В свързания списък има три позиции, където може да се добави елемент от данни.
# 1) В началото на свързания списък
Свързан списък е показан по-долу 2-> 4-> 6-> 8-> 10. Ако искаме да добавим нов възел 1 като първи възел от списъка, тогава главата, сочеща към възел 2, сега ще сочи към 1, а следващият указател на възел 1 ще има адрес на паметта на възел 2, както е показано по-долу фигура.
Така новият свързан списък става 1-> 2-> 4-> 6-> 8-> 10.
# 2) След дадения възел
Тук е даден възел и ние трябва да добавим нов възел след дадения възел. В свързания по-долу списък a-> b-> c-> d -> e, ако искаме да добавим възел f след възел c, тогава свързаният списък ще изглежда по следния начин:
По този начин в горната диаграма проверяваме дали даденият възел е наличен. Ако е налице, ние създаваме нов възел f. След това насочваме следващия указател на възел c, за да сочим към новия възел f. Следващият указател на възела f сега сочи към възел d.
# 3) В края на свързания списък
В третия случай добавяме нов възел в края на свързания списък. Помислете, че имаме същия свързан списък a-> b-> c-> d-> e и трябва да добавим възел f в края на списъка. Свързаният списък ще изглежда както е показано по-долу след добавяне на възела.
най-добрият системен оптимизатор за Windows 10
По този начин ние създаваме нов възел f. Тогава указателят на опашката, сочещ към null, е посочен към f, а следващият указател на възел f е посочен към null. Внедрихме и трите типа функции за вмъкване в долната програма на C ++.
В C ++ можем да декларираме свързан списък като структура или като клас. Декларирането на свързан списък като структура е традиционна декларация в стил С. Свързан списък като клас се използва в съвременния C ++, най-вече докато се използва стандартна библиотека с шаблони.
В следващата програма използвахме структура за деклариране и създаване на свързан списък. В неговите членове ще има данни и указател към следващия елемент.
#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–> нула
След това изпълняваме свързаната операция за вмъкване на списък в Java. На езика Java свързаният списък е реализиран като клас. Програмата по-долу е подобна по логика на програмата C ++, единствената разлика е, че използваме клас за свързания списък.
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–> нула
И в горната програма, C ++, както и в Java, имаме отделни функции за добавяне на възел пред списъка, края на списъка и между списъците, дадени в възел. В крайна сметка отпечатваме съдържанието на списъка, създаден с помощта на трите метода.
# 2) Изтриване
Подобно на вмъкването, изтриването на възел от свързан списък включва и различни позиции, от които възелът може да бъде изтрит. Можем да изтрием първия възел, последния възел или произволен k-ти възел от свързания списък. След изтриването трябва да настроим по подходящ начин следващия указател и другите указатели в свързания списък, така че свързаният списък да остане непокътнат.
В следващото изпълнение на C ++, ние дадохме два метода за изтриване, т.е. изтриване на първия възел в списъка и изтриване на последния възел в списъка. Първо създаваме списък, като добавяме възли към главата. След това показваме съдържанието на списъка след вмъкване и всяко изтриване.
#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–
> NULL
Свързан списък след изтриване на главен възел
8–> 6–> 4–> 2–
> NULL
Свързан списък след изтриване на последния възел
8–> 6–> 4–> NULL
кои са най-добрите vr приложения за android
Следва изпълнението на Java за изтриване на възли от свързания списък. Логиката за внедряване е същата като използваната в програмата C ++. Единствената разлика е, че свързаният списък е деклариран като клас.
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–> нула
Пребройте броя на възлите
Операцията за преброяване на броя на възлите може да се извърши, докато обхождате свързания списък. Вече видяхме в изпълнението по-горе, че всеки път, когато трябва да вмъкнем / изтрием възел или да покажем съдържанието на свързания списък, трябва да преминем през свързания списък от начало.
Запазването на брояч и увеличаването му при преминаване през всеки възел ще ни даде броя на възлите, присъстващи в свързания списък. Ще оставим тази програма за изпълнение на читателите.
Масиви и свързани списъци
След като видяхме операциите и изпълнението на свързания списък, нека да сравним как масивите и свързаният списък са справедливи в сравнение помежду си.
Масиви Свързани списъци Масивите имат фиксиран размер Размерът на свързания списък е динамичен Вмъкването на нов елемент е скъпо Вмъкването / изтриването е по-лесно Допуска се произволен достъп Не е възможен произволен достъп Елементите са на съседно място Елементите имат непрекъснато местоположение За следващия указател не се изисква допълнително пространство За следващия указател е необходимо допълнително място в паметта
Приложения
Тъй като масивите и свързаните списъци се използват за съхраняване на елементи и са линейни структури от данни, и двете структури могат да се използват по сходни начини за повечето приложения.
Някои от приложенията за свързани списъци са както следва:
- Свързан списък може да се използва за внедряване на стекове и опашки.
- Свързан списък може да се използва и за внедряване на графики, когато трябва да представяме графики като списъци за съседство.
- Математически полином може да се съхранява като свързан списък.
- В случай на техника на хеширане, групите, използвани при хеширането, се изпълняват, като се използват свързаните списъци.
- Винаги, когато дадена програма изисква динамично разпределение на паметта, можем да използваме свързан списък, тъй като свързаните списъци работят по-ефективно в този случай.
Заключение
Свързаните списъци са структурите от данни, които се използват за съхраняване на елементи от данни по линеен начин, но несъседни места. Свързаният списък е колекция от възли, които съдържат част от данни и следващ указател, който съдържа адреса на паметта на следващия елемент в списъка.
Последният елемент в списъка има следващия указател, зададен на NULL, като по този начин указва края на списъка. Първият елемент от списъка се нарича Head. Свързаният списък поддържа различни операции като вмъкване, изтриване, обръщане и др. В случай на динамично разпределение на паметта, свързаните списъци са за предпочитане пред масивите.
Свързаните списъци са скъпи, що се отнася до тяхното обръщане, тъй като не можем да получим произволен достъп до елементите като масиви. Операциите за вмъкване и изтриване обаче са по-евтини в сравнение с масиви.
Научихме всичко за линейно свързани списъци в този урок. Свързаните списъци също могат да бъдат кръгли или двойно. Ще разгледаме задълбочено тези списъци в предстоящите ни уроци.
=> Проверете тук за пълна серия за обучение на C ++.
Препоръчително четене
- Структура на данните от циркулярно свързан списък в C ++ с илюстрация
- Структура на данните от двойно свързан списък в C ++ с илюстрация
- Структура на данните за опашката в C ++ с илюстрация
- Структура на данните за стека в C ++ с илюстрация
- Структура на данните за приоритетна опашка в C ++ с илюстрация
- Топ 15 най-добри безплатни инструменти за извличане на данни: Най-изчерпателният списък
- 15 най-добри ETL инструмента през 2021 г. (Пълен актуализиран списък)
- Въведение в структурите на данни в C ++