Makala
Başla
Öwrenip başlaň
JavaRush /Java Blog /Random-TK /Java-da LinkedList
Зепп Бранниган
Dereje

Java-da LinkedList

Toparda çap edildi
Salam! Recenthli soňky leksiýalar ArrayList sanawyny öwrenmäge bagyşlandy . Bu maglumat gurluşy örän amatly we köp meseläni çözmäge mümkinçilik berýär. Şeýle-de bolsa, Java-da başga-da köp maglumat gurluşy bar. Näme üçin? Ilki bilen, bar bolan meseleleriň gerimi gaty giň we dürli meseleler üçin dürli maglumat gurluşlary has täsirli . Bu gün täze gurluş - iki gezek baglanyşdyrylan LinkedList sanawy bilen tanyşarys . Onuň nähili işleýändigini, näme üçin iki esse baglanyşdyrylýandygyny we ArrayList -den nähili tapawutlanýandygyny öwreneliň . “LinkedList” -de elementler aslynda zynjyrdaky baglanyşyklardyr. Her element, saklaýan maglumatlaryna goşmaça, öňki we indiki element bilen baglanyşygy bar . Bu baglanyşyklar bir elementden beýlekisine geçmäge mümkinçilik berýär. Munuň ýaly döredildi: 
public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Moscow");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}
Netije: 

[Hello World! My name is Earl, I love Java, I live in Moscow]
Sanawymyzyň gurluşy şeýle bolar: LinkedList - 2Geliň, täze elementiň nädip goşulandygyny göreliň. Bu ulanylýar add(). 
earlBio.add(str2);
Bu setir kody ýazylanda, sanawymyz bir elementden - setirden durýar str1. Suratda indiki näme bolýandygyny göreliň: LinkedList - 3Netijede str2, str1olarda saklanýan baglanyşyklar arkaly birleşiň nextwe previous: LinkedList - 4Indi iki gezek baglanyşdyrylan sanawyň esasy ideýasyna düşünmeli. Elementler LinkedListbu baglanyşyk zynjyrynyň kömegi bilen ýekeje sanawdyr. Içinde ýa-da şuňa LinkedListmeňzeş ArrayListbir zat ýok. “ArrayList” bilen işleýänleriň hemmesi (umuman alanyňda) içerki massiw bilen işlemek üçin gelýär. Withhli işler LinkedListbaglanyşyklary üýtgetmek bilen baglanyşykly. Sanawyň ortasyna bir element goşmak bilen muny aýdyň görkezýär: 
public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Moscow");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}
Görşüňiz ýaly, artykmaç ýüklenen usul add()täze element üçin belli bir görkezijini kesgitlemäge mümkinçilik berýär. Bu ýagdaýda, we str2arasynda bir setir goşmak isleýäris . Içinde boljak zat: Içerki baglanyşyklary üýtgetmegiň netijesinde element sanawa üstünlikli goşulýar: Indi 3 elementiň hemmesi baglanyşdy. Zynjyryň boýundaky birinji elementden iň soňky we yza gidip bilersiňiz. Goýmany has az düşündik, ýöne elementleri pozmak hakda näme? Işleýiş ýörelgesi birmeňzeş. Diňe aýrylýan elementiň “gapdallarynda” iki elementiň baglanyşyklaryny täzeden kesgitleýäris: str1str3LinkedList - 5str2LinkedList - 6next
Java-университет 
public class Main {

   public static void main(String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Moscow");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}
1-nji indeks bilen elementi pozsak (bu sanawyň ortasynda): LinkedList - 7Baglanyşyklary täzeden kesgitlänimizden soň, islenýän netijäni alarys: LinkedList - 8Öçürmekden tapawutlylykda, ArrayListmassiw elementleriniň üýtgemegi we şuňa meňzeşler ýok. str1Diňe elementleriň we elementleriň salgylanmalaryny täzeden kesgitleýäris str3. Indi biri-birine yşarat edýärler we obýekt str2bu baglanyşyk zynjyryndan “çykdy” we indi sanawyň bir bölegi däl.

Usullara syn

Usullary LinkedListbilen köp meňzeşligi bar . Mysal üçin , ,,,, ( sanawdaky element), (çalyşmak bilen bir element goýmak) ýaly ArrayListusullar iki synpda-da bar. (Mysalda bilşimiz ýaly we ) olaryň köpüsi içerde başgaça işleýärler, ýöne ahyrynda şol bir zady edýärler. Şeýle-de bolsa, sanawyň başy we soňy bilen işlemek üçin aýratyn usullary bar, olar ýok : add()remove()indexOf()clear()contains()set()size()add()remove()LinkedListArrayList
  • addFirst(), addLast(): sanawyň başyna / soňuna element goşmagyň usullary
public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}
Netije: 

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]
Netijede, Ford sanawyň başynda, ahyrynda bolsa Fiat boldy.
  • peekFirst(), peekLast(): sanawyň birinji / soňky elementini gaýtaryň. nullSanaw boş bolsa gaýdyp gel .
public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}
Netije: 

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
  • pollFirst(), pollLast(): sanawyň birinji / soňky elementini yzyna gaýtaryň we sanawdan aýyryň . nullSanaw boş bolsa gaýdyp gel
public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println("What's left on the list?");
   System.out.println(cars);
}
Netije: 

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]
  • toArray(): sanaw elementleriniň toplumyny görkezýär
