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]

Біздің тізімнің құрылымы келесідей болады: Жаңа элемент қалай қосылатынын көрейік. Бұл арқылы жасалады add().

earlBio.add(str2);

Осы code жолының уақытында біздің тізім бір элементтен тұрады - string str1. Келесі суретте не болатынын көрейік: Нәтижесінде str2, және str1оларда сақталған сілтемелер арқылы қосылыңыз nextжәне previous: Енді сіз қос байланыстырылған тізімнің негізгі идеясын түсінуіңіз керек. Элементтер LinkedListдәл осы сілтемелер тізбегінің арқасында бір тізім болып табылады. ішінде 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арасында жолды қосқымыз келеді . Ішінде осылай болады: Ішкі сілтемелерді өзгерту нәтижесінде элемент тізімге сәтті қосылды: Енді барлық 3 элемент байланыстырылды. Тізбек бойындағы бірінші элементтен соңғы және артқа өтуге болады. Біз кірістіруді азды-көпті түсіндік, бірақ элементтерді жою туралы не деуге болады? Жұмыс принципі бірдей. Біз жай ғана жойылатын элементтің «жағындағы» екі элементтің сілтемелерін қайта анықтаймыз: str1str3str2next

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 индексі бар элементті жойсақ, осылай болады (ол тізімнің ортасында): Сілтемелерді қайта анықтағаннан кейін біз қажетті нәтиже аламыз: Жоюдан айырмашылығы, ArrayListмассив элементтерінің жылжулары және т.б. str1Біз жай ғана және элементтерінің сілтемелерін қайта анықтаймыз str3. Енді олар бір-біріне нұсқайды және нысан 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'}]

Нәтижесінде Форд тізімнің басында, ал 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бұл жадтағы нақты address, себебі оның ішінде массив бар. Ал 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% сенімділікпен айту мүмкін емес. Кейінірек сіз бұл жинақтар туралы көбірек білесіз және таңдау жасау оңайырақ болады. Бірақ ең қарапайым және ең тиімді нұсқа әрқашан бірдей: екеуін де бағдарламаңыздағы нақты деректерде тексеріңіз. Сонда сіз екі тізімнің нәтижелерін өз көзіңізбен көре аласыз және сіз қателеспейсіз :)