Lista podwójnie połączona w Javie

doubly linked list java implementation code examples

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Wybierz System Operacyjny Wybierz Program Projekcji (Opcjonalnie)

Opisz Swój Problem

W tym samouczku wyjaśniono listę podwójnie połączonych list w Javie wraz z implementacją listy podwójnie połączonej, okólną listą podwójnie połączoną z kodem Java i przykładami:

Lista połączona jest sekwencyjną reprezentacją elementów. Każdy element połączonej listy nazywany jest „węzłem”. Jeden typ listy połączonej nosi nazwę „Lista pojedynczo połączona”.

W tym przypadku każdy węzeł zawiera część danych, która przechowuje rzeczywiste dane, oraz drugą część, która przechowuje wskaźnik do następnego węzła na liście. Dowiedzieliśmy się już szczegółów pojedynczo połączonej listy w naszym poprzednim samouczku.

=> Sprawdź WSZYSTKIE samouczki Java tutaj.

Lista podwójnie połączona w Javie

Czego się nauczysz:

Lista podwójnie połączona w Javie
Okrągła lista podwójnie połączona w Javie
- Często Zadawane Pytania
Wniosek
- rekomendowane lektury

Lista połączona ma inną odmianę zwaną „listą podwójnie połączoną”. Lista podwójnie połączona ma dodatkowy wskaźnik znany jako poprzedni wskaźnik w swoim węźle, oprócz części danych i następny wskaźnik, jak na liście pojedynczo połączonej.

Węzeł na liście podwójnie połączonej wygląda następująco:

testowanie ręczne pytania do rozmowy kwalifikacyjnej na 4 lata doświadczenia

węzeł na liście podwójnie połączonej

Tutaj „Poprzedni” i „Następny” są wskaźnikami odpowiednio do poprzedniego i następnego elementu węzła. „Dane” to rzeczywisty element przechowywany w węźle.

Poniższy rysunek przedstawia podwójnie połączoną listę.

lista podwójnie połączona

Powyższy diagram przedstawia podwójnie połączoną listę. Na tej liście znajdują się cztery węzły. Jak widać, poprzedni wskaźnik pierwszego węzła i następny wskaźnik ostatniego węzła są ustawione na null. Poprzedni wskaźnik ustawiony na null wskazuje, że jest to pierwszy węzeł na liście podwójnie połączonej, podczas gdy następny wskaźnik ustawiony na null wskazuje, że węzeł jest ostatnim węzłem.

Zalety

Ponieważ każdy węzeł ma wskaźniki wskazujące na poprzedni i następny węzeł, podwójnie połączona lista może być łatwo przechodzona zarówno w kierunku do przodu, jak i do tyłu
Możesz szybko dodać nowy węzeł, po prostu zmieniając wskaźniki.
Podobnie w przypadku operacji usuwania, ponieważ mamy poprzednie i następne wskaźniki, usuwanie jest łatwiejsze i nie musimy przechodzić przez całą listę, aby znaleźć poprzedni węzeł, jak w przypadku listy pojedynczo połączonej.

Niedogodności

Ponieważ na podwójnie połączonej liście znajduje się dodatkowy wskaźnik, tj. Poprzedni wskaźnik, do przechowywania tego wskaźnika wraz z następnym wskaźnikiem i elementem danych wymagane jest dodatkowe miejsce w pamięci.
Wszystkie operacje, takie jak dodawanie, usuwanie itp., Wymagają manipulowania zarówno poprzednimi, jak i następnymi wskaźnikami, w ten sposób narzucając narzut operacyjny.

Implementacja w Javie

Implementacja podwójnie połączonej listy w Javie obejmuje utworzenie podwójnie połączonej listy, klasy węzłów i dodania węzłów do podwójnie połączonej listy

Dodanie nowych węzłów zwykle odbywa się na końcu listy. Poniższy diagram przedstawia dodanie nowego węzła na końcu podwójnie połączonej listy.

Implementacja list podwójnie połączonych w Javie

Jak pokazano na powyższym diagramie, aby dodać nowy węzeł na końcu listy, następny wskaźnik ostatniego węzła wskazuje teraz nowy węzeł zamiast null. Poprzedni wskaźnik nowego węzła wskazuje na ostatni węzeł. Ponadto następny wskaźnik nowego węzła wskazuje na wartość null, co czyni go nowym ostatnim węzłem.

Poniższy program pokazuje implementację w Javie podwójnie połączonej listy z dodaniem nowych węzłów na końcu listy.

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

Wynik:

Węzły podwójnie połączonej listy:
10 20 30 40 50

Wyjście - dodanie nowych węzłów

Oprócz dodania nowego węzła na końcu listy, możesz także dodać nowy węzeł na początku listy lub pomiędzy listą. Implementację tę pozostawiamy czytelnikowi, aby czytelnicy mogli lepiej zrozumieć operacje.

Okrągła lista podwójnie połączona w Javie

Okrągła lista podwójnie połączona jest jedną ze złożonych struktur. Na tej liście ostatni węzeł z podwójnie połączonej listy zawiera adres pierwszego węzła, a pierwszy węzeł zawiera adres ostatniego węzła. Tak więc na kołowej podwójnie połączonej liście istnieje cykl i żaden ze wskaźników węzła nie jest ustawiony na zero.

Poniższy diagram przedstawia okrągłą listę podwójnie połączoną.

okrągła lista podwójnie połączona

Jak pokazano na powyższym diagramie, następny wskaźnik ostatniego węzła wskazuje na pierwszy węzeł. Poprzedni wskaźnik pierwszego węzła wskazuje na ostatni węzeł.

Okrągłe listy podwójnie połączone mają szerokie zastosowanie w branży oprogramowania. Jedną z takich aplikacji jest aplikacja muzyczna z listą odtwarzania. Na liście odtwarzania po zakończeniu odtwarzania wszystkich utworów, a następnie na końcu ostatniego utworu, automatycznie wrócisz do pierwszego utworu. Odbywa się to za pomocą okrągłych list.

Zalety okrągłej listy podwójnie połączonej:

Okrągłą podwójnie połączoną listę można przechodzić od głowy do ogona lub od ogona do głowy.
Przejście od głowy do ogona lub od ogona do głowy jest wydajne i zajmuje tylko stały czas O (1).
Może być używany do implementacji zaawansowanych struktur danych, w tym sterty Fibonacciego.

Niedogodności:

Ponieważ każdy węzeł musi zrobić miejsce na poprzedni wskaźnik, wymagana jest dodatkowa pamięć.
Podczas wykonywania operacji na okrągłej liście podwójnie połączonej musimy mieć do czynienia z wieloma wskaźnikami. Jeśli wskaźniki nie są obsługiwane prawidłowo, implementacja może się zepsuć.

Poniższy program Java przedstawia implementację listy Circular podwójnie połączonej.

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

Wynik:

Okrągła lista podwójnie połączona: 40 50 60 70 80
Okrągła lista podwójnie połączona przeszła wstecz:
80 70 60 50 40

wyjście - Okrągła, podwójnie połączona lista

W powyższym programie dodaliśmy węzeł na końcu listy. Ponieważ lista jest okrągła, po dodaniu nowego węzła następny wskaźnik nowego węzła będzie wskazywał na pierwszy węzeł, a poprzedni wskaźnik pierwszego węzła będzie wskazywał na nowy węzeł.

Podobnie, poprzedni wskaźnik nowego węzła będzie wskazywał na bieżący ostatni węzeł, który stanie się teraz przedostatnim węzłem. Realizację dodania nowego węzła pozostawiamy na początku listy i pomiędzy węzłami czytelnikom.

Często Zadawane Pytania

P # 1) Czy lista podwójnie połączona może być okrągła?

co to jest plik .eps

Odpowiedź: Tak. Jest to bardziej złożona struktura danych. Na okrągłej liście podwójnie połączonej poprzedni wskaźnik pierwszego węzła zawiera adres ostatniego węzła, a następny wskaźnik ostatniego węzła zawiera adres pierwszego węzła.

P # 2) Jak utworzyć listę połączoną podwójnie kołowo?

Odpowiedź: Możesz utworzyć klasę dla listy połączonej podwójnie cyklicznie. Wewnątrz tej klasy będzie klasa statyczna reprezentująca węzeł. Każdy węzeł będzie zawierał dwa wskaźniki - poprzedni i następny oraz element danych. Następnie możesz mieć operacje dodawania węzłów do listy i przechodzenia przez listę.

P # 3) Czy lista podwójnie połączona jest liniowa czy kołowa?

Odpowiedź: Lista podwójnie połączona jest strukturą liniową, ale okrągłą listą podwójnie połączoną, której ogon jest skierowany w stronę głowy, a głowa skierowana w stronę ogona. Dlatego jest to lista cykliczna.

P # 4) Jaka jest różnica między listą podwójnie połączoną a listą połączoną cyklicznie?

Odpowiedź: Lista podwójnie połączona zawiera węzły, które przechowują informacje o swoich poprzednich i następnych węzłach, używając odpowiednio poprzedniego i następnego wskaźnika. Ponadto poprzedni wskaźnik pierwszego węzła i następny wskaźnik ostatniego węzła są ustawione na zero na liście podwójnie połączonej.

Na liście połączonych cyklicznie nie ma węzłów początkowych ani końcowych, a węzły tworzą cykl. Ponadto żaden ze wskaźników nie jest ustawiony na wartość null na cyklicznej liście połączonej.

P # 5) Jakie są zalety podwójnie połączonej listy?

Odpowiedź: Zalety listy podwójnie połączonej to:

Można nim poruszać się zarówno do przodu, jak i do tyłu.
Operacja wstawiania jest łatwiejsza, ponieważ nie musimy przechodzić przez całą listę, aby znaleźć poprzedni element.
Usuwanie jest wydajne, ponieważ wiemy, że poprzednie i następne węzły i manipulowanie są łatwiejsze.

Wniosek

W tym samouczku szczegółowo omówiliśmy listę podwójnie połączoną w Javie. Lista podwójnie połączona jest złożoną strukturą, w której każdy węzeł zawiera wskaźniki do swoich poprzednich i następnych węzłów. Zarządzanie tymi linkami jest czasami trudne i może prowadzić do awarii kodu, jeśli nie jest obsługiwane prawidłowo.

Ogólnie operacje na podwójnie połączonej liście są bardziej wydajne, ponieważ możemy zaoszczędzić czas na przechodzenie przez listę, ponieważ mamy zarówno poprzednie, jak i następne wskaźniki.

Okrągła lista podwójnie połączona jest bardziej złożona i tworzy kołowy wzór, w którym poprzedni wskaźnik pierwszego węzła wskazuje na ostatni węzeł, a następny wskaźnik ostatniego węzła wskazuje na pierwszy węzeł. W tym przypadku również operacje są wydajne.

Skończyliśmy z połączoną listą w Javie. Wkrótce pojawi się wiele innych samouczków dotyczących technik wyszukiwania i sortowania w Javie.

=> Odwiedź tutaj ekskluzywną serię samouczków szkoleniowych Java.

Lista podwójnie połączona w Javie - przykłady implementacji i kodu