การวิเคราะห์ความแตกต่างระหว่าง ArrayList และ LinkList ใน java

1.ArrayList ใช้โครงสร้างข้อมูลตามอาร์เรย์แบบไดนามิก และ LinkedList ใช้โครงสร้างข้อมูลตามรายการที่เชื่อมโยง
2. สำหรับการเข้าถึงและตั้งค่าแบบสุ่ม ArrayList ดีกว่า LinkedList เนื่องจาก ArrayList สามารถวางตำแหน่งแบบสุ่มได้ ในขณะที่ LinkedList จำเป็นต้องย้ายตัวชี้ไปยังโหนดทีละขั้นตอน (คิดโดยอ้างอิงถึงอาร์เรย์และรายการที่เชื่อมโยง)
3. สำหรับการดำเนินการใหม่และการลบการเพิ่มและการลบ LinedList จะมีประโยชน์มากกว่า เพียงแก้ไขตัวชี้เท่านั้น ในขณะที่ ArrayList จำเป็นต้องย้ายข้อมูลเพื่อเติมพื้นที่ของวัตถุที่ถูกลบ

ArrayList และ LinkedList เป็นคลาสคอลเลกชันสองคลาสที่ใช้จัดเก็บชุดการอ้างอิงอ็อบเจ็กต์ ตัวอย่างเช่น เราสามารถใช้ ArrayList เพื่อจัดเก็บชุดของ String หรือ Integer ดังนั้นประสิทธิภาพระหว่าง ArrayList และ LinkedList แตกต่างกันอย่างไร? เมื่อใดที่คุณควรใช้ ArrayList และเมื่อใดที่คุณควรใช้ LinkedList

หนึ่ง. ความซับซ้อนของเวลา

ประเด็นสำคัญประการแรกคือการใช้งานภายใน ArrayList ขึ้นอยู่กับอาร์เรย์วัตถุพื้นฐาน ดังนั้น เมื่อใช้วิธีการ get เพื่อเข้าถึงองค์ประกอบใดๆ ในรายการ (การเข้าถึงแบบสุ่ม) จะเร็วกว่า LinkedList วิธีการรับใน LinkedList จะตรวจสอบจากปลายด้านหนึ่งของรายการไปยังอีกด้านหนึ่งตามลำดับ สำหรับ LinkedList ไม่มีวิธีที่เร็วกว่าในการเข้าถึงองค์ประกอบเฉพาะในรายการ

สมมติว่าเรามีรายการจำนวนมากและองค์ประกอบในนั้นได้รับการจัดเรียงแล้ว รายการนี้อาจเป็นประเภท ArrayList หรือประเภท LinkedList ตอนนี้เราทำการค้นหาแบบไบนารี่ในรายการนี้ ดูโปรแกรมต่อไปนี้:

เวลาที่ใช้ไปของ LinkedList: 2596

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

นี่หมายความว่า ArrayList ทำงานได้ดีกว่า LinkedList เสมอหรือไม่ สิ่งนี้ไม่จำเป็นต้องเป็นความจริงเสมอไป ในบางกรณี LinkedList ทำงานได้ดีกว่า ArrayList และอัลกอริธึมบางตัวจะมีประสิทธิภาพมากกว่าเมื่อนำมาใช้ใน LinkedList ตัวอย่างเช่น ประสิทธิภาพจะดีกว่าเมื่อใช้เมธอด Collections.reverse เพื่อย้อนกลับรายการ

ดูตัวอย่างดังกล่าว หากเรามีรายการและต้องการดำเนินการแทรกและการลบจำนวนมาก ในกรณีนี้ LinkedList ก็เป็นตัวเลือกที่ดีกว่า ลองพิจารณาตัวอย่างสุดโต่งต่อไปนี้ โดยที่เราแทรกองค์ประกอบซ้ำๆ ที่จุดเริ่มต้นของรายการ:

ในขณะนี้ ผลลัพธ์ของฉันคือ: ArrayList ใช้เวลา: 2463

LinkedList ใช้เวลา: 15

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

สอง. ความซับซ้อนของพื้นที่

มีคลาสภายในส่วนตัวใน LinkedList ซึ่งกำหนดไว้ดังนี้:

รายการคลาสคงที่ส่วนตัว {
องค์ประกอบวัตถุ
รายการต่อไป;
รายการก่อนหน้า;
-

แต่ละออบเจ็กต์ Entry อ้างอิงองค์ประกอบในรายการ เช่นเดียวกับองค์ประกอบก่อนหน้าและองค์ประกอบถัดไปใน LinkedList ออบเจ็กต์ LinkedList ที่มีองค์ประกอบ 1,000 รายการจะมีออบเจ็กต์รายการ 1,000 รายการเชื่อมโยงเข้าด้วยกัน แต่ละออบเจ็กต์ที่สอดคล้องกับองค์ประกอบในรายการ ในกรณีนี้ จะมีค่าใช้จ่ายด้านพื้นที่จำนวนมากในโครงสร้าง LinkedList เนื่องจากจำเป็นต้องจัดเก็บข้อมูลที่เกี่ยวข้องของออบเจ็กต์เอนทิตี 1,000 เหล่านี้

ArrayList ใช้อาร์เรย์ในตัวเพื่อจัดเก็บองค์ประกอบ ความจุเริ่มต้นของอาร์เรย์นี้คือ 10 เมื่ออาร์เรย์จำเป็นต้องขยาย ความจุใหม่จะได้รับตามสูตรต่อไปนี้: ความจุใหม่ = (ความจุเก่า*3)/2+ 1 กล่าวคือ ความจุจะเพิ่มขึ้นประมาณ 50% ในแต่ละครั้ง ซึ่งหมายความว่าหากคุณมีออบเจ็กต์ ArrayList ที่มีองค์ประกอบจำนวนมาก คุณจะสูญเสียพื้นที่จำนวนมากโดยเปล่าประโยชน์มีสาเหตุมาจากวิธีการทำงานของ ArrayList หากมีพื้นที่ไม่เพียงพอที่จะจัดเก็บองค์ประกอบใหม่ จะต้องจัดสรรอาร์เรย์ใหม่เพื่อให้สามารถเพิ่มองค์ประกอบใหม่ได้ การจัดสรรอาร์เรย์ใหม่จะทำให้ประสิทธิภาพลดลงอย่างมาก หากเรารู้ว่า ArrayList จะมีองค์ประกอบจำนวนเท่าใด เราก็สามารถระบุความจุผ่าน Constructor ได้ นอกจากนี้เรายังสามารถใช้เมธอด trimToSize เพื่อลบพื้นที่ที่สูญเปล่าหลังจากจัดสรร ArrayList แล้ว

สาม. สรุป

ArrayList และ LinkedList ต่างก็มีข้อดีและข้อเสียในแง่ของประสิทธิภาพ และแต่ละอันก็มีแอปพลิเคชันของตัวเอง โดยทั่วไปสามารถอธิบายได้ดังนี้:

สรุปผลการดำเนินงาน:

1. สำหรับทั้ง ArrayList และ LinkedList ค่าใช้จ่ายในการเพิ่มองค์ประกอบที่ส่วนท้ายของรายการได้รับการแก้ไขแล้ว สำหรับ ArrayList ส่วนใหญ่จะเพิ่มรายการลงในอาร์เรย์ภายใน โดยชี้ไปที่องค์ประกอบที่เพิ่ม ซึ่งบางครั้งอาจทำให้อาร์เรย์ถูกจัดสรรใหม่ สำหรับ LinkedList โอเวอร์เฮดนี้จะเหมือนกัน โดยจัดสรรออบเจ็กต์รายการภายใน

2. การแทรกหรือการลบองค์ประกอบที่อยู่ตรงกลางของ ArrayList หมายความว่าองค์ประกอบที่เหลือในรายการจะถูกย้าย ในขณะที่การแทรกหรือการลบองค์ประกอบที่อยู่ตรงกลางของ LinkedList จะมีต้นทุนคงที่

3. LinkedList ไม่รองรับการเข้าถึงองค์ประกอบแบบสุ่มที่มีประสิทธิภาพ

4. การเสียพื้นที่ของ ArrayList ส่วนใหญ่จะสะท้อนให้เห็นในการสำรองพื้นที่จำนวนหนึ่งที่ส่วนท้ายของรายการ ในขณะที่การใช้พื้นที่ของ LinkedList สะท้อนให้เห็นได้ว่าแต่ละองค์ประกอบจำเป็นต้องใช้พื้นที่จำนวนมาก

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

ความแตกต่างระหว่าง ArrayList และ List ใน java

คอลเลกชันรายการ
รายการที่สืบทอดมาจากอินเทอร์เฟซของคอลเลกชัน รายการเป็นคอลเลกชันที่เรียงลำดับ องค์ประกอบในรายการสามารถรับ/ลบ/แทรกตามดัชนี (หมายเลขลำดับ: ข้อมูลตำแหน่งขององค์ประกอบในคอลเลกชัน)

ไม่เหมือนกับคอลเลกชัน Set ตรงที่ List อนุญาตให้มีองค์ประกอบที่ซ้ำกัน สำหรับองค์ประกอบออบเจ็กต์ e1 และ e2 ที่ตรงตามเงื่อนไขของ e1.equals(e2) จะสามารถมีอยู่ในคอลเลกชันรายการได้ในเวลาเดียวกัน แน่นอนว่ายังมีคลาสการใช้งาน List ที่ไม่อนุญาตให้มีองค์ประกอบที่ซ้ำกัน
ในเวลาเดียวกัน List ยังมีเมธอด listIterator() ซึ่งส่งคืนอ็อบเจ็กต์อินเทอร์เฟซ ListIterator เมื่อเปรียบเทียบกับอินเทอร์เฟซ Iterator แล้ว ListIterator จะเพิ่มวิธีการสำหรับการเพิ่ม การลบ และการตั้งค่าองค์ประกอบ และยังสามารถเคลื่อนที่ไปข้างหน้าหรือข้างหลังได้อีกด้วย

ความสัมพันธ์ระหว่างรายการและคอลเลกชัน:
java.util.คอลเลกชัน[I]
+--java.util.List[I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vector [C]
+--java.util.Stack [C]

คลาสการใช้งานของอินเทอร์เฟซรายการส่วนใหญ่ประกอบด้วย ArrayList, LinkedList, Vector, Stack ฯลฯ

ความสัมพันธ์แบบพ่อ-ลูก.
List คืออินเทอร์เฟซ และ ArrayList สืบทอดอินเทอร์เฟซนี้และนำไปใช้
เวลาใช้งานฉันมักจะใช้ ArrayList ฉันไม่เคยใช้ List คุณสามารถใช้มันได้ดังนี้: List list = new ArrayList();

อินเตอร์เฟซการรวบรวม
คอลเลกชันเป็นอินเทอร์เฟซคอลเลกชันพื้นฐานที่สุด คอลเลกชันแสดงถึงชุดของออบเจ็กต์ นั่นคือ องค์ประกอบของคอลเลกชัน คอลเลกชันบางรายการอนุญาตให้มีองค์ประกอบที่เหมือนกันและบางคอลเลกชันไม่อนุญาต บางประเภทและบางประเภทไม่ทำ Java SDK ไม่ได้จัดเตรียมคลาสที่สืบทอดมาจากคอลเลคชันโดยตรง คลาสที่ Java SDK มอบให้นั้นเป็น "อินเทอร์เฟซย่อย" ทั้งหมดที่สืบทอดมาจากคอลเลคชัน เช่น รายการและเซ็ต
คลาสทั้งหมดที่ใช้อินเทอร์เฟซคอลเลกชันจะต้องมีตัวสร้างมาตรฐานสองตัว: ตัวสร้างแบบไม่มีพารามิเตอร์สำหรับการสร้างคอลเลกชันที่ว่างเปล่า และตัวสร้างพารามิเตอร์ของคอลเลกชันสำหรับการสร้างคอลเลกชันใหม่ คอลเลกชันอินพุตมีองค์ประกอบเดียวกัน ตัวสร้างหลังอนุญาตให้ผู้ใช้คัดลอกคอลเลกชัน

จะวนซ้ำแต่ละองค์ประกอบในคอลเลกชันได้อย่างไร ไม่ว่าคอลเลกชันที่แท้จริงจะเป็นประเภทใด แต่ก็รองรับเมธอด iterator() ซึ่งส่งคืนตัววนซ้ำที่สามารถใช้เพื่อเข้าถึงแต่ละองค์ประกอบในคอลเลกชันทีละรายการ การใช้งานทั่วไปมีดังนี้:
Iterator it = collection.iterator(); // รับตัววนซ้ำ
ในขณะที่(it.hasNext()) {
Object obj = it.next(); // รับองค์ประกอบถัดไป
-
อินเทอร์เฟซทั้งสองที่ได้รับจากอินเทอร์เฟซคอลเลกชันคือรายการและตั้งค่า

อินเตอร์เฟซรายการ:
รายการเป็นคอลเลกชันที่เรียงลำดับ เมื่อใช้อินเทอร์เฟซนี้ คุณจะสามารถควบคุมตำแหน่งการแทรกของแต่ละองค์ประกอบได้อย่างแม่นยำ ผู้ใช้สามารถเข้าถึงองค์ประกอบในรายการโดยใช้ดัชนี (ตำแหน่งขององค์ประกอบในรายการ คล้ายกับตัวห้อยอาร์เรย์) ซึ่งคล้ายกับอาร์เรย์ Java
ไม่เหมือนกับชุดที่กล่าวถึงด้านล่าง List อนุญาตให้ใช้องค์ประกอบเดียวกัน
นอกเหนือจากเมธอด iterator() ที่จำเป็นสำหรับอินเทอร์เฟซ Collection แล้ว List ยังมีเมธอด listIterator() ซึ่งส่งคืนอินเทอร์เฟซ ListIterator เมื่อเปรียบเทียบกับอินเทอร์เฟซ Iterator มาตรฐาน ListIterator ยังมีวิธี add() เพิ่มเติมและวิธีอื่น ๆ ที่อนุญาตให้เพิ่ม ลบ ตั้งค่าองค์ประกอบ และเคลื่อนที่ไปข้างหน้าหรือข้างหลัง
คลาสทั่วไปที่ใช้อินเทอร์เฟซรายการคือ LinkedList, ArrayList, Vector และ Stack

คลาส LinkedList
LinkedList ใช้อินเทอร์เฟซรายการและอนุญาตให้มีองค์ประกอบที่เป็นโมฆะ นอกจากนี้ LinkedList ยังมีวิธีการรับ ลบ และแทรกเพิ่มเติมที่ส่วนหัวหรือส่วนท้ายของ LinkedList การดำเนินการเหล่านี้อนุญาตให้ใช้ LinkedList เป็นสแต็ก คิว หรือ deque
โปรดทราบว่า LinkedList ไม่มีวิธีการซิงโครไนซ์ หากหลายเธรดเข้าถึงรายการพร้อมกัน พวกเขาจะต้องดำเนินการซิงโครไนซ์การเข้าถึงด้วยตนเอง วิธีแก้ปัญหาหนึ่งคือการสร้างรายการที่ซิงโครไนซ์เมื่อสร้างรายการ:
รายการรายการ = Collections.synchronizedList(new LinkedList(...));

คลาส ArrayList
ArrayList ใช้อาร์เรย์ขนาดตัวแปร อนุญาตให้ใช้องค์ประกอบทั้งหมด รวมถึงค่าว่างด้วย ArrayList ไม่ได้รับการซิงโครไนซ์
เวลาทำงานของขนาด isEmpty, get และ set วิธีการจะคงที่ อย่างไรก็ตาม ต้นทุนของวิธีเพิ่มเป็นค่าคงที่ที่ตัดจำหน่าย และการเพิ่มองค์ประกอบ n รายการต้องใช้เวลา O(n) วิธีอื่นมีเวลาในการทำงานเป็นเส้นตรง
แต่ละอินสแตนซ์ ArrayList มีความจุ (Capacity) ซึ่งเป็นขนาดของอาร์เรย์ที่ใช้จัดเก็บองค์ประกอบ ความจุนี้จะเพิ่มขึ้นโดยอัตโนมัติเมื่อมีการเพิ่มองค์ประกอบใหม่ แต่ไม่ได้กำหนดอัลกอริทึมการเติบโต เมื่อจำเป็นต้องแทรกองค์ประกอบจำนวนมาก สามารถเรียกใช้เมธอด SureCapacity เพื่อเพิ่มความจุของ ArrayList ก่อนที่จะแทรกเพื่อปรับปรุงประสิทธิภาพการแทรก
เช่นเดียวกับ LinkedList ArrayList ก็ไม่ได้รับการซิงโครไนซ์เช่นกัน

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