สวัสดี! บทเรียนล่าสุดทั้งหมดอุทิศให้กับArrayList โครงสร้างข้อมูลนี้สะดวกและมีประโยชน์มาก สามารถจัดการงานได้มากมาย แต่ Java มีโครงสร้างข้อมูลอื่น ๆ มากมาย ทำไม เหนือสิ่งอื่นใด เนื่องจากขอบเขตของงานมีมากมายมหาศาล และโครงสร้างข้อมูลที่มีประสิทธิภาพสูงสุดก็แตกต่างกันไปตามงานต่างๆ วันนี้เราจะพบกับโครงสร้างใหม่: Java LinkedListซึ่งเป็นรายการที่เชื่อมโยงแบบทวีคูณ
มาดูกันว่ามีการจัดระเบียบอย่างไร ทำไมถึงเรียกว่า double-linked แตกต่างจากArrayListอย่างไร องค์ประกอบใน Java LinkedListเป็นลิงค์ในห่วงโซ่เดียว นอกจากข้อมูลแล้ว แต่ละองค์ประกอบยังเก็บการอ้างอิงถึงองค์ประกอบก่อนหน้าและถัดไป การอ้างอิงเหล่านี้ช่วยให้คุณย้ายจากองค์ประกอบหนึ่งไปยังอีกองค์ประกอบหนึ่งได้ นี่คือวิธีที่คุณสร้าง:
มาดูวิธีเพิ่มองค์ประกอบใหม่ สิ่งนี้ทำได้โดยใช้เมธอด add()
ด้วยเหตุนี้str2และstr1จึงเชื่อมโยงผ่าน ลิงก์ ถัดไปและก่อนหน้าที่จัดเก็บไว้ในโหนดของรายการ:
ตอนนี้คุณควรเข้าใจแนวคิดหลักของรายการที่เชื่อมโยงแบบทวีคูณ สายเชื่อมโยงนี้เป็นสิ่งที่ทำให้ องค์ประกอบ LinkedListเป็นรายการเดียว ซึ่งแตกต่างจากArrayList LinkedList ไม่มีอาร์เรย์หรือสิ่งที่เหมือนอาร์เรย์อยู่ภายใน การทำงานใด ๆ (และส่วนใหญ่) กับ ArrayList นั้นขึ้นอยู่กับการทำงานกับอาร์เรย์ภายใน ทำงานกับJava LinkedList ใด ๆเดือดลงเพื่อเปลี่ยนลิงค์ สิ่งนี้สามารถเห็นได้อย่างชัดเจนโดยเพิ่มองค์ประกอบที่ตรงกลางของรายการ:
หลังจากเปลี่ยนลิงก์ภายในแล้วstr2ได้ถูกเพิ่มเข้าไปในรายการเรียบร้อยแล้ว:
ขณะนี้องค์ประกอบทั้ง 3 เชื่อมต่อกันแล้ว คุณสามารถย้ายผ่าน ลิงค์ ถัดไปจากองค์ประกอบแรกในห่วงโซ่ไปยังองค์ประกอบสุดท้ายและย้อนกลับอีกครั้ง ดังนั้นเราจึงค่อนข้างพอใจกับการแทรก แต่แล้วการลบองค์ประกอบล่ะ หลักการเหมือนกันทุกประการ เราเพิ่งอัปเดตลิงก์ในสององค์ประกอบ "ทางซ้ายและขวา" ขององค์ประกอบที่ถูกลบ:
หลังจากอัปเดตลิงก์แล้ว เราได้รับผลลัพธ์ตามที่ต้องการ:
ไม่เหมือนกับการดำเนินการลบในArrayListที่นี่ไม่จำเป็นต้องเปลี่ยนองค์ประกอบอาร์เรย์หรือทำ อะไรก็ได้ เรา เพิ่งอัปเดตลิงก์สำหรับstr1และstr3 ตอนนี้พวกมันชี้เข้าหากัน และstr2ได้ " หลุด " ออกจากห่วงโซ่การเชื่อมโยง และไม่เป็นส่วนหนึ่งของรายการอีกต่อไป

public class Main {
public static void main(java.lang.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 Canada");
LinkedList<String> earlBio = new LinkedList<>();
earlBio.add(str1);
earlBio.add(str2);
earlBio.add(str3);
earlBio.add(str4);
System.out.println(earlBio);
}
}
ผลลัพธ์: [สวัสดีชาวโลก! ฉันชื่อเอิร์ล ฉันรักชวา ฉันอาศัยอยู่ที่แคนาดา] นี่คือลักษณะของรายการของเรา: 
earlBio.add(str2);
ที่จุดในรหัส รายการของเราประกอบด้วยหนึ่งองค์ประกอบ: สตริงstr1 มาดูกันว่าจะเกิดอะไรขึ้นต่อไปในภาพ: 

public class Main {
public static void main(java.lang.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 Canada");
LinkedList<String> earlBio = new LinkedList<>();
earlBio.add(str1);
earlBio.add(str3);
earlBio.add(1, str2);
System.out.println(earlBio);
}
}
อย่างที่คุณเห็น วิธี การเพิ่ม () ที่โอเวอร์โหลด ช่วยให้คุณระบุดัชนีเฉพาะสำหรับรายการใหม่ได้ ในกรณีนี้ เรา ต้องการเพิ่ม String str2ระหว่างstr1และstr3 นี่คือสิ่งที่จะเกิดขึ้นภายใน: 

public class Main {
public static void main(java.lang.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 Canada");
LinkedList<String> earlBio = new LinkedList<>();
earlBio.add(str1);
earlBio.add(str3);
earlBio.add(1, str2);
earlBio.remove(1);
System.out.println(earlBio);
}
}
ต่อไปนี้คือสิ่งที่เกิดขึ้นหากเราลบรายการที่มีดัชนี 1 (ซึ่งอยู่ตรงกลางของรายการ): 

ภาพรวมของวิธีการ
LinkedListมีวิธีการมากมายที่เหมือนกันกับArrayList ตัวอย่างเช่น ทั้งสองคลาสมีเมธอด เช่นadd() , remove() , indexOf() , clear() , contain() (ระบุว่ามีรายการอยู่ในรายการหรือไม่), set() (แทนที่องค์ประกอบที่มีอยู่) และขนาด() . แม้ว่าหลายคนจะทำงานแตกต่างกันภายใน (ตามที่เราพบใน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 + '\'' +
'}';
}
}
ผลลัพธ์: [รถยนต์{model='Ferrari 360 Spider'} รถยนต์{model='Bugatti Veyron'} รถยนต์{model='Lamborghini Diablo'}] [รถยนต์{model='Ford Mondeo'} รถยนต์{model=' Ferrari 360 Spider'}, รถยนต์{model='Bugatti Veyron'}, รถยนต์{model='Lamborghini Diablo'}, รถยนต์{model='Fiat Ducato'}] ปิดท้าย ด้วย "Ford" ที่ด้านบนสุดของรายการ และ "เฟียต" ในตอนท้าย
- 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());
}
ผลลัพธ์: รถยนต์{model='Ferrari 360 Spider'} รถยนต์{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 on the list?");
System.out.println(cars);
}
ผลลัพธ์: รถยนต์{model='Ferrari 360 Spider'} รถยนต์{model='Lamborghini Diablo'} มีอะไรเหลืออยู่ในรายการบ้าง [รถยนต์{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));
}
ผลลัพธ์: [รถยนต์{model=' Ferrari 360 Spider'}, รถยนต์{model='Bugatti Veyron'}, รถยนต์{model='Lamborghini Diablo'}] ตอนนี้ เรารู้แล้วว่าLinkedListทำงานอย่างไรและการจัดองค์กรแตกต่างจากArrayList อย่างไร ประโยชน์ของการใช้LinkedList คืออะไร ? เหนือสิ่งอื่นใด เราได้ประโยชน์เมื่อทำงานกลางรายการ การดำเนิน การแทรกและลบระหว่างLinkedListนั้นง่ายกว่าในArrayList มาก เราเพียงอัปเดตลิงก์ขององค์ประกอบที่อยู่ใกล้เคียง และองค์ประกอบที่ไม่ต้องการ "เลื่อนออก" ของห่วงโซ่ของลิงก์ แต่ในArrayListเราต้อง
- ตรวจสอบว่ามีพื้นที่เพียงพอหรือไม่ (เมื่อใส่)
- ถ้าไม่เช่นนั้นเราจะสร้างอาร์เรย์ใหม่และคัดลอกข้อมูลที่นั่น (เมื่อใส่)
- เราลบ/แทรกองค์ประกอบ และย้ายองค์ประกอบอื่นๆ ทั้งหมดไปทางขวา/ซ้าย (ขึ้นอยู่กับประเภทของการดำเนินการ) และความซับซ้อนของกระบวนการนี้ขึ้นอยู่กับขนาดของรายการเป็นอย่างมาก การคัดลอก/ย้ายองค์ประกอบ 10 รายการเป็นเรื่องหนึ่ง และอีกเรื่องหนึ่งที่จะทำเช่นเดียวกันกับองค์ประกอบนับล้าน
ในทางทฤษฎี
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 taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
}
}
ผลลัพธ์: เวลาที่ LinkedList ใช้ (หน่วยเป็นมิลลิวินาที) = 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 taken by 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 ตามห่วงโซ่ของการเชื่อมโยง สำหรับ LinkedList นี่ไม่ใช่ที่อยู่หน่วยความจำ แต่เป็นลิงก์ที่ต้องเข้าถึง: 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…… ด้วยเหตุนี้ ระหว่างการแทรก (removal) แต่ละครั้งตรงกลางรายการ , 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("The 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 ตอนนี้เราได้ผลลัพธ์ที่แตกต่างไปจากเดิมอย่างสิ้นเชิง! ArrayListใช้เวลามากกว่า 43 วินาทีในการแทรกรายการหนึ่งล้านรายการที่ด้านหน้าของรายการในขณะที่LinkedListสามารถทำได้ภายใน 0.1 วินาที! LinkedListได้รับประโยชน์จากที่นี่ เนื่องจากไม่ต้องผ่านห่วงโซ่ของลิงก์ไปยังตรงกลางของรายการทุกครั้ง ค้นหาดัชนีที่ต้องการทันทีที่จุดเริ่มต้นของรายการ ดังนั้นอัลกอริทึมที่แตกต่างกันจึงได้เปรียบอยู่แล้ว :) อันที่จริง การอภิปราย " ArrayListกับLinkedList " นั้นแพร่หลายมากและเราจะไม่ลงลึกถึงระดับปัจจุบัน สิ่งสำคัญที่คุณต้องจำไว้คือ:
- ข้อดีทางทฤษฎีบางคอลเลกชั่นใด ๆ นั้นไม่ได้ผลเสมอไปในความเป็นจริง (เราเห็นสิ่งนี้พร้อมกับตัวอย่างที่เกี่ยวข้องกับรายการตรงกลาง)
- อย่าใช้ตำแหน่งที่มากเกินไปเมื่อต้องเลือกคอลเลกชั่น (" ArrayListเร็วกว่าเสมอ ใช้มันแล้วคุณจะไม่ผิดพลาด ไม่มีใครใช้LinkedListมานานแล้ว")
อ่านเพิ่มเติม: |
---|
GO TO FULL VERSION