Java'da veri yapıları ve algoritmalar, Bölüm 4: Tekil bağlantılı listeler

Bu eğitim dizisinin 3. Bölümünde tanıtılan diziler gibi, bağlantılı listeler, daha karmaşık veri yapılarının dayandırılabileceği temel bir veri yapısı kategorisidir. Bununla birlikte, bir dizi öğeden farklı olarak, bağlantılı bir liste , her düğümün dizideki önceki ve sonraki düğüme bağlı olduğu bir düğüm dizisidir. Bir düğümün kendine başvuran bir sınıftan oluşturulmuş bir nesne olduğunu ve kendine başvuran bir sınıfın , başvuru türü sınıf adı olan en az bir alana sahip olduğunu hatırlayın . Bağlantılı bir listedeki düğümler, bir düğüm referansı aracılığıyla bağlanır. İşte bir örnek:

 class Employee { private int empno; private String name; private double salary; public Employee next; // Other members. }

Bu örnekte, Employeekendi nextalanında tür olduğu için kendine başvuran bir sınıftır Employee. Bu alan bir bağlantı alanı örneğidir çünkü kendi sınıfındaki başka bir nesneye (bu durumda başka bir Employeenesneye) bir başvuru depolayabilir .

Bu eğitim, Java programlamasında tekil bağlantılı listelerin giriş ve çıkışlarını tanıtır. Tekil bağlantılı bir liste oluşturma, tekil bağlantılı bir listeye düğüm ekleme, tek bağlantılı bir listeden düğüm silme, tekil bağlantılı bir listeyi başka bir tek bağlantılı listeyle bitirme ve tekil bağlantılı bir listeyi ters çevirme işlemlerini öğreneceksiniz. Ayrıca, tek tek bağlantılı listeleri sıralamak için en sık kullanılan algoritmaları inceleyeceğiz ve Ekleme Sıralama algoritmasını gösteren bir örnekle sonlandıracağız.

indir Kodu alın Bu makale için üç örnek uygulamayı indirin. JavaWorld için Jeff Friesen tarafından düzenlendi.

Tek bağlantılı liste nedir?

Bir tek başına bağlantılı liste her bir düğüm tek bir bağlantı alanı olan, bağlantılı bir düğümler listesidir. Bu veri yapısında, bir referans değişkeni, birinci (veya üst) düğüme bir referans içerir; her düğüm (son veya alt düğüm hariç) bir sonrakine bağlanır; ve son düğümün bağlantı alanı, listenin sonunu belirtmek için boş referans içerir. Referans değişkeni genel olarak adlandırılsa da top, istediğiniz herhangi bir adı seçebilirsiniz.

Şekil 1, üç düğümlü tek bağlantılı bir liste sunar.

Aşağıda, tekil bağlantılı bir liste için sözde kod verilmiştir.

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next END DECLARE DECLARE Node top = NULL 

Nodebir nameveri alanı ve bir nextbağlantı alanı olan kendine başvuran bir sınıftır . tek bağlantılı bir listedeki ilk nesneye bir referansı tutan toptipte bir referans değişkenidir . Liste henüz mevcut olmadığından, 'nin başlangıç ​​değeri .NodeNodetopNULL

Java'da tek bağlantılı bir liste oluşturma

Tek bir Nodenesne ekleyerek tek bağlantılı bir liste oluşturursunuz . Aşağıdaki sözde kod bir Nodenesne oluşturur , referansını atar top, veri alanını başlatır NULLve bağlantı alanına atar :

 top = NEW Node top.name = "A" top.next = NULL 

Şekil 2, bu sözde koddan ortaya çıkan ilk tek bağlantılı listeyi göstermektedir.

Bu işlemin zaman karmaşıklığı O (1) - sabittir. O (1) 'in "Big Oh of 1" olarak telaffuz edildiğini hatırlayın. (Veri yapılarını değerlendirmek için zaman ve alan karmaşıklığı ölçümlerinin nasıl kullanıldığına dair bir hatırlatma için Bölüm 1'e bakın.)

Tek bağlantılı bir listeye düğüm ekleme

Tek bağlantılı bir listeye bir düğüm eklemek, tek bağlantılı bir liste oluşturmaktan biraz daha karmaşıktır çünkü dikkate alınması gereken üç durum vardır:

  • İlk düğümden önce ekleme.
  • Son düğümden sonra ekleme.
  • İki düğüm arasına ekleme.

İlk düğümden önce ekleme

Yeni düğümün referansını yeni düğümün bağlantı alanına atayarak ve yeni düğümün referansını topdeğişkene atayarak ilk düğümden önce yeni bir düğüm eklenir . Bu işlem aşağıdaki sözde kodla gösterilmiştir:

 DECLARE Node temp temp = NEW Node temp.name = "B" temp.next = top top = temp 

Ortaya çıkan iki Nodeliste Şekil 3'te görünür.

Bu işlemin zaman karmaşıklığı O (1).

Son düğümden sonra ekleme

Yeni düğümün bağlantı alanına null atanarak , son düğümü bulmak için tek bağlı listeden geçerek ve aşağıdaki sözde kodun gösterdiği gibi yeni düğümün son düğümün bağlantı alanına referansını atayarak son düğümden sonra yeni bir düğüm eklenir :

 temp = NEW Node temp.name = "C" temp.next = NULL DECLARE Node temp2 temp2 = top // We assume top (and temp2) are not NULL // because of the previous pseudocode. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 now references the last node. temp2.next = temp 

Şekil 4, A'dan Nodesonra C'nin eklenmesinden sonraki listeyi göstermektedir Node.

Bu işlemin zaman karmaşıklığı O ( n ) - doğrusaldır. Son düğüme bir referans korunarak, zaman karmaşıklığı O (1) 'e yükseltilebilir. Bu durumda son düğümü aramak gerekli olmayacaktır.

İki düğüm arasına ekleme

İki düğüm arasına bir düğüm eklemek en karmaşık durumdur. Yeni düğümden önce gelen düğümü bulmak için listeyi geçerek, bulunan düğümün bağlantı alanındaki referansı yeni düğümün bağlantı alanına atayarak ve yeni düğümün referansını bulunan düğümün bağlantısına atayarak, iki düğüm arasına yeni bir düğüm eklersiniz. alan. Aşağıdaki sözde kod, bu görevleri gösterir:

 temp = NEW Node temp.name = "D" temp2 = top // We assume that the newly created Node inserts after Node // A and that Node A exists. In the real world, there is no // guarantee that any Node exists, so we would need to check // for temp2 containing NULL in both the WHILE loop's header // and after the WHILE loop completes. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 now references Node A. temp.next = temp2.next temp2.next = temp 

Şekil 5, s A ve C Nodearasına D' nin eklenmesinin ardından listeyi göstermektedir Node.

Bu işlemin zaman karmaşıklığı O ( n ).

Tek bağlantılı bir listeden düğümleri silme

Tek bağlantılı bir listeden bir düğümü silmek, tekil bağlantılı bir liste oluşturmaktan da biraz daha karmaşıktır. Ancak dikkate alınması gereken sadece iki durum vardır:

  • İlk düğümün silinmesi.
  • İlk düğüm dışındaki herhangi bir düğümün silinmesi.

İlk düğümün silinmesi

İlk düğümün silinmesi, ilk düğümün bağlantı alanındaki bağlantının ilk düğüme başvuran değişkene atanmasını içerir, ancak yalnızca bir ilk düğüm olduğunda:

 IF top NE NULL THEN top = top.next; // Reference the second Node (or NULL when there's only one Node). END IF 

Şekil 6 Node, birincinin silindiği bir listenin öncesi ve sonrası görünümlerini sunar . Düğüm Bkaybolur ve NodeA birinci olur Node.

Bu işlemin zaman karmaşıklığı O (1).

İlk düğüm hariç herhangi bir düğümün silinmesi

Herhangi bir düğümü silmek, ancak ilk düğüm, silinecek düğümden önce gelen düğümün konumlandırılmasını ve silinecek düğümün bağlantı alanındaki referansın önceki düğümün bağlantı alanına atanmasını içerir. Aşağıdaki sözde kodu düşünün:

 IF top NE NULL THEN temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // We assume that temp references Node A. temp.next = temp.next.next // Node D no longer exists. END IF 

Şekil 7, bir ara Nodemaddenin silindiği bir listenin öncesi ve sonrası görünümlerini sunar . NodeD kaybolur.

Bu işlemin zaman karmaşıklığı O ( n ).

Örnek 1: Tek bağlantılı bir liste oluşturun, ekleyin ve silin

SLLDemoTek bağlantılı bir listedeki düğümlerin nasıl oluşturulacağını, ekleneceğini ve silineceğini gösteren bir Java uygulaması oluşturdum . Liste 1, bu uygulamanın kaynak kodunu gösterir.

Liste 1. Tek bağlantılı listeler için Java uygulama demosu (SSLDemo.java, sürüm 1)

 public final class SLLDemo { private static class Node { String name; Node next; } public static void main(String[] args) { Node top = null; // 1. The singly linked list does not exist. top = new Node(); top.name = "A"; top.next = null; dump("Case 1", top); // 2. The singly linked list exists and the node must be inserted // before the first node. Node temp; temp = new Node(); temp.name = "B"; temp.next = top; top = temp; dump("Case 2", top); // 3. The singly linked list exists and the node must be inserted // after the last node. temp = new Node(); temp.name = "C"; temp.next = null; Node temp2; temp2 = top; while (temp2.next != null) temp2 = temp2.next; temp2.next = temp; dump("Case 3", top); // 4. The singly linked list exists and the node must be inserted // between two nodes. temp = new Node(); temp.name = "D"; temp2 = top; while (temp2.name.equals("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump("Case 4", top); // 5. Delete the first node. top = top.next; dump("After first node deletion", top); // 5.1 Restore node B. temp = new Node(); temp.name = "B"; temp.next = top; top = temp; // 6. Delete any node but the first node. temp = top; while (temp.name.equals("A") == false) temp = temp.next; temp.next = temp.next.next; dump("After D node deletion", top); } private static void dump(String msg, Node topNode) { System.out.print(msg + " "); while (topNode != null) { System.out.print(topNode.name + " "); topNode = topNode.next; } System.out.println(); } } 

Liste 1'i aşağıdaki gibi derleyin:

 javac SLLDemo.java 

Ortaya çıkan uygulamayı aşağıdaki gibi çalıştırın:

 java SLLDemo 

Aşağıdaki çıktıyı gözlemlemelisiniz:

 Case 1 A Case 2 B A Case 3 B A C Case 4 B A D C After first node deletion A D C After D node deletion B A C 

Tekil bağlantılı listeleri birleştirme

You might occasionally need to concatenate a singly linked list to another singly linked list. For example, suppose you have a list of words that start with letters A through M and another list of words starting with letters N through Z, and you want to combine these lists into a single list. The following pseudocode describes an algorithm for concatenating one singly linked list to another:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Assume code that creates top1-referenced singly linked list. // Assume code that creates top2-referenced singly linked list. // Concatenate top2-referenced list to top1-referenced list. IF top1 EQ NULL top1 = top2 END END IF // Locate final Node in top1-referenced list. DECLARE Node temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Concatenate top2 to top1. temp.next = top2 END 

In the trivial case, there is no top1-referenced list, and so top1 is assigned top2's value, which would be NULL if there was no top2-referenced list.

This operation has a time complexity of O(1) in the trivial case and a time complexity of O(n) otherwise. However, if you maintain a reference to the last node, there's no need to search the list for this node; the time complexity changes to O(1).

Inverting a singly linked list

Another useful operation on a singly linked list is inversion, which reverses the list's links to let you traverse its nodes in the opposite direction. The following pseudocode reverses the top1-referenced list's links:

 DECLARE Node p = top1 // Top of original singly linked list. DECLARE Node q = NULL // Top of reversed singly linked list. DECLARE Node r // Temporary Node reference variable. WHILE p NE NULL // For each Node in original singly linked list ... r = q // Save future successor Node's reference. q = p // Reference future predecessor Node. p = p.next // Reference next Node in original singly linked list. q.next = r // Link future predecessor Node to future successor Node. END WHILE top1 = q // Make top1 reference first Node in reversed singly linked list. END 

This operation has a time complexity of O(n).

Example #2: Concatenating and inverting a singly linked list

SLLDemoJava uygulamasının birleştirme ve ters çevirmeyi gösteren ikinci bir sürümünü oluşturdum . Liste 2, bu uygulamanın kaynak kodunu gösterir.