Java LinkedList

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

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);

   }
}

ผลลัพธ์: [สวัสดีชาวโลก! ฉันชื่อเอิร์ล ฉันรักชวา ฉันอาศัยอยู่ที่แคนาดา] นี่คือลักษณะของรายการของเรา: มาดูวิธีเพิ่มองค์ประกอบใหม่ สิ่งนี้ทำได้โดยใช้เมธอด add()

earlBio.add(str2);

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

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 นี่คือสิ่งที่จะเกิดขึ้นภายใน: หลังจากเปลี่ยนลิงก์ภายในแล้วstr2ได้ถูกเพิ่มเข้าไปในรายการเรียบร้อยแล้ว: ขณะนี้องค์ประกอบทั้ง 3 เชื่อมต่อกันแล้ว คุณสามารถย้ายผ่าน ลิงค์ ถัดไปจากองค์ประกอบแรกในห่วงโซ่ไปยังองค์ประกอบสุดท้ายและย้อนกลับอีกครั้ง ดังนั้นเราจึงค่อนข้างพอใจกับการแทรก แต่แล้วการลบองค์ประกอบล่ะ หลักการเหมือนกันทุกประการ เราเพิ่งอัปเดตลิงก์ในสององค์ประกอบ "ทางซ้ายและขวา" ขององค์ประกอบที่ถูกลบ:

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 (ซึ่งอยู่ตรงกลางของรายการ): หลังจากอัปเดตลิงก์แล้ว เราได้รับผลลัพธ์ตามที่ต้องการ: ไม่เหมือนกับการดำเนินการลบในArrayListที่นี่ไม่จำเป็นต้องเปลี่ยนองค์ประกอบอาร์เรย์หรือทำ อะไรก็ได้ เรา เพิ่งอัปเดตลิงก์สำหรับstr1และstr3 ตอนนี้พวกมันชี้เข้าหากัน และstr2ได้ " หลุด " ออกจากห่วงโซ่การเชื่อมโยง และไม่เป็นส่วนหนึ่งของรายการอีกต่อไป

ภาพรวมของวิธีการ

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 รายการเป็นเรื่องหนึ่ง และอีกเรื่องหนึ่งที่จะทำเช่นเดียวกันกับองค์ประกอบนับล้าน

กล่าวอีกนัยหนึ่ง ถ้าการดำเนินการแทรก/ลบตรงกลางรายการเป็นเรื่องปกติมากที่สุดในโปรแกรมของคุณ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 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มานานแล้ว")

แม้ว่า Joshua Bloch ผู้เขียนของ LinkedListจะบอกว่าเป็นกรณีนี้ :) ถึงกระนั้น มุมมองนี้ก็ยังห่างไกลจากความถูกต้อง 100% และเราเชื่อมั่นในสิ่งนี้ ในตัวอย่างก่อนหน้านี้LinkedListเร็วขึ้น 400 (!) เท่า อีกสิ่งหนึ่งคือมีบางสถานการณ์จริงๆ ที่LinkedListเป็นตัวเลือกที่ดีที่สุด แต่มันมีอยู่จริงและในเวลาที่เหมาะสมLinkedListสามารถตอบแทนคุณได้อย่างงาม อย่าลืมสิ่งที่เรากล่าวไว้ในตอนต้นของบทเรียน: โครงสร้างข้อมูลที่มีประสิทธิภาพสูงสุดนั้นแตกต่างกันไปตามงานต่างๆ เป็นไปไม่ได้ที่จะแน่ใจได้ 100% ว่าโครงสร้างข้อมูลใดจะดีที่สุดจนกว่าคุณจะทราบเงื่อนไขทั้งหมดของงานของคุณ คุณจะทราบข้อมูลเพิ่มเติมเกี่ยวกับคอลเล็กชันเหล่านี้ในภายหลัง ซึ่งจะทำให้เลือกได้ง่ายขึ้น แต่ตัวเลือกที่ง่ายและมีประสิทธิภาพมากที่สุดนั้นเหมือนกันเสมอ: ลองทั้งสองอย่างกับข้อมูลจริงที่ใช้ในโปรแกรมของคุณ จากนั้นคุณจะสามารถเห็นได้ด้วยตัวคุณเองว่ารายการทั้งสองประเภททำงานอย่างไร และคุณจะไม่ผิดพลาดอย่างแน่นอน :) เพื่อเสริมสิ่งที่คุณได้เรียนรู้ เราขอแนะนำให้คุณดูบทเรียนวิดีโอจากหลักสูตร Java ของเรา