Макала
Баштоо
Үйрөнүүнү баштаңыз
JavaRush /Java блогу /Random-KY /Java тилиндеги LinkedList
Зепп Бранниган
Деңгээл

Java тилиндеги LinkedList

Группада жарыяланган
Салам! Бардык акыркы лекциялар 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]
Биздин тизменин түзүлүшү ушундай болот: LinkedList - 2Келгиле, жаңы элемент кантип кошуларын карап көрөлү. Бул колдонуу менен жүзөгө ашырылат add(). 
earlBio.add(str2);
Коддун ушул сабында биздин тизме бир элементтен турат - string str1. Сүрөттө андан ары эмне болорун карап көрөлү: LinkedList - 3Натыйжада str2, жана str1аларда сакталган шилтемелер аркылуу туташуу nextжана previous: LinkedList - 4Эми сиз эки эселенген тизменин негизги идеясын түшүнүшүңүз керек. LinkedListБул шилтемелер чынжырынын аркасында элементтер бир тизмеден турат. Ичинде эч кандай массив жок LinkedList, in 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ортосунда сызык кошууну каалайбыз . Ичинде эмне болот: Жана ички шилтемелерди өзгөртүүнүн натыйжасында элемент тизмеге ийгorктүү кошулду: Эми бардык 3 элемент байланышты. Биринчи элементтен чынжыр боюнча сиз акыркы жана артка кете аласыз. Кыстарууну аздыр-көптүр түшүндүк, бирок элементтерди жок кылуу жөнүндө эмне айтууга болот? Иштөө принциби бирдей. Биз жөн гана алып салынган элементтин "капталындагы" эки элементтин шилтемелерин кайра аныктайбыз: 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 индекси бар элементти жок кылсак, ушундай болот (ал тизменин ортосунда): LinkedList - 7Шилтемелерди кайра аныктагандан кийин биз каалаган натыйжаны алабыз: LinkedList - 8Жок кылуудан айырмаланып, ArrayListмассив элементтеринин жылышуусу жана ушул сыяктуулар болбойт. str1Биз жөн гана жана элементтердин шилтемелерин кайра аныктайбыз str3. Эми алар бири-бирин көрсөтүп, an object str2бул шилтемелердин чынжырынан "чыгып кетти" жана мындан ары тизменин бир бөлүгү эмес.

Методдорго сереп салуу

Бул ыкмалар LinkedListменен көп окшоштуктары бар . ArrayListМисалы, add(), remove(), indexOf(), clear(), contains()(тизмеде камтылган элемент), set()(алмаштырылган элементти киргизүү) сыяктуу ыкмалар size()эки класста тең бар. Бирок (биз мисалдан билгенибиздей add()жана remove()) алардын көбү ички жагынан башкача иштешет, бирок акыры алар бир эле нерсени жасашат. Бирок, анын 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'}]
Жыйынтыгында тизменин башында Ford, ал эми 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));
анда [2_000_000] учурда ArrayListбул эстутумдагы белгилүү бир дарек, анткени анын ичинде массив бар. Ал эми 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