Java'da Bağlantılı Liste Veri Yapısı

Farklı amaçlar için farklı veri yapıları oluşturulur. ArrayList'i biliyor olabilirsiniz (hala bilmiyorsanız, önce onu okumanızı öneririz). Bu yazıda LinkedList'i öğreneceğiz ve bu koleksiyonun ne işe yaradığını anlayacağız. LinkedList Java 8 (veya dilin sonraki sürümü) sınıf kodu kaynağına bakarsanız (Oracle web sitesinde veya IDE'nizde, sınıf adında IDEA: crtl+B olması durumunda) bir sonraki bildirimi görürsünüz:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Şu anda koddan gelen en önemli bilgi, LinkedList'in List ve Deque arayüzlerini uyguladığı gerçeğidir . Liste arayüzü, öğe ekleme sırasını korur ve öğeye dizine göre erişim sağlar. "Sıradan" Sıra , öğelerin sonuna kadar eklenmesini ve baştan çıkarılmasını destekler. Deque iki yönlü bir sıradır ve her iki taraftan öğe eklemeyi ve kaldırmayı destekler. Yığın ve kuyruğun bir kombinasyonu olarak düşünebilirsiniz. Dolayısıyla, LinkedList bu ikisinin bir uygulamasıdır ve null dahil herhangi bir nesneden oluşan çift yönlü bir sıra oluşturmamıza izin verir. Bağlantılı listeelementler topluluğudur. Sınıfın kod kaynağında görebiliriz, bu sefer alanlara dikkat edin:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

Genellikle Düğüm olarak adlandırdığımız her öğe , bir nesne içerir ve önceki ve sonraki iki komşu nesneye gönderme yapar. Bu nedenle, hafıza kullanımı açısından çok etkili değildir. LinkedList aslında çift yönlü bir yapı olduğundan , her iki taraftan da kolayca eleman ekleyebilir veya kaldırabiliriz.

LinkedList Oluşturucuları

Kod kaynağına dönersek, LinkedList'in iki kurucusu olduğunu görebiliriz.

• LinkedList() parametresiz boş bir liste oluşturmak için kullanılır.
• >LinkedList(Collection<? extensions E> c), belirtilen koleksiyonun öğelerini, koleksiyonun yineleyicisi tarafından döndürülme sırasına göre içeren bir liste oluşturmak içindir.

LinkedList Bildirimi

Aslında, bağlantılı bir liste (Java veya başka bir dilde) bir dizi düğümden oluşur. Her düğüm, oluşturulurken tanımlanan türden bir nesneyi depolamak için tasarlanmıştır. Dolayısıyla, LinkedList oluşturmak için sıradaki Java kodudur:

LinkedList<Integer> myList = new LinkedList<>();

Bir tamsayı dizisini ve komşulara bağlantıları tutacak bir nesnemiz var. Ancak şu anda boş.

LinkedList Ana İşlemleri

Her zamanki gibi, Koleksiyonlar söz konusu olduğunda LinkedList'e öğeler koyabilir (sonuna veya ortasına), oradan kaldırabilir ve dizine göre bir öğe alabilirsiniz. İşte buradalar:

• add(E element) Belirtilen elemanı bu listenin sonuna ekler;
• add(int index, E element) Elemanı belirtilen konuma ekler index ;
• get(int index) Bu listede belirtilen konumdaki elemanı döndürür;
• remove(int index) Dizinde konumdaki elemanı siler;
• remove(Object o) ? öğesinin ilk geçtiği yeri kaldırır. o öğe varsa bu listeden.
• remove() Listenin ilk öğesini alır ve kaldırır.

Java'da bağlantılı liste uygulaması, öğe ekleme ve kaldırma. Örnek

Bu işlemleri uygulamalı olarak deneyelim. İlk olarak, Java LinkedList uygulaması: bir LinkedList of Strings oluşturmak, oraya 3 öğe eklemek. Sonra birini çıkarın, ardından ortasına bir tane ekleyin.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Bu programı çalıştırmanın sonucu:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

LinkedList , Koleksiyon çerçevesinin bir parçasıdır , öğeleri kaldırmak için Iterator'ı ve listeler için özel bir yineleyiciyi kullanabilirsiniz - ListIterator . Dahası, yineleyicili işlemler LinkedList sınıfının ana faydalarını sağlar: iyi ekleme/silme işlemleri performansı. Yineleyiciyi kullanarak onlar için sabit bir süre elde edebilirsiniz. Bu makalenin ilerleyen kısımlarında, ArrayList ve LinkedList+Iterator'ı karşılaştırmak için bir kod örneği yazacağız.

• Iterator.remove(), bu yineleyici tarafından döndürülen son öğeyi kaldırır.
• ListIterator.add(E element) listeye bir eleman ekler

Java LinkedList Örneği: Yineleyici nasıl çalışır?

Burada , Iterator aracılığıyla ekleme ve silmeyi denediğimiz küçük bir Java LinkedList Örnek kodumuz var .

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

Bu programı çalıştırmanın sonucu:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

Daha Fazla Java LinkedList İşlemi:

• addFirst() , addLast() bir listenin başına/sonuna bir öğe ekler
• clear() listeden tüm öğeleri kaldırır
• include(Object o), liste o öğesini içeriyorsa true değerini döndürür.
• indexOf(Object o), o öğesinin ilk geçtiği dizinin dizinini veya listede yoksa -1'i döndürür.
• set(int dizini, E öğesi), dizin konumundaki öğeyi öğeyle değiştirir
• size() Listedeki öğelerin miktarını döndürür.
• toArray(), ilk öğeden son öğeye kadar tüm liste öğelerini içeren bir dizi döndürür.

BTW iki boyutlu bir sıra olduğundan, Java'daki LinkedList yığına özgü işlemlere sahiptir:

• yığından bir öğe çıkaran pop() (liste tarafından temsil edilir)
• push(E e) bir öğeyi yığına iter (bu liste tarafından temsil edilir)

LinkedList nasıl tersine çevrilir: örnek

İşte küçük bir örnek, popüler ama yeni başlayanlar için kolay bir iş. Bir LinkedList'imiz var ve onu tersine çevirmeliyiz. En kolay algoritma, LinkedList'i ters sırayla gözden geçirmek ve her öğeyi yenisine koymaktır. Ancak, belki daha iyi bir yol bulacaksınız? İşte ters bağlantılı liste java programının kodu:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

Sonuç:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList vs ArrayList: ilki ne zaman kullanılır?

Hem LinkedList hem de ArrayList, List arayüzünün uygulamalarıdır . LinkedList, onu çift bağlantılı bir listeyle uygular. ArrayList, onu dinamik olarak yeniden boyutlandıran bir dizi kullanarak uygular. Bildiğiniz gibi, LinkedList'in her düğümü, Nesneler ve komşulara iki referans içerir. Bu, Java LinkedList durumunda öğeler arasında referansları depolamak için ek bellek maliyetleri anlamına gelir . ArrayList, onu dinamik olarak yeniden boyutlandıran bir dizi ile uygular. LinkedList ve ArrayList işlemlerinden bazıları aynı görünür, ancak farklı şekilde çalışırlar. ArrayList'te _durumda, dahili dizilerle, LinkedList'te - referanslarla manipüle edersiniz . ArrayList , en popüler List uygulamasıdır. Bu işlemler sabit zamanda yapıldığından, dizin erişimi öncelikli olduğunda ArrayList'i kesinlikle kullanmalısınız . Ortalama olarak listenin sonuna ekleme de sabit sürede yapılır. Dahası, ArrayList'in bir grup öğeyi depolamak için ek maliyeti yoktur. Listenin sonunda yapılmadığı takdirde ekleme ve çıkarma işlemlerinin hızını Eksi olarak sayabilirsiniz. Bağlantılı listebazı yönlerden ekleme ve silme işlemleri performansında daha kullanışlıdır: yineleyiciler kullanırsanız, sabit zamanda gerçekleşir. İndeks bazında erişim işlemleri, sonun başından (hangisi daha yakınsa) istenilen elemana kadar arama yapılarak gerçekleştirilir. Ancak, öğeler arasında referansları depolamak için ek maliyetleri unutmayın. İşte algoritmik çalışma zamanları ile standart LinkedList ve ArrayList işlemleri. N, listede zaten bulunan öğelerin sayısını ifade eder. O(N), en kötü durumda, örneğin listeye yeni öğenin eklenmesi için gerekli konum bulunana kadar tüm listede "yürümemiz" gerektiği anlamına gelir. O(1)işlemin, öğe sayısından bağımsız olarak sabit zamanda gerçekleştiği anlamına gelir.

LinkedList Zaman Karmaşıklığı

ArrayList Zaman Karmaşıklığı

LinkedList ne zaman kullanılır: Örnek

Kesinlikle, ArrayList en popüler List uygulamasıdır. Ancak, ekleme/kaldırma işlemlerine çok sık ihtiyaç duyulan durumlarla karşılaşabilirsiniz. Bu durumda, Iterator ile birlikte LinkedList faydalı olabilir. İşte bir örnek. Uzun bir listemiz var ve bu listedeki her öğeyi silmeliyiz. Bu görevi ArrayList ve LinkedList + Iterator ile yapalım . Her işlemin zamanını karşılaştırır ve konsola yazdırırız. İşte kod:

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

ArrayList için sonuç:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

LinkedList için sonuç:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

Bu durumda görebileceğiniz gibi, LinkedList çok daha etkilidir. Dürüst olalım. Gerçek yazılım geliştirmede LinkedList kullanımı nadir görülen bir olaydır. Bununla birlikte, bir profesyonel bu veri yapısının varlığını ve avantajlarını bilmelidir. Gerçek kodda LinkedList nadir bir konuksa, Java Junior röportajlarında çok popülerdir. Yine de, Joshua Bloch'un LinkedList hakkında yazdıkları :

AddOn: Tek Bağlantılı Liste Java

Java'da klasik Koleksiyon arasında Tek Bağlantılı Liste yoktur , Tek Bağlantılı Liste, her düğümün bir Nesne ve bir sonraki Düğüme referans içerdiği, ancak bir önceki Düğüme referans içermediği bir yapıdır. Java LinkedList iki bağlantılıdır, ancak Singly ,code>Linked List gibi kendi Veri Yapınızı oluşturmanıza kimse müdahale etmez. Bu görevleri çözmek için bazı adımlar şunlardır:

1. Data ve next olmak üzere iki özniteliğe sahip bir Düğüm sınıfı oluşturun. Sonraki, sonraki düğüme bir referanstır.
2. Head ve tail olmak üzere iki özelliğe sahip FirstLast sınıfı oluşturun .
3. Listeye yeni bir düğüm eklemek için bir add() yöntemi oluşturun. Önce listenin boş olup olmadığını kontrol edin ( head == null ). Eğer öyleyse, baş ve kuyruk yeni düğümü ifade eder. Liste boş değilse, yeni düğüm sona eklenecektir, böylece kuyruğun bir sonraki özelliği eklenen düğümü ifade eder ve yeni düğüm listenin kuyruğu olur.

Bu arada , bir alıştırma olarak kendi LinkedList'inizi oluşturmayı da deneyebilirsiniz . Öğrenmende iyi şanslar.