Подвійно пов’язаний список на Java

doubly linked list java implementation code examples

Спробуйте Наш Інструмент Для Усунення Проблем

Виберіть Операційну Систему Виберіть Програму Проекції (Необов'Язково)

Опишіть Свою Проблему

Цей посібник пояснює подвійний зв’язаний список у Java, а також реалізацію подвійного зв’язаного списку, циклічний подвійний зв’язаний список Java-коду та приклади:

Зв’язаний список - це послідовне представлення елементів. Кожен елемент пов'язаного списку називається «Вузол». Один з типів пов’язаних списків називається “Односписовий список”.

При цьому кожен вузол містить частину даних, яка зберігає фактичні дані, і другу частину, яка зберігає вказівник на наступний вузол у списку. Ми вже дізналися подробиці списку, що має єдиний зв’язок, у нашому попередньому уроці.

=> Перевірте ВСІ підручники Java тут.

Подвійно пов’язаний список на Java

Що ви дізнаєтесь:

Подвійно пов’язаний список на Java
Круговий подвійно пов’язаний список на Java
- Часті запитання
Висновок
- Рекомендована література

Зв’язаний список має ще один варіант, який називається “подвійно пов’язаний список”. У подвійно зв’язаному списку є додатковий вказівник, відомий як попередній вказівник, у своєму вузлі, крім частини даних, і наступний вказівник, як у списку з єдиним зв’язком.

Вузол у подвійно зв’язаному списку виглядає так:

який найкращий обліковий запис електронної пошти

вузол у подвійно пов

Тут “Попередній” та “Далі” - це вказівники на попередній та наступний елементи вузла відповідно. „Дані” - це фактичний елемент, який зберігається у вузлі.

На наступному малюнку показано подвійно пов’язаний список.

подвійно зв’язаний список

На наведеній вище схемі показано подвійно пов’язаний список. У цьому списку чотири вузли. Як бачите, попередній вказівник першого вузла, а наступний вказівник останнього вузла має нульове значення. Попередній вказівник, встановлений як нульовий, вказує, що це перший вузол у списку подвійних зв’язків, тоді як наступний вказівник, встановлений у нульовий значення, вказує, що вузол є останнім вузлом.

Переваги

Оскільки кожен вузол має покажчики, що вказують на попередній і наступний вузли, подвійно зв’язаний список можна легко прокрутити як вперед, так і назад
Ви можете швидко додати новий вузол, просто змінивши вказівники.
Подібним чином, для операції видалення, оскільки ми маємо як попередні, так і наступні вказівники, видалення простіше, і нам не потрібно обходити весь список, щоб знайти попередній вузол, як у випадку з однопов'язаним списком.

Недоліки

Оскільки в списку з подвійним зв’язком є додатковий вказівник, тобто попередній, потрібен додатковий простір пам’яті для зберігання цього вказівника разом із наступним вказівником та елементом даних.
Всі операції, такі як додавання, видалення тощо вимагають маніпулювання як попередніми, так і наступними вказівниками, що накладає операційні накладні витрати.

Впровадження в Java

Реалізація подвійно пов'язаного списку в 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

вихід - циклічний подвійно зв’язаний список

У наведеній вище програмі ми додали вузол в кінці списку. Оскільки список є круговим, при додаванні нового вузла наступний вказівник нового вузла вказуватиме на перший вузол, а попередній вказівник першого вузла вказуватиме на новий вузол.

Подібним чином попередній вказівник нового вузла вказуватиме на поточний останній вузол, який тепер стане другим останнім вузлом. Ми залишаємо реалізацію додавання нового вузла на початку списку та між вузлами для читачів.

Часті запитання

Q # 1) Чи може бути подвійно пов’язаний список круговим?

Відповідь: Так. Це більш складна структура даних. У круговому подвійно пов'язаному списку попередній покажчик першого вузла містить адресу останнього вузла, а наступний вказівник останнього вузла - адресу першого вузла.

Запитання №2) Як створити подвійно круговий зв’язаний список?

Відповідь: Ви можете створити клас для подвійного кругового пов'язаного списку. Усередині цього класу буде статичний клас, який представляє вузол. Кожен вузол міститиме два покажчики - попередній і наступний та елемент даних. Тоді ви можете виконати операції додавання вузлів до списку та обходу списку.

Запитання №3) Чи є подвійно пов’язаний список лінійним чи круговим?

Відповідь: Подвійно пов’язаний список - це лінійна структура, але круговий подвійно пов’язаний список, хвіст якого спрямований до голови, а голова - до хвоста. Отже, це круговий список.

Q # 4) Яка різниця між списком подвійно пов'язаних та списком кругових зв'язків?

Відповідь: У подвійно пов’язаному списку є вузли, які зберігають інформацію про попередні та наступні вузли, використовуючи попередній та наступний покажчики відповідно. Крім того, попередній вказівник першого вузла та наступний вказівник останнього вузла встановлюються як нульові у списку подвійних зв’язків.

У круговому зв’язаному списку немає початкового або кінцевого вузлів, і вузли утворюють цикл. Крім того, жоден із покажчиків не має значення null у списку кругових зв’язків.

Q # 5) Які переваги списку подвійно пов’язаних?

безкоштовний блокувальник спливаючих вікон для хрому -

Відповідь: Переваги списку подвійних зв’язків:

Її можна рухати як вперед, так і назад.
Операція вставки простіша, оскільки нам не потрібно обходити весь список, щоб знайти попередній елемент.
Видалення є ефективним, оскільки ми знаємо, що попередні та наступні вузли та маніпулювання ними простіші.

Висновок

У цьому посібнику ми детально обговорили подвійно пов'язаний список на Java. Подвійно пов’язаний список - це складна структура, в якій кожен вузол містить вказівники на попередній, а також наступний вузли. Управління цими посиланнями буває складним і може призвести до поломки коду, якщо не обробляти його належним чином.

В цілому, дії подвійно пов’язаного списку ефективніші, оскільки ми можемо заощадити час на обхід списку, оскільки ми маємо як попередній, так і наступний вказівники.

Циклічний подвійно зв’язаний список є більш складним, і вони утворюють круговий шаблон із попереднім покажчиком першого вузла, що вказує на останній вузол, а наступним вказівником останнього вузла - першим вузлом. У цьому випадку операції також ефективні.

На цьому ми закінчили зв’язаний список на Java. Слідкуйте за ще багатьма підручниками з техніки пошуку та сортування на Java.

=> Завітайте сюди, щоб ознайомитись із ексклюзивними навчальними посібниками з Java.

Подвійно пов’язаний список на Java - приклади реалізації та коду