LinkedList در جاوا

سلام! تمام سخنرانی های اخیر به مطالعه لیست ArrayList اختصاص یافته است . این ساختار داده بسیار راحت است و به شما اجازه می دهد تا بسیاری از مشکلات را حل کنید. با این حال، جاوا دارای بسیاری از ساختارهای داده دیگر است. چرا؟ اول از همه، به این دلیل که دامنه وظایف موجود بسیار گسترده است و برای کارهای مختلف ساختارهای داده متفاوت بیشترین تأثیر را دارند . امروز با یک ساختار جدید آشنا می شویم - یک لیست پیوندی دوگانه 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);

در زمان این خط کد، لیست ما از یک عنصر تشکیل شده است - رشته str1. بیایید ببینیم در تصویر بعدی چه اتفاقی می‌افتد: در نتیجه str2، و str1از طریق پیوندهای ذخیره شده در آنها به هم متصل شوید nextو previous: اکنون باید ایده اصلی یک لیست دارای پیوند دوگانه را درک کنید. عناصر 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);

   }
}

همانطور که می بینید، روش overloaded add()به شما این امکان را می دهد که یک شاخص خاص برای عنصر جدید مشخص کنید. در این حالت می خواهیم یک خط str2بین str1و اضافه کنیم str3. این همان چیزی است که در داخل اتفاق می افتد: و در نتیجه تغییر پیوندهای داخلی، عنصر str2با موفقیت به لیست اضافه می شود: اکنون هر 3 عنصر پیوند داده شده اند. از اولین عنصر در امتداد زنجیره nextمی توانید به آخرین و عقب بروید. ما کم و بیش متوجه درج شده ایم، اما در مورد حذف عناصر چطور؟ اصل عملکرد یکسان است. ما به سادگی پیوندهای دو عنصر را "در طرفین" عنصر حذف شده دوباره تعریف می کنیم:

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'}]

در نتیجه، فورد در صدر لیست قرار گرفت و فیات در پایان.

• 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] این یک آدرس خاص در حافظه است، زیرا دارای یک آرایه در داخل است. در حالی که 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هیچ کس مدت زیادی است که از آن استفاده نکرده است").

اگرچه حتی خالق LinkedListJoshua Bloch هم چنین می گوید:) با این حال، این دیدگاه 100٪ درست نیست و ما در این مورد متقاعد شده ایم. در مثال قبلی ما LinkedList400 (!) بار سریعتر کار می کرد. نکته دیگر این است که واقعاً موقعیت های کمی وجود دارد که LinkedListبهترین انتخاب باشد. اما آنها وجود دارند و در زمان مناسب LinkedListمی توانند به طور جدی به شما کمک کنند. فراموش نکنید که در ابتدای سخنرانی در مورد آن صحبت کردیم: ساختارهای داده های مختلف برای کارهای مختلف مؤثرتر هستند. تا زمانی که همه شرایط مشکل مشخص نشود، نمی توان با اطمینان 100٪ گفت که کدام ساختار داده بهتر است. بعداً در مورد این مجموعه ها بیشتر خواهید دانست و انتخاب آسان تر خواهد بود. اما ساده ترین و مؤثرترین گزینه همیشه یکسان است: هر دو را بر روی داده های واقعی از برنامه خود آزمایش کنید. سپس می توانید با چشمان خود نتایج هر دو لیست را ببینید و قطعاً اشتباه نخواهید کرد :)