Моддаи
Оғоз
Омӯзишро оғоз кунед
JavaRush /Блоги Java /Random-TG /LinkedList дар Java
Зепп Бранниган
Сатҳи

LinkedList дар Java

Дар гурӯҳ нашр шудааст
Салом! Ҳама лексияҳои охирин ба омӯзиши рӯйхати ArrayList бахшида шудаанд . Ин сохтори додаҳо хеле қулай аст ва ба шумо имкон медиҳад, ки бисёр мушкилотро ҳал кунед. Бо вуҷуди ин, Java бисёр сохторҳои дигари маълумот дорад. Чаро? Пеш аз ҳама, зеро доираи вазифаҳои мавҷуда хеле васеъ аст ва барои вазифаҳои гуногун сохторҳои гуногуни додаҳо самараноктаранд . Имрӯз мо бо сохтори нав шинос мешавем - рӯйхати дукарата пайвандшуда LinkedList . Биёед бифаҳмем, ки он чӣ гуна кор мекунад, чаро онро дучандон пайваст меноманд ва чӣ гуна он аз ArrayList фарқ мекунад . Дар LinkedList, унсурҳо воқеан пайвандҳои занҷир мебошанд. Ҳар як элемент, ба ғайр аз маълумоте, ки дар он нигоҳ дошта мешавад, ба унсури қаблӣ ва оянда пайванд дорад . Ин пайвандҳо ба шумо имкон медиҳанд, ки аз як элемент ба элементи дигар гузаред. Он чунин сохта шудааст: 
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);

   }
}
Хулоса: 

[Hello World! My name is Earl, I love Java, I live in Moscow]
Сохтори рӯйхати мо чунин хоҳад буд: Рӯйхати пайвандшуда - 2Биёед бубинем, ки элементи нав чӣ гуна илова карда мешавад. Ин бо истифода аз add(). 
earlBio.add(str2);
Дар замони ин сатри code, рӯйхати мо аз як элемент иборат аст - string str1. Биёед бубинем, ки минбаъд дар расм чӣ мешавад: Рӯйхати пайвандшуда - 3Дар натиҷа str2, ва str1тавассути истинодҳои дар онҳо нигоҳ дошташуда пайваст шавед nextва previous: Рӯйхати пайвандшуда - 4Акнун шумо бояд идеяи асосии рӯйхати дукарата алоқамандро дарк кунед. Элементҳо LinkedListяк рӯйхати ягона мебошанд, маҳз ба шарофати ин занҷири пайвандҳо. Дар дохor ягон массив LinkedList, ба монанди дар ArrayList, ё ягон чизи шабеҳ вуҷуд надорад. Ҳама корҳо бо ArrayList (ба андозаи калон) ба кор бо массиви дохилӣ рост меоянд. Ҳама корҳо бо LinkedListтағир додани пайвандҳо анҷом дода мешаванд. Ин тавассути илова кардани элемент ба мобайни рӯйхат хеле равшан дида мешавад: 
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);

   }
}
Тавре ки шумо мебинед, усули изофабор add()ба шумо имкон медиҳад, ки индекси мушаххасро барои элементи нав муайян кунед. str2Дар ин ҳолат, мо мехоҳем, ки дар байни str1ва як сатр илова кунем str3. Ин аст он чизе ки дар дохor он рӯй медиҳад: Рӯйхати пайвандшуда - 5Ва дар натиҷаи тағир додани истинодҳои дохилӣ, элемент str2бомуваффақият ба рӯйхат илова карда мешавад: Рӯйхати пайвандшуда - 6Ҳоло ҳама 3 элемент пайваст карда шудаанд. Аз унсури аввал дар баробари занҷир nextшумо метавонед ба охир ва бозгашт биравед. Мо бештар ё камтар воридкуниро фаҳмидем, аммо дар бораи нест кардани элементҳо чӣ гуфтан мумкин аст? Принсипи амалиёт ҳамон аст. Мо танҳо истинодҳои ду унсури "дар паҳлӯ" -и хориҷшавандаро аз нав муайян мекунем:
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-ро нест кунем, чунин мешавад (он дар мобайни рӯйхат): Рӯйхати пайвандшуда - 7Баъди аз нав муайян кардани пайвандҳо, мо натиҷаи дилхоҳ мегирем: Рӯйхати пайвандшуда - 8Баръакси несткунӣ, ArrayListивазшавии элементҳои массив ва монанди инҳо вуҷуд надорад. Мо танҳо истинодҳои str1ва унсурҳоро аз нав муайян мекунем str3. Ҳоло онҳо ба ҳамдигар ишора мекунанд ва an object str2аз ин занҷири пайвандҳо "баромадааст" ва дигар дар рӯйхат нест.

