Java'da Çift Bağlantılı Liste

doubly linked list java implementation code examples

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

İşletim Sistemini Seçin Bir Projeksiyon Programı Seçin (Isteğe Bağlı Olarak)

Sorununuzu Açıklayın

Bu Öğretici, Çift Bağlantılı Liste Uygulaması, Dairesel Çift Bağlantılı Liste Java Kodu ve Örneklerle birlikte Java'daki Çift Bağlantılı Listeyi Açıklar:

Bağlantılı liste, öğelerin sıralı bir temsilidir. Bağlantılı listenin her bir öğesi 'Düğüm' olarak adlandırılır. Bir tür bağlantılı liste, 'Tek bağlantılı liste' olarak adlandırılır.

Bunda, her düğüm, gerçek verileri depolayan bir veri bölümü ve listedeki sonraki düğüme işaretçiyi depolayan ikinci bir bölüm içerir. Önceki eğitimimizde tek bağlantılı listenin ayrıntılarını zaten öğrendik.

=> TÜM Java Öğreticilerini Buradan Kontrol Edin.

Java

Ne öğreneceksin:

Java'da Çift Bağlantılı Liste
Java'da Dairesel Çift Bağlantılı Liste
- Sıkça Sorulan Sorular
Sonuç
- Önerilen Kaynaklar

Bağlantılı listenin 'çift bağlantılı liste' adı verilen başka bir çeşidi vardır. Çift bağlantılı bir liste, veri kısmından ayrı olarak düğümünde önceki işaretçi olarak bilinen ek bir işaretçiye ve tekil bağlantılı listedeki gibi sonraki işaretçiye sahiptir.

Çift bağlantılı listedeki bir düğüm aşağıdaki gibi görünür:

dublajlı anime izlemek için en iyi siteler

çift bağlantılı listedeki düğüm

Burada, 'Önceki' ve 'Sonraki', düğümün sırasıyla önceki ve sonraki öğelerine işaretçilerdir. 'Veri', düğümde depolanan asıl öğedir.

Aşağıdaki şekil, çift bağlantılı bir listeyi göstermektedir.

çift bağlantılı liste

Yukarıdaki diyagram, çift bağlantılı listeyi göstermektedir. Bu listede dört düğüm var. Gördüğünüz gibi, ilk düğümün önceki göstericisi ve son düğümün sonraki göstericisi null olarak ayarlanmıştır. Null olarak ayarlanan önceki işaretçi, bunun çift bağlantılı listedeki ilk düğüm olduğunu belirtirken, null olarak ayarlanan sonraki işaretçi düğümün son düğüm olduğunu belirtir.

Avantajları

Her düğümün önceki ve sonraki düğümlere işaret eden işaretçileri olduğundan, çift bağlantılı liste ileri ve geri yönde kolayca gezilebilir
Yalnızca işaretçileri değiştirerek yeni düğümü hızlı bir şekilde ekleyebilirsiniz.
Benzer şekilde, silme işlemi için, önceki ve sonraki işaretçilerimiz olduğu için, silme işlemi daha kolaydır ve tek bağlı listede olduğu gibi önceki düğümü bulmak için tüm listeyi geçmemize gerek yoktur.

Dezavantajları

Çift bağlantılı listede, yani önceki işaretçide fazladan bir işaretçi olduğundan, bu işaretçiyi sonraki işaretçi ve veri öğesi ile birlikte saklamak için ek bellek alanı gerekir.
Ekleme, silme, vb. Gibi tüm işlemler, hem önceki hem de sonraki işaretçilerin manipüle edilmesini gerektirir, böylece operasyonel ek yük getirir.

Java'da Uygulama

Java'da çift bağlantılı listenin uygulanması, çift bağlantılı bir liste sınıfı, düğüm sınıfı ve çift bağlantılı listeye düğümler eklemeyi içerir.

Yeni düğümlerin eklenmesi genellikle listenin sonunda yapılır. Aşağıdaki diyagram, çift bağlantılı listenin sonuna yeni düğümün eklenmesini göstermektedir.

Java

Yukarıdaki diyagramda gösterildiği gibi, listenin sonuna yeni bir düğüm eklemek için, son düğümün bir sonraki göstericisi artık boş yerine yeni düğümü işaret eder. Yeni düğümün önceki işaretçisi son düğümü gösterir. Ayrıca, yeni düğümün bir sonraki göstericisi boşa işaret eder, bu nedenle onu yeni bir son düğüm yapar.

Aşağıdaki program, listenin sonuna yeni düğümlerin eklenmesi ile çift bağlantılı bir listenin Java uygulamasını göstermektedir.

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

Çıktı:

Çift bağlantılı listenin düğümleri:
10 20 30 40 50

Çıktı - yeni düğümlerin eklenmesi

Listenin sonuna yeni bir düğüm eklemenin yanı sıra, listenin başına veya listenin arasına yeni bir düğüm de ekleyebilirsiniz. Okuyucuların işlemleri daha iyi anlayabilmesi için bu uygulamayı okuyucuya bırakıyoruz.

Java'da Dairesel Çift Bağlantılı Liste

Dairesel çift bağlantılı bir liste, karmaşık yapılardan biridir. Bu listede, çift bağlantılı listenin son düğümü, birinci düğümün adresini ve ilk düğüm, son düğümün adresini içerir. Bu nedenle, döngüsel çift bağlantılı bir listede, bir döngü vardır ve düğüm işaretçilerinin hiçbiri null olarak ayarlanmamıştır.

Aşağıdaki diyagram, dairesel çift bağlantılı listeyi göstermektedir.

döngüsel çift bağlantılı liste

Yukarıdaki diyagramda gösterildiği gibi, son düğümün bir sonraki göstericisi ilk düğümü gösterir. İlk düğümün önceki işaretçisi son düğümü gösterir.

yük ve performans testi arasındaki fark

Dairesel çift bağlantılı listelerin yazılım endüstrisinde geniş uygulamaları vardır. Böyle bir uygulama, bir çalma listesine sahip olan müzik uygulamasıdır. Çalma listesinde, tüm şarkıları çalmayı bitirdiğinizde, son şarkının sonunda otomatik olarak ilk şarkıya geri dönersiniz. Bu, döngüsel listeler kullanılarak yapılır.

Dairesel Çift Bağlantılı Listenin Avantajları:

Dairesel çift bağlantılı liste baştan sona veya kuyruktan başa geçebilir.
Baştan kuyruğa veya kuyruktan başa gitmek etkilidir ve yalnızca sabit zaman O (1) alır.
Fibonacci yığını dahil olmak üzere gelişmiş veri yapılarını uygulamak için kullanılabilir.

Dezavantajları:

Her düğümün önceki işaretçi için yer açması gerektiğinden, fazladan bellek gereklidir.
Dairesel çift bağlantılı bir liste üzerinde işlem yaparken birçok işaretçi ile uğraşmamız gerekir. İşaretçiler düzgün bir şekilde ele alınmazsa, uygulama bozulabilir.

Aşağıdaki Java programı, Dairesel çift bağlantılı listenin uygulanmasını göstermektedir.

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

Çıktı:

Dairesel çift bağlantılı liste: 40 50 60 70 80
Dairesel çift bağlantılı liste geriye doğru ilerliyor:
80 70 60 50 40

çıktı - Dairesel çift bağlantılı liste

Yukarıdaki programda listenin sonuna düğümü ekledik. Liste dairesel olduğundan, yeni düğüm eklendiğinde, yeni düğümün bir sonraki göstericisi ilk düğümü gösterecek ve ilk düğümün önceki göstericisi yeni düğümü gösterecektir.

Benzer şekilde, yeni düğümün önceki göstericisi, şimdi ikinci son düğüm olacak olan geçerli son düğümü gösterecektir. Listenin başında ve düğümler arasında yeni bir düğüm ekleme uygulamasını okuyuculara bırakıyoruz.

Sıkça Sorulan Sorular

S # 1) Çift Bağlantılı Liste dairesel olabilir mi?

Cevap: Evet. Daha karmaşık bir veri yapısıdır. Dairesel çift bağlantılı bir listede, ilk düğümün önceki göstericisi son düğümün adresini içerir ve son düğümün bir sonraki göstericisi, ilk düğümün adresini içerir.

S # 2) Nasıl Çift Dairesel Bağlantılı Liste oluşturursunuz?

Cevap: Çift döngüsel bağlantılı bir liste için bir sınıf oluşturabilirsiniz. Bu sınıfın içinde, düğümü temsil edecek statik bir sınıf olacaktır. Her düğüm iki işaretçi içerecektir - önceki ve sonraki ve bir veri öğesi. Daha sonra listeye düğüm eklemek ve listede gezinmek için işlemlere sahip olabilirsiniz.

S # 3) Çift Bağlantılı Liste doğrusal mı yoksa dairesel mi?

Cevap: Çift bağlantılı liste, doğrusal bir yapıdır, ancak kuyruğu başa dönük ve başı kuyruğu işaret eden dairesel, çift bağlantılı bir listedir. Dolayısıyla döngüsel bir listedir.

S # 4) Çift bağlantılı liste ile Dairesel bağlantılı liste arasındaki fark nedir?

Cevap: Çift bağlantılı bir liste, sırasıyla önceki ve sonraki işaretçileri kullanarak önceki ve sonraki düğümler hakkında bilgi tutan düğümlere sahiptir. Ayrıca, ilk düğümün önceki göstericisi ve son düğümün sonraki göstericisi, çift bağlantılı listede boş olarak ayarlanır.

Dairesel bağlantılı listede, başlangıç veya bitiş düğümleri yoktur ve düğümler bir döngü oluşturur. Ayrıca, döngüsel bağlantılı listede işaretçilerden hiçbiri boş değer olarak ayarlanmamıştır.

S # 5) Çift Bağlantılı Listenin Avantajları Nelerdir?

Cevap: Çift Bağlantılı Listenin Avantajları:

Hem ileri hem de geri yönde hareket ettirilebilir.
Önceki öğeyi bulmak için tüm listeyi taramamız gerekmediğinden ekleme işlemi daha kolaydır.
Önceki ve sonraki düğümlerin ve işlemenin daha kolay olduğunu bildiğimiz için silme etkilidir.

Sonuç

Bu eğitimde, Java'daki Doubly bağlantılı listeyi ayrıntılı olarak tartıştık. Çift bağlantılı bir liste, her bir düğümün önceki ve sonraki düğümlere işaretçiler içerdiği karmaşık bir yapıdır. Bu bağlantıların yönetimi bazen zordur ve uygun şekilde kullanılmazsa kodun bozulmasına neden olabilir.

Genel olarak, çift bağlantılı bir listenin işlemleri, hem önceki hem de sonraki işaretçilerimiz olduğu için listeyi geçmek için zamandan tasarruf edebileceğimizden daha verimlidir.

Dairesel çift bağlantılı liste daha karmaşıktır ve birinci düğümün önceki işaretçisiyle son düğüme işaret eden ve son düğümün bir sonraki göstericisinin ilk düğüme işaret ettiği dairesel bir model oluştururlar. Bu durumda da operasyonlar verimlidir.

Bununla, Java'daki bağlantılı liste ile işimiz bitti. Java'da arama ve sıralama teknikleriyle ilgili daha birçok öğretici için bizi izlemeye devam edin.

=> Özel Java Eğitimi Eğitim Dizisi İçin Burayı Ziyaret Edin.

Java'da Çift Bağlantılı Liste - Uygulama ve Kod Örnekleri