سلام! تمام سخنرانی های اخیر به مطالعه لیست 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
هیچ کس مدت زیادی است که از آن استفاده نکرده است").
LinkedList
Joshua Bloch هم چنین می گوید:) با این حال، این دیدگاه 100٪ درست نیست و ما در این مورد متقاعد شده ایم. در مثال قبلی ما LinkedList
400 (!) بار سریعتر کار می کرد. نکته دیگر این است که واقعاً موقعیت های کمی وجود دارد که LinkedList
بهترین انتخاب باشد. اما آنها وجود دارند و در زمان مناسب LinkedList
می توانند به طور جدی به شما کمک کنند. فراموش نکنید که در ابتدای سخنرانی در مورد آن صحبت کردیم: ساختارهای داده های مختلف برای کارهای مختلف مؤثرتر هستند. تا زمانی که همه شرایط مشکل مشخص نشود، نمی توان با اطمینان 100٪ گفت که کدام ساختار داده بهتر است. بعداً در مورد این مجموعه ها بیشتر خواهید دانست و انتخاب آسان تر خواهد بود. اما ساده ترین و مؤثرترین گزینه همیشه یکسان است: هر دو را بر روی داده های واقعی از برنامه خود آزمایش کنید. سپس می توانید با چشمان خود نتایج هر دو لیست را ببینید و قطعاً اشتباه نخواهید کرد :)
GO TO FULL VERSION