Баррасии усулҳо

Он бо усулҳои LinkedListбисёр монандӣ дорад . ArrayListМасалан, усулҳо ба монанди add(), remove(), indexOf(), clear(), contains()(элементест, ки дар рӯйхат мавҷуд аст), set()(ворид кардани элемент бо иваз) size()дар ҳарду синфҳо мавҷуданд. add()Гарчанде ки (чунон ки мо дар мисол ва ) фаҳмидем remove(), бисёре аз онҳо дар дохor худ ба таври гуногун кор мекунанд, аммо дар ниҳоят онҳо як корро мекунанд. Аммо, он LinkedListдорои усулҳои алоҳидаи кор бо ибтидо ва охири рӯйхат мебошад, ки дар : мавҷуд нестанд ArrayList:
  • addFirst(), addLast(): усулҳои илова кардани элемент ба аввал/охири рӯйхат
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 + '\'' +
               '}';
   }
}
Хулоса: 

[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'}]
Дар натиҷа, Форд дар болои рӯйхат ва Fiat дар охири рӯйхат қарор гирифтанд.
  • peekFirst(), peekLast(): унсури якум/охирини рӯйхатро бармегардонад. nullАгар рӯйхат холӣ бошад, баргардед .
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());
}
Хулоса: 

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
  • pollFirst(), pollLast(): унсури якум/охирини рӯйхатро баргардонед ва онро аз рӯйхат хориҷ кунед . nullАгар рӯйхат холӣ бошад, баргардед
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);
}
Хулоса: 

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
What осталось в списке?
[Car{model='Bugatti Veyron'}]
  • toArray(): массиви элементҳои рӯйхатро бармегардонад
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));
}
Хулоса: 

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
Акнун мо медонем, ки он чӣ гуна кор мекунад LinkedListва чӣ гуна он аз ArrayList. Манфиатҳои истифодаи он чӣ гунаанд LinkedList? Пеш аз ҳама, дар кор бо миёнаи рӯйхат . Ворид кардан ва нест кардан дар мобайн LinkedListнисбат ба ArrayList. Мо танҳо пайвандҳои унсурҳои ҳамсояро аз нав муайян мекунем ва унсури нолозим аз занҷири пайвандҳо "афтад". Ҳангоми дар ArrayListмо:
  • санҷед, ки фазои кофӣ вуҷуд дорад (ҳангоми ворид кардан)
  • агар ин кифоя набошад, массиви нав эҷод кунед ва маълумотро дар он ҷо нусхабардорӣ кунед (ҳангоми часпондан)
  • нест кардан/ворид кардани элемент, ва кӯчонидани ҳамаи унсурҳои дигар ба рост/чап (вобаста ба намуди амалиёт). Илова бар ин, мураккабии ин раванд аз андозаи рӯйхат вобаста аст. Нусхабардорӣ/кӯчонидани 10 элемент як чиз аст, аммо бо як миллион элемент ин корро кардан тамоман дигар аст.
Яъне, агар дар барномаи шумо амалиёти воридкунӣ/ҳазф бештар бо миёнаи рӯйхат рух диҳад, LinkedListон бояд аз ArrayList.

Дар назария

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));
   }
}
Хулоса: 

Время работы для 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));
   }
}
Хулоса: 

Время работы для ArrayList (в миллисекундах) = 181
Ногаҳон! Чунин ба назар мерасад, ки мо амалиётеро иҷро мекардем, ки LinkedListбояд хеле самараноктар бошад - ворид кардани 100 элемент ба мобайни рӯйхат. Ва рӯйхати мо бузург аст - 5,000,000 элемент: ArrayListмо маҷбур шудем, ки ҳар дафъае, ки онҳоро ворид кунем, якчанд миллион элементро иваз кунем! Сабаби галабаи у дар чист? Аввалан, ба элемент дар ArrayListмуддати муайян дастрас мешавад. Вақте ки шумо нишон медиҳед: 
list.add(2_000_000, new Integer(Integer.MAX_VALUE));
пас дар мавриди ArrayList[2_000_000] ин суроғаи мушаххас дар хотира аст, зеро он дар дохor он массив дорад. Дар ҳоле ки LinkedListмассив ин тавр намекунад. Он элементи рақами 2_000_000-ро дар баробари занҷири пайвандҳо ҷустуҷӯ мекунад. Барои ӯ, ин суроғаи хотиравӣ нест, балки истинодест, ки ҳоло ҳам бояд ба он расид: 

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………
Дар натиҷа, бо ҳар як воридкунӣ (нест кардан) дар мобайни рӯйхат, ArrayListон аллакай суроғаи дақиқро дар хотира медонад, ки бояд ба он дастрасӣ пайдо кунад, аммо LinkedListба ҳар ҳол лозим аст, ки ба ҷои лозима "пайдо" кунад. Сониян , масъала дар сохтори ArrayListхуди як аст. Васеъ кардани массиви дохилӣ, нусхабардории ҳама элементҳо ва иваз кардани элементҳо бо функсияи махсуси дохилӣ - System.arrayCopy(). Он хеле зуд кор мекунад, зеро он махсус барои ин кор оптимизатсия шудааст. Аммо дар ҳолатҳое, ки лозим нест, ки ба индекси дилхоҳ "даста" кунед, LinkedListон дар ҳақиқат худро беҳтар нишон медиҳад. Масалан, агар воридкунӣ дар аввали рӯйхат рух диҳад. Биёед кӯшиш кунем, ки ба он як миллион элемент ворид кунем: 
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());
       }
   }

}
Хулоса: 

Результат в миллисекундах: 43448
Результат в миллисекундах: 107
Натиҷаи тамоман дигар! Барои ворид кардани як миллион элемент ба аввали рӯйхат зиёда аз 43 сония вақт лозим буд ArrayList, дар ҳоле ки LinkedListон дар 0,1 сония анҷом ёфт! Махз аз он иборат буд, ки дар ин вазъият LinkedListба мо лозим набуд, ки хар дафъа аз занчири пайвандакхо ба мобайни руйхат «давем». Вай дар оғози рӯйхат дарҳол нишондиҳандаи лозимиро пайдо кард ва дар он ҷо фарқият дар принсипҳои кор аллакай дар паҳлӯи ӯ буд :) Дар ҳақиқат, баҳси " ArrayListбар зидди LinkedList" хеле васеъ паҳн шудааст ва мо дар айни замон ба он амиқ намеравем. сатҳи. Чизи асосие, ки шумо бояд дар хотир доред:
  • На ҳама бартариҳои коллексияи мушаххаси "дар рӯи коғаз" дар асл кор хоҳанд кард (мо инро бо мисоли мобайни рӯйхат дида баромадем)
  • Ҳангоми интихоби коллексия набояд ба ифротӣ равед (“ ArrayListон ҳамеша тезтар аст, истифода баред ва хато намекунед. LinkedListҲеҷ кас онро муддати тӯлонӣ истифода накардааст”).
Ҳарчанд ҳатто созанда LinkedListҶошуа Блох чунин мегӯяд :) Аммо, ин нуқтаи назар аз 100% дуруст аст ва мо ба ин боварӣ дорем. Дар мисоли пешинаи мо LinkedListон 400 (!) маротиба тезтар кор мекард. Чизи дигар ин аст, ки дар ҳақиқат кам ҳолатҳое ҳастанд, ки LinkedListон интихоби беҳтарин аст. Аммо онҳо вуҷуд доранд ва дар вақти лозима LinkedListонҳо метавонанд ба шумо ба таври ҷиддӣ кӯмак расонанд. Фаромӯш накунед, ки мо дар оғози лексия дар бораи он чӣ сӯҳбат кардем: сохторҳои гуногуни додаҳо барои вазифаҳои гуногун самараноктаранд. Бо боварии 100% гуфтан ғайриимкон аст, ки кадом сохтори додаҳо беҳтар хоҳад буд, то даме ки тамоми шароити мушкилот маълум шавад. Баъдтар шумо дар бораи ин коллексияҳо маълумоти бештар хоҳед гирифт ва интихоб кардан осонтар мешавад. Аммо соддатарин ва самараноктарин вариант ҳамеша як аст: ҳардуро дар бораи маълумоти воқеии барномаи шумо санҷед. Пас шумо метавонед бо чашмони худ натиҷаҳои ҳарду рӯйхатро бубинед ва шумо бешубҳа хато намекунед :)
Шарҳҳо
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION