Двоструко повезана листа у Јави

doubly linked list java implementation code examples

Испробајте Наш Инструмент За Елиминисање Проблема

Изаберите Оперативни Систем Изаберите Програм Пројекције (Опционо)

Опишите Свој Проблем

Овај водич објашњава двоструко повезану листу у Јави, заједно са применом двоструко повезане листе, кружни двоструко повезани списак Јава кода и примери:

Повезана листа је секвенцијални приказ елемената. Сваки елемент повезане листе назива се „чвор“. Једна врста повезане листе назива се „Једноструко повезана листа“.

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

=> Овде проверите СВЕ Јава туторијале.

Двоструко повезана листа на Јави

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

Двоструко повезана листа у Јави
Кружна двоструко повезана листа на Јави
- Често постављана питања
Закључак
- Препоручено читање

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

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

кружно повезана листа у ц ++

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

Овде су „Прев“ и „Нект“ показивачи на претходни и следећи елементи чвора. „Подаци“ је стварни елемент који се чува у чвору.

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

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

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

Предности

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

Мане

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

Имплементација у Јави

Имплементација двоструко повезане листе у Јави састоји се од креирања двоструко повезане класе листе, класе чворова и додавања чворова на двоструко повезану листу

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

Имплементација двоструко повезане листе у Јави

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

Програм испод приказује Јава имплементацију двоструко повезане листе са додатком нових чворова на крају листе.

 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

Излаз - додавање нових чворова

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

Кружна двоструко повезана листа на Јави

Кружна двоструко повезана листа једна је од сложених структура. На овој листи, последњи чвор двоструко повезане листе садржи адресу првог чвора, а први чвор садржи адресу последњег чвора. Тако у кружној двоструко повезаној листи постоји циклус и ниједан од показивача на чвор није постављен на нулу.

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

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

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

Кружне двоструко повезане листе имају широку примену у индустрији софтвера. Једна од таквих апликација је музичка апликација која има листу песама. На листи за репродукцију, када завршите са свирањем свих песама, на крају последње песме аутоматски се враћате на прву песму. То се ради помоћу кружних спискова.

Предности кружне двоструко повезане листе:

Кружном двоструко повезаном листом може се прелазити од главе до репа или репа до главе.
Прелазак од главе до репа или репа до главе је ефикасан и траје само константно време О (1).
Може се користити за примену напредних структура података, укључујући Фибонаццијеву гомилу.

Мане:

Како сваки чвор треба да направи простор за претходни показивач, потребна је додатна меморија.
Морамо да се носимо са пуно показивача док изводимо операције на кружној двоструко повезаној листи. Ако се са показивачима не рукује правилно, примена се може прекинути.

Јава програм у наставку приказује примену двоструко повезане листе Цирцулар.

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) Које су предности двоструко повезане листе?

Одговор: Предности двоструко повезане листе су:

Може се кретати у правцу унапред, као и уназад.
Операција уметања је лакша јер не треба да прелазимо целу листу да бисмо пронашли претходни елемент.
Брисање је ефикасно јер знамо да су претходни и следећи чворови и управљање њима лакши.

Закључак

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

Све у свему, операције двоструко повезане листе су ефикасније јер можемо уштедети време за прелазак листе јер имамо и претходне и следеће смернице.

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

Са овим смо завршили са повезаном листом у Јави. Пратите још много водича о техникама претраживања и сортирања на Јави.

како створити нови пројекат у помрачењу

=> Посетите овде за ексклузивну серију лекција за Јава тренинг.

Двоструко повезана листа у Јави - примери примене и кода