public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}
Netije: 

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
LinkedListIndi onuň nähili işleýändigini we nähili tapawutlanýandygyny bilýäris ArrayList. Ony ulanmagyň peýdalary näme LinkedList? Ilki bilen sanawyň ortasy bilen işlemekde . Ortada goýmak we pozmak LinkedListöňküsinden has ýönekeý ArrayList. Diňe goňşy elementleriň baglanyşyklaryny täzeden kesgitleýäris, gereksiz element bolsa baglanyşyk zynjyryndan “çykýar”. Bizde ArrayList:
  • ýeterlik ýeriň bardygyny barlaň (salýan wagtyňyz)
  • ýeterlik bolmasa, täze bir massiw dörediň we maglumatlary şol ýere göçüriň (ýelmende)
  • bir elementi poz / goý we beýleki elementleri sag / çepe geçir (işiň görnüşine baglylykda). Mundan başga-da, bu prosesiň çylşyrymlylygy sanawyň ululygyna baglydyr. 10 elementi göçürmek / göçürmek bir zat, ýöne million element bilen edil şonuň ýaly etmek düýbünden başga zat.
.Agny, programmaňyzda goýmak / pozmak amallary sanawyň ortasynda ýygy-ýygydan ýüze çyksa, has LinkedListçalt bolmaly ArrayList.

Teoriýa boýunça

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start=System.currentTimeMillis();

       for(int i=0;i<100;i++){
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time to run for LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}
Netije: 

Время работы для LinkedList (в мorсекундах) = 1873
public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start=System.currentTimeMillis();

       for (int i=0;i<100;i++){
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time to run for ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}
Netije: 

Время работы для ArrayList (в миллисекундах) = 181
Birden! LinkedListHas täsirli bolmaly - sanawyň ortasyna 100 element girizip, has täsirli bolmaly bir operasiýa ýerine ýetirýän ýaly . Sanawymyz ullakan - 5000 000 element: ArrayListher gezek salanymyzda iki million elementi üýtgetmeli bolduk! Victoryeňişiniň sebäbi näme? Ilki bilen, belli bir wagtyň içinde bir elemente girilýär . ArrayListGörkezeniňizde: 
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
soň [2_000_000] ýagdaýynda ArrayListbu ýatda belli bir salgy, sebäbi içinde bir massiw bar. Bu LinkedListmassiw ýok. Baglanyşyk zynjyry boýunça 2_000_000 element belgisini gözlär. Onuň üçin bu ýatda galan salgy däl, henizem ýetilmeli baglanyşyk: 

fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next………
Netijede, sanawyň ortasyna her bir goýulma (pozulma) bilen, ArrayListýatda saklanmaly takyk adresi eýýäm bilýär, ýöne LinkedListşonda-da gerekli ýere “gözlemeli”. IkinjidenArrayList , mesele “özi” gurluşynda . Içerki massiwi giňeltmek, ähli elementleri göçürmek we üýtgeýän elementler ýörite içerki funksiýa bilen amala aşyrylýar - System.arrayCopy(). Bu iş üçin ýörite optimallaşdyrylanlygy sebäpli gaty çalt işleýär. Desiredöne islenýän görkezijä “basmagyň” zerurlygy ýok ýagdaýlarda LinkedListhakykatdanam özüni has gowy görkezýär. Mysal üçin, goýmak sanawyň başynda ýüze çyksa. Geliň, ol ýerde million elementi goýmaga synanyşalyň: 
public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       //write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); //calculate the difference
       System.out.println("Result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}
Netije: 

Результат в миллисекундах: 43448
Результат в миллисекундах: 107
Doly başga netije! Sanawyň başyna million element girizmek üçin 43 sekuntdan gowrak wagt gerek boldy ArrayList, LinkedListol bolsa 0,1 sekuntda tamamlandy! Bu ýagdaýda LinkedListher gezek sanawyň ortasyna baglanyşyk zynjyryndan “ylgamak” hökman däldi. Sanawyň başynda derrew zerur görkezijini tapdy we operasiýa ýörelgeleriniň tapawudy eýýäm onuň tarapynda bolupdy :) Aslynda, " ArrayListgarşy LinkedList" diskussiýa gaty giň ýaýrady we häzirki wagtda bu meselä çuňňur girmeris; derejesi. Rememberatda saklamaly esasy zat:
  • Belli bir kolleksiýanyň “kagyz ýüzünde” artykmaçlyklary hakykatda işlemez (muňa sanawyň ortasyndan mysal alyp seretdik)
  • Collectionygyndy saýlanyňyzda aşa aşa gitmeli dälsiňiz (" ArrayListelmydama has çalt, ulanyň we ýalňyşmarsyňyz. LinkedListHiç kim muny köp wagt bäri ulanmaýar").
Hatda dörediji LinkedListJoşua Bloç hem şeýle diýýär :) Şeýle-de bolsa, bu nukdaýnazardan 100% dogry däl we biz muňa ynanýarys. Öňki mysalymyzda LinkedList400 (!) Has çalt işledi. LinkedListAnotherene bir zat, iň gowy saýlanjak ýagdaýlar hakykatdanam az . Theyöne olar bar we gerekli wagtda LinkedListsize çynlakaý kömek edip bilerler. Leksiýanyň başynda näme hakda gürleşendigimizi ýatdan çykarmaň: dürli maglumatlar gurluşlary dürli meseleler üçin has täsirli. Meseläniň ähli şertleri belli bolýança haýsy maglumat gurluşynyň has gowy boljakdygyny 100% ynam bilen aýtmak mümkin däl. Soň bu ýygyndylar hakda has köp maglumat alarsyňyz we saýlamak has aňsat bolar. Emma iň ýönekeý we iň täsirli wariant hemişe birmeňzeş: programmaňyzdaky hakyky maglumatlary synap görüň. Soňra iki sanawyň netijelerini öz gözüňiz bilen görüp bilersiňiz we hökman ýalňyşmarys :)
Teswirler
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION