Linked List Data Structure sa Java

Ang iba't ibang istruktura ng data ay nilikha para sa iba't ibang layunin. Maaaring alam mo ang tungkol sa ArrayList (kung hindi pa rin, inirerekomenda naming basahin mo muna ang tungkol dito). Sa artikulong ito, matututuhan natin ang tungkol sa LinkedList at upang mapagtanto kung para saan ang koleksyong ito. Kung titingnan mo ang LinkList Java 8 (o mas bagong bersyon ng wika) source code ng klase (sa website ng Oracle o sa iyong IDE, kung sakaling may IDEA: crtl+B sa pangalan ng klase) makikita mo ang susunod na deklarasyon:

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

Sa ngayon, ang pinakamahalagang impormasyon mula sa code ay ang katotohanan na ang LinkedList ay nagpapatupad ng mga interface ng List at Deque . Pinapanatili ng interface ng Listahan ang pagkakasunud-sunod ng pagdaragdag ng mga item at nagbibigay-daan sa pag-access sa item ayon sa index. Sinusuportahan ng "ordinaryong" Queue ang pagdaragdag ng mga elemento sa dulo at pagkuha ng mga ito mula sa simula. Ang Deque ay isang two-way queue, at sinusuportahan nito ang pagdaragdag at pag-alis ng mga elemento mula sa magkabilang panig. Maaari mong isipin ito bilang isang kumbinasyon ng stack at queue. Kaya, ang LinkList ay isang pagpapatupad ng dalawang ito, at nagbibigay-daan ito sa amin na lumikha ng isang bidirectional queue na binubuo ng anumang mga bagay kabilang ang null. LinkedListay isang koleksyon ng mga elemento. Makikita natin ito sa source code ng klase, sa pagkakataong ito ay bigyang pansin ang mga field:

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

Ang bawat elemento, karaniwang tinatawag namin itong Node , ay naglalaman ng isang bagay at mga sanggunian sa dalawang magkatabing bagay - ang nakaraan at ang susunod. Samakatuwid, ito ay hindi masyadong epektibo sa mga tuntunin ng paggamit ng memorya. Dahil ang LinkList ay talagang isang bidirectional na istraktura, madali kaming magdagdag o mag-alis ng mga elemento mula sa magkabilang panig.

LinkedList Constructors

Bumalik sa source code, malalaman natin na ang LinkList ay may dalawang constructor

• Ang LinkList() na walang mga parameter ay ginagamit upang bumuo ng isang walang laman na listahan.
• >LinkedList(Collection<? extends E> c) ay para sa paglikha ng isang listahan na naglalaman ng mga elemento ng tinukoy na koleksyon, sa pagkakasunud-sunod, ang mga ito ay ibinalik ng iterator ng koleksyon.

Pahayag ng LinkList

Sa katunayan, ang isang naka-link na listahan (Java o sa anumang iba pang wika) ay binubuo ng isang sequence ng mga node. Ang bawat node ay idinisenyo upang mag-imbak ng isang bagay ng isang uri na tinukoy kapag lumilikha. Kaya upang lumikha ng LinkList , ang Java code ay ang susunod:

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

Mayroon kaming isang bagay upang panatilihin ang isang pagkakasunud-sunod ng mga integer at mga link sa mga kapitbahay. Gayunpaman, ito ay walang laman sa ngayon.

Mga Pangunahing Operasyon ng LinkList

Gaya ng dati, sa kaso ng Mga Koleksyon maaari kang maglagay ng mga elemento sa LinkedList (hanggang sa dulo nito o sa gitna), alisin mula doon, at kumuha ng elemento ayon sa index. Kaya narito sila:

• add(E element) Idinaragdag ang tinukoy na elemento sa dulo ng listahang ito;
• add(int index, E element) Ipinapasok ang elemento sa tinukoy na index ng posisyon ;
• get(int index) Ibinabalik ang elemento sa tinukoy na posisyon sa listahang ito;
• remove(int index) Tinatanggal ang elemento na nasa position index;
• remove(Object o) Tinatanggal ang unang paglitaw ng ? o elemento mula sa listahang ito kung naroon.
• remove() Kinukuha at inaalis ang unang elemento ng listahan.

Pagpapatupad ng naka-link na listahan sa Java, pagdaragdag at pag-alis ng mga elemento. Halimbawa

Subukan natin ang mga operasyong ito sa pagsasanay. Una, pagpapatupad ng Java LinkedList: paglikha ng LinkedList ng mga String, pagdaragdag doon ng 3 elemento. Pagkatapos ay alisin ang isa, pagkatapos ay magdagdag ng isa sa gitna.

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

Ang resulta ng pagpapatakbo ng program na ito:

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]

Ang LinkedList ay isang bahagi ng balangkas ng Koleksyon , maaari mong gamitin ang Iterator upang alisin ang mga elemento, pati na rin ang isang espesyal na iterator para sa mga listahan — ListIterator . Higit pa rito, ang mga pagpapatakbo na may iterator ay nagbibigay ng mga pangunahing benepisyo ng klase ng LinkList : mahusay na pagganap ng mga operasyong insert/delete. Gamit ang Iterator maaari kang makakuha ng patuloy na oras para sa kanila. Sa ibang pagkakataon sa artikulong ito, magsusulat kami ng halimbawa ng code upang ihambing ang ArrayList at LinkedList+Iterator

• Inaalis ng Iterator.remove() ang huling elementong ibinalik ng iterator na ito.
• Ang ListIterator.add(E element) ay naglalagay ng elemento sa listahan

Halimbawa ng Java LinkedList: kung paano gumagana ang Iterator

Narito mayroon kaming maliit na Java LinkedList Example code, kung saan sinusubukan naming magdagdag at magtanggal sa pamamagitan ng Iterator.

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

Ang resulta ng pagpapatakbo ng program na ito:

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

Higit pang Java LinkedList Operations:

• addFirst() , addLast() magdagdag ng elemento sa simula/pagtatapos ng isang listahan
• Tinatanggal ng clear() ang lahat ng elemento mula sa listahan
• contains(Object o) returns true kung ang listahan ay naglalaman ng o element.
• Ibinabalik ng indexOf(Object o) ang index ng unang paglitaw ng elementong o, o -1 kung wala ito sa listahan.
• pinapalitan ng set(int index, E element) ang elemento sa posisyon ng index ng elemento
• size()Ibinabalik ang dami ng mga elemento sa listahan.
• toArray() ay nagbabalik ng array na naglalaman ng lahat ng mga elemento ng listahan mula una hanggang sa huling elemento.

BTW bilang isang dalawang-sized na pila, ang LinkList sa Java ay may stack na mga partikular na operasyon:

• pop() na nagpa-pop ng isang elemento mula sa stack (kinakatawan ng listahan)
• push(E e) na nagtutulak ng elemento papunta sa stack (kinakatawan ng listahang ito)

Paano baligtarin ang LinkList: halimbawa

Narito ang isang maliit na halimbawa, isang sikat, ngunit isang madaling gawain para sa mga nagsisimula. Mayroon kaming LinkedList at dapat itong baligtarin. Ang pinakamadaling algorithm ay dumaan sa LinkedList sa reverse order at ilagay ang bawat elemento sa bago. Gayunpaman, marahil ay makakahanap ka ng isang mas mahusay na paraan? Narito ang code ng reverse linked list java program:

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

Ang resulta:

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

LinkedList vs ArrayList: kung kailan gagamitin ang una

Parehong ang LinkList at ArrayList ay mga pagpapatupad ng interface ng Listahan . Ipinapatupad ito ng LinkedList na may dobleng naka-link na listahan. Ipinapatupad ito ng ArrayList gamit ang isang dynamic na pagbabago ng laki ng array. Tulad ng alam mo na, ang bawat node ng LinkedList ay naglalaman ng Mga Bagay at dalawang sanggunian sa mga kapitbahay. Nangangahulugan iyon ng mga karagdagang gastos sa memorya para sa pag-iimbak ng mga sanggunian sa pagitan ng mga elemento sa kaso ng Java LinkedList . Ipinapatupad ito ng ArrayList na may dynamic na pagbabago ng laki ng array. Magkamukha ang ilan sa mga operasyon ng LinkList at ArrayList , ngunit gumagana ang mga ito sa ibang paraan. Sa ArrayListkaso, manipulahin mo ang mga panloob na array, sa LinkList — na may mga sanggunian. Ang ArrayList ay ang pinakasikat na pagpapatupad ng Listahan . Tiyak na dapat mong gamitin ang ArrayList kapag ang pag-access sa index ay isang priyoridad dahil ang mga operasyong ito ay ginagawa nang tuluy-tuloy. Ang pagdaragdag sa dulo ng listahan sa karaniwan ay ginagawa din sa palagiang oras. Higit pa rito, ang ArrayList ay walang karagdagang gastos para sa pag-iimbak ng isang grupo ng mga elemento. Maaari mong bilangin bilang Cons ang bilis ng pagpasok at pag-alis ng mga operasyon kapag hindi ito nagawa sa dulo ng listahan. LinkedListay mas kapaki-pakinabang sa kaso ng pagpasok at pagtanggal ng pagganap ng mga pagpapatakbo sa ilang mga paraan: kung gumagamit ka ng mga iterator ito ay nangyayari sa patuloy na oras. Ang mga operasyon sa pag-access sa pamamagitan ng index ay isinasagawa sa pamamagitan ng paghahanap mula sa simula ng dulo (alinman ang mas malapit) sa nais na elemento. Gayunpaman, huwag kalimutan ang tungkol sa mga karagdagang gastos para sa pag-iimbak ng mga sanggunian sa pagitan ng mga elemento. Kaya narito ang mga karaniwang operasyon ng LinkList at ArrayList na may mga algorithmic runtime. Ang N ay tumutukoy sa bilang ng mga item na nasa listahan na. Nangangahulugan ang O(N) na sa pinakamasamang kaso dapat tayong "maglakad" sa buong listahan hanggang sa matagpuan ang kinakailangang posisyon, halimbawa, para sa pagpasok ng bagong elemento sa listahan. O(1)Nangangahulugan na ang operasyon ay nangyayari sa pare-parehong oras, independyente sa bilang ng mga item.

Pagiging Kumplikado ng Oras ng LinkList

ArrayList Time Complexity

Kailan gagamitin ang LinkList: Halimbawa

Talagang, ArrayList ang pinakasikat na pagpapatupad ng Listahan . Gayunpaman, maaari mong matugunan ang mga sitwasyon, kapag ang mga pagpapatakbo ng pagdaragdag/pag-alis ay kinakailangan nang madalas. Sa kasong iyon, maaaring maging kapaki-pakinabang ang LinkedList kasama ang Iterator. Narito ang isang halimbawa. Mayroon kaming mahabang listahan, at dapat naming tanggalin ang bawat elemento sa listahang ito. Gawin natin ang gawaing ito sa ArrayList at LinkedList + Iterator . Inihahambing namin ang oras ng bawat operasyon at i-print ito sa console. Narito ang code:

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

Resulta para sa ArrayList:

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

Resulta para sa LinkedList:

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

Tulad ng nakikita mo sa kasong ito, ang LinkList ay mas epektibo. Maging tapat tayo. Sa totoong software development, ang LinkList ay isang uri ng pambihirang kaganapan. Gayunpaman, dapat malaman ng isang propesyonal ang tungkol sa pagkakaroon ng istruktura ng data na ito at ang mga pakinabang nito. Kung sa totoong code ang LinkList ay isang bihirang panauhin, sa mga panayam ng Java Junior ito ay napakapopular. Gayunpaman, narito ang isinulat ni Joshua Bloch tungkol sa LinkedList :

AddOn: Singly Linked List Java

Walang Singly Linked List sa classical Collection sa Java, ang Singly Linked List ay isang istraktura kung saan ang bawat node ay naglalaman ng isang Object at isang reference sa susunod na Node, ngunit hindi para sa nauna. Ang Java LinkedList ay dalawang-link, ngunit walang nakikialam sa iyo upang lumikha ng iyong sariling Structure ng Data, tulad ng Singly ,code>Linked List. Narito ang ilang hakbang upang malutas ang mga gawaing ito:

1. Lumikha ng klase ng Node na may dalawang katangian, data at susunod. Susunod ay isang sanggunian sa susunod na node.
2. Lumikha ng FirstLast na klase na may dalawang katangian, ulo, at buntot.
3. Lumikha ng paraan ng add() upang magdagdag ng bagong node sa listahan. Suriin kung ang listahan ay walang laman muna ( ulo == null ). Kung gayon, ang ulo at buntot ay tumutukoy sa bagong node. Kung ang listahan ay walang laman, ang bagong node ay idaragdag sa dulo, kaya ang susunod na katangian ng buntot ay tumutukoy sa idinagdag na node at ang bagong node ay magiging buntot ng listahan.

Sa pamamagitan ng paraan, maaari mong subukang lumikha ng iyong sariling LinkList bilang isang ehersisyo din. Good luck sa iyong pag-aaral.