doubly linked list java implementation code examples
Този урок обяснява списъка с двойно свързан списък в Java заедно с изпълнението на двойно свързан списък, цикъла на кода и примери за двойно свързан списък на Java и примери:
Свързаният списък е последователно представяне на елементи. Всеки елемент от свързания списък се нарича „възел“. Един тип свързан списък се нарича „Единично свързан списък“.
При това всеки възел съдържа част с данни, която съхранява действителни данни, и втора част, която съхранява указател към следващия възел в списъка. Вече научихме подробностите за единично свързания списък в нашия предишен урок.
=> Проверете ВСИЧКИ уроци за Java тук.
Какво ще научите:
Двойно свързан списък в Java
Свързаният списък има друг вариант, наречен „двойно свързан списък“. Двойно свързан списък има допълнителен указател, известен като предишния указател в своя възел, освен частта с данни и следващия указател, както в единично свързания списък.
Възел в двойно свързания списък изглежда както следва:
къде мога да гледам безплатни аниме онлайн
Тук „Prev“ и „Next“ са указатели съответно към предишния и следващия елемент на възела. „Данните“ е действителният елемент, който се съхранява във възела.
Следващата фигура показва двойно свързан списък.
Горната диаграма показва двойно свързания списък. В този списък има четири възли. Както можете да видите, предишният указател на първия възел и следващият указател на последния възел са настроени на нула. Предишният указател, зададен за нула, показва, че това е първият възел в двойно свързания списък, докато следващият указател, зададен за нула, показва, че възелът е последният възел.
Предимства
- Тъй като всеки възел има указатели, сочещи към предишния и следващия възел, двойно свързаният списък може лесно да бъде преместен както в посока напред, така и назад
- Можете бързо да добавите новия възел, само като промените указателите.
- По същия начин, за операция за изтриване, тъй като имаме предходни, както и следващи указатели, изтриването е по-лесно и не е необходимо да обхождаме целия списък, за да намерим предишния възел, както в случай на единично свързан списък.
Недостатъци
- Тъй като има допълнителен указател в двойно свързания списък, т.е.предишния указател, е необходимо допълнително пространство в паметта за съхраняване на този указател заедно със следващия указател и елемент от данни.
- Всички операции като добавяне, изтриване и т.н. изискват както предишните, така и следващите указатели да бъдат манипулирани, като по този начин се налагат оперативни режийни.
Внедряване в Java
Внедряването на двойно свързан списък в Java се състои от създаване на двойно свързан клас списък, клас възел и добавяне на възли към двойно свързания списък
Добавянето на нови възли обикновено се извършва в края на списъка. Диаграмата по-долу показва добавянето на новия възел в края на двойно свързания списък.
Както е показано на горната диаграма, за да добавите нов възел в края на списъка, следващият указател на последния възел сега сочи към новия възел вместо null. Предишният указател на новия възел сочи към последния възел. Освен това следващият указател на новия възел сочи към нула, като по този начин го прави нов последен възел.
Програмата по-долу показва изпълнението на Java на двойно свързан списък с добавяне на нови възли в края на списъка.
class DoublyLinkedList { //A node class for doubly linked list class Node{ int item; Node previous; Node next; public Node(int item) { this.item = item; } } //Initially, heade and tail is set to null Node head, tail = null; //add a node to the list public void addNode(int item) { //Create a new node Node newNode = new Node(item); //if list is empty, head and tail points to newNode if(head == null) { head = tail = newNode; //head's previous will be null head.previous = null; //tail's next will be null tail.next = null; } else { //add newNode to the end of list. tail->next set to newNode tail.next = newNode; //newNode->previous set to tail newNode.previous = tail; //newNode becomes new tail tail = newNode; //tail's next point to null tail.next = null; } } //print all the nodes of doubly linked list public void printNodes() { //Node current will point to head Node current = head; if(head == null) { System.out.println('Doubly linked list is empty'); return; } System.out.println('Nodes of doubly linked list: '); while(current != null) { //Print each node and then go to next. System.out.print(current.item + ' '); current = current.next; } } } class Main{ public static void main(String() args) { //create a DoublyLinkedList object DoublyLinkedList dl_List = new DoublyLinkedList(); //Add nodes to the list dl_List.addNode(10); dl_List.addNode(20); dl_List.addNode(30); dl_List.addNode(40); dl_List.addNode(50); //print the nodes of DoublyLinkedList dl_List.printNodes(); } } Изход:
Възли на двойно свързан списък:
10 20 30 40 50
Освен добавяне на нов възел в края на списъка, можете да добавите и нов възел в началото на списъка или между него. Оставяме това изпълнение на читателя, за да могат читателите да разберат операциите по-добре.
Кръгов двойно свързан списък в Java
Кръговият двойно свързан списък е една от сложните структури. В този списък последният възел от двойно свързания списък съдържа адреса на първия възел, а първият възел съдържа адреса на последния възел. По този начин в кръгъл двойно свързан списък има цикъл и нито един от указателите на възли не е настроен на нула.
Следващата диаграма показва кръговия двойно свързан списък.
Както е показано на горната диаграма, следващият указател на последния възел сочи към първия възел. Предишният указател на първия възел сочи към последния възел.
Кръговите двойно свързани списъци имат широко приложение в софтуерната индустрия. Едно такова приложение е музикалното приложение, което има плейлист. В плейлиста, когато завършите възпроизвеждането на всички песни, в края на последната песен автоматично се връщате към първата песен. Това се прави с помощта на кръгови списъци.
Предимства на кръгъл двойно свързан списък:
- Кръговият двойно свързан списък може да бъде обхождан от главата до опашката или опашката до главата.
- Преминаването от глава до опашка или опашка до глава е ефективно и отнема само постоянно време O (1).
- Може да се използва за внедряване на усъвършенствани структури от данни, включително купчина на Фибоначи.
Недостатъци:
- Тъй като всеки възел трябва да освободи място за предишния указател, се изисква допълнителна памет.
- Трябва да се справим с много указатели, докато изпълняваме операции в кръгъл двойно свързан списък. Ако указателите не се обработват правилно, тогава изпълнението може да се счупи.
Долната програма Java показва изпълнението на двойно свързания списък Circular.
import java.util.*; class Main{ static Node head; // Doubly linked list node definition static class Node{ int data; Node next; Node prev; }; // Function to insert node in the list static void addNode(int value) { // List is empty so create a single node furst if (head == null) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; head = new_node; return; } // find last node in the list if list is not empty Node last = (head).prev; //previous of head is the last node // create a new node Node new_node = new Node(); new_node.data = value; // next of new_node will point to head since list is circular new_node.next = head; // similarly previous of head will be new_node (head).prev = new_node; // change new_node=>prev to last new_node.prev = last; // Make new node next of old last last.next = new_node; } static void printNodes() { Node temp = head; //traverse in forward direction starting from head to print the list while (temp.next != head) { System.out.printf('%d ', temp.data); temp = temp.next; } System.out.printf('%d ', temp.data); //traverse in backward direction starting from last node System.out.printf('
Circular doubly linked list travesed backward:
'); Node last = head.prev; temp = last; while (temp.prev != last) { System.out.printf('%d ', temp.data); temp = temp.prev; } System.out.printf('%d ', temp.data); } public static void main(String() args) { //the empty list Node l_list = null; // add nodes to the list addNode(40); addNode(50); addNode(60); addNode(70); addNode(80); //print the list System.out.printf('Circular doubly linked list: '); printNodes(); } } Изход:
Кръгов двойно свързан списък: 40 50 60 70 80
Кръговият двойно свързан списък се движи назад:
80 70 60 50 40
В горната програма сме добавили възела в края на списъка. Тъй като списъкът е кръгов, при добавяне на новия възел следващият указател на новия възел ще сочи към първия възел, а предишният указател на първия възел ще сочи към новия възел.
По същия начин предишният указател на новия възел ще сочи към текущия последен възел, който сега ще се превърне във втория последен възел. Оставяме изпълнението за добавяне на нов възел в началото на списъка и между възлите на читателите.
къде мога да гледам безплатни аниме онлайн
често задавани въпроси
В # 1) Може ли списъкът с двойно свързване да бъде кръгъл?
Отговор: Да. Това е по-сложна структура от данни. В кръгъл двойно свързан списък, предишният указател на първия възел съдържа адреса на последния възел, а следващият указател на последния възел съдържа адреса на първия възел.
В # 2) Как се създава списък с двойно кръгова връзка?
Отговор: Можете да създадете клас за двойно кръгово свързан списък. Вътре в този клас ще има статичен клас, който да представлява възела. Всеки възел ще съдържа два указателя - предишен и следващ и елемент от данни. След това можете да извършвате операции за добавяне на възли към списъка и за обхождане на списъка.
В # 3) Линейно или кръгъл е списъкът с двойно свързване?
Отговор: Двойно свързаният списък е линейна структура, но кръгъл двойно свързан списък, чиято опашка е насочена към главата и главата е насочена към опашката. Следователно това е кръгов списък.
В # 4) Каква е разликата между списъка с двойно свързаност и списъка с циркулярни връзки?
Отговор: Двойно свързан списък има възли, които съхраняват информация за неговите предишни, както и следващите възли, използвайки съответно предходния и следващия указатели. Също така предишният указател на първия възел и следващият указател на последния възел е зададен за нула в двойно свързания списък.
В списъка с кръгови връзки няма начален или краен възел и възлите образуват цикъл. Също така, нито един от указателите не е зададен за нула в списъка с кръгови връзки.
В # 5) Какви са предимствата на двойно свързан списък?
Отговор: Предимствата на двойно свързания списък са:
- Тя може да се движи както в посока напред, така и назад.
- Операцията за вмъкване е по-лесна, тъй като не е необходимо да обхождаме целия списък, за да намерим предишния елемент.
- Изтриването е ефективно, тъй като знаем, че предишните и следващите възли и манипулирането е по-лесно.
Заключение
В този урок обсъдихме подробно двойно свързания списък в Java. Двойно свързаният списък е сложна структура, в която всеки възел съдържа указатели към предишния, както и към следващите възли. Управлението на тези връзки понякога е трудно и може да доведе до повреда на кода, ако не се обработва правилно.
Като цяло операциите на двойно свързан списък са по-ефективни, тъй като можем да спестим време за обхождане на списъка, тъй като имаме както предишния, така и следващия указател.
Кръговият двойно свързан списък е по-сложен и те образуват кръгов модел с предишния указател на първия възел, сочещ към последния възел и следващия указател на последния възел, сочещ към първия възел. В този случай също операциите са ефективни.
С това приключихме със свързания списък в Java. Следете за още много уроци за техниките за търсене и сортиране в Java.
=> Посетете тук за ексклузивната серия уроци за обучение по Java.
Препоръчително четене
- Структура на данните от списъка с двойно свързване в C ++ с илюстрация
- Алгоритъм на двоично търсене в Java - Внедряване и примери
- Списък на Java - Как да създадете, инициализирате и използвате списък в Java
- Урок за интерфейс на Java и абстрактен клас с примери
- Методи на Java List - Сортиране на списък, Съдържа, Добавяне на списък, Премахване на списък
- Сортиране при вмъкване в Java - Алгоритъм за сортиране при вмъкване и примери
- Урок за JAVA за начинаещи: 100+ практически ръководства за Java видео
- Сортиране на балончета в Java - алгоритми за сортиране на Java и примери за кодове