LinkedList ใน Java

สวัสดี! การบรรยายล่าสุดทั้งหมดมีไว้เพื่อศึกษารายการ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);

ในช่วงเวลาของโค้ดบรรทัดนี้ รายการของเราประกอบด้วยองค์ประกอบเดียว - 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);

   }
}

อย่างที่คุณเห็น วิธีการโอเวอร์โหลด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'}]

เป็นผลให้ Ford อยู่ในอันดับต้นๆ ของรายการ และ 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));

ในกรณีของ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% และเราเชื่อมั่นในสิ่งนี้ ในตัวอย่างก่อนหน้านี้LinkedListมันทำงานเร็วขึ้น 400 (!) เท่า อีกประการหนึ่งคือมีสถานการณ์น้อยมากที่LinkedListจะเป็นตัวเลือกที่ดีที่สุด แต่สิ่งเหล่านี้มีอยู่จริง และในเวลาที่เหมาะสมLinkedListก็สามารถช่วยเหลือคุณได้อย่างจริงจัง อย่าลืมสิ่งที่เราพูดถึงในตอนต้นของการบรรยาย: โครงสร้างข้อมูลที่แตกต่างกันจะมีประสิทธิภาพมากที่สุดสำหรับงานที่แตกต่างกัน เป็นไปไม่ได้ที่จะพูดด้วยความมั่นใจ 100% ว่าโครงสร้างข้อมูลใดจะดีกว่าจนกว่าจะทราบเงื่อนไขทั้งหมดของปัญหา หลังจากนั้นคุณจะทราบข้อมูลเพิ่มเติมเกี่ยวกับคอลเลกชันเหล่านี้ และจะง่ายต่อการตัดสินใจ แต่ตัวเลือกที่ง่ายและมีประสิทธิภาพมากที่สุดจะเหมือนเดิมเสมอ นั่นคือทดสอบทั้งข้อมูลจริงจากโปรแกรมของคุณ จากนั้นคุณจะเห็นผลลัพธ์ของทั้งสองรายการด้วยตาของคุณเองและคุณจะไม่ผิดพลาดอย่างแน่นอน :)