0Pricing
Java Academy · บทเรียน

ข้อแลกเปลี่ยนระหว่าง LinkedList กับ ArrayList

เปรียบเทียบประสิทธิภาพการแทรก การลบ และการเข้าถึงแบบสุ่ม เพื่อเลือกชนิดรายการที่เหมาะสม

ข้อแลกเปลี่ยนระหว่าง LinkedList กับ ArrayList เป็นบทเรียน Java Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Java Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Java Academy มีบทเรียนทั้งหมด 4 บทเรียน

คำถามหลัก

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

โครงสร้างภายในของ ArrayList

ArrayList เก็บองค์ประกอบไว้ในอาร์เรย์ที่ต่อเนื่องกัน เมื่ออาร์เรย์เต็ม ระบบจะแทนที่ด้วยอาร์เรย์ใหม่ที่มีขนาดใหญ่ขึ้น 1.5 เท่า และคัดลอกองค์ประกอบทั้งหมด

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

ทบทวนโครงสร้างภายในของ LinkedList

แต่ละองค์ประกอบอยู่ในอ็อบเจ็กต์ Node ของตนเอง ซึ่งมีตัวชี้ไปยังโหนดก่อนหน้าและถัดไป ไม่มีหน่วยความจำที่ต่อเนื่องกัน โหนดจึงอยู่ที่ใดก็ได้บนฮีป

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

การเข้าถึงแบบสุ่ม: ArrayList เหนือกว่า

ArrayList.get(i) ใช้เวลา O(1) เพราะเข้าถึงดัชนีของอาร์เรย์โดยตรง ส่วน LinkedList.get(i) ใช้เวลา O(n) เพราะต้องท่องผ่านโหนดมากถึง n/2 โหนด

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

การเพิ่มที่หัว: LinkedList เหนือกว่า

การเพิ่มที่ดัชนี 0 ใน ArrayList ต้องเลื่อนองค์ประกอบทั้งหมด ใช้เวลา O(n) ส่วน LinkedList เพียงอัปเดตตัวชี้สองตัว ใช้เวลา O(1)

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

การเพิ่มที่ท้าย: ใกล้เคียงกัน

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

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

การใช้หน่วยความจำ

ArrayList: ประมาณ 8 ไบต์ต่อองค์ประกอบ (การอ้างอิงหนึ่งรายการในอาร์เรย์) LinkedList: ประมาณ 48 ไบต์ต่อองค์ประกอบ (อ็อบเจ็กต์ Node ที่มีข้อมูล การอ้างอิงไปยังโหนดก่อนหน้าและถัดไป รวมถึงส่วนหัวอ็อบเจ็กต์) สำหรับชุดข้อมูลขนาดใหญ่ ArrayList ใช้หน่วยความจำน้อยกว่าอย่างเห็นได้ชัด

ประสิทธิภาพการวนซ้ำ

การวนซ้ำตามลำดับ (ทีละรายการหรือด้วยตัววนซ้ำ) ใช้เวลา O(n) สำหรับทั้งสองแบบ แต่ ArrayList ได้ประโยชน์จากการดึงข้อมูลล่วงหน้าของแคช CPU เพราะองค์ประกอบอยู่ต่อเนื่องกันในหน่วยความจำ ส่วนโหนดของ LinkedList กระจายอยู่ทั่วฮีป ทำให้เกิดการพลาดแคช

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

การเพิ่มหรือลบตรงกลาง

ทั้งสองแบบต้องใช้เวลา O(n) เพื่อค้นหาตำแหน่ง เมื่อพบแล้ว ArrayList จะเลื่อนองค์ประกอบด้วยเวลา O(n) ส่วน LinkedList เพียงถอดการเชื่อมโยงด้วยเวลา O(1) ดังนั้นสำหรับการเปลี่ยนแปลงตรงกลางบ่อยครั้ง เมื่อคุณมีตัววนซ้ำอยู่แล้ว LinkedList จะเหนือกว่า แต่ในกรณีอื่นทั้งสองแบบใกล้เคียงกัน

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

แนวทางการตัดสินใจ

เลือกโดยพิจารณาการดำเนินการที่ใช้เป็นหลัก:

  • ArrayList: การเข้าถึงแบบสุ่ม การวนซ้ำ และการเพิ่มต่อท้าย — ครอบคลุมกรณีใช้งาน 90%
  • LinkedList: การเพิ่มหรือนำรายการออกจากหัวหรือต้ายบ่อยครั้ง รวมถึงการสร้างคิว คิวสองทาง หรือสแตก
  • ArrayDeque: หากต้องการคิวหรือสแตกโดยเฉพาะ ซึ่งดีกว่า LinkedList

สรุปการทดสอบประสิทธิภาพ

กรอบความคิดสำหรับประสิทธิภาพ:

  • get(i): ArrayList O(1) เทียบกับ LinkedList O(n)
  • add(0,x): ArrayList O(n) เทียบกับ LinkedList O(1)
  • add(x): ทั้งสองแบบมีค่าเฉลี่ยแบบตัดจำหน่ายเป็น O(1)
  • การนำออกด้วยตัววนซ้ำ: ทั้งสองแบบเป็น O(1) เมื่ออยู่ที่ตำแหน่งแล้ว
  • หน่วยความจำต่อองค์ประกอบ: ArrayList ประมาณ 8B เทียบกับ LinkedList ประมาณ 48B

ตรวจสอบความเข้าใจอย่างรวดเร็ว

คุณกำลังสร้างคิวงานที่มีการเพิ่มงานที่ท้ายและนำงานออกจากด้านหน้าหลายล้านครั้งต่อวินาที โครงสร้างข้อมูลใดเหมาะสมที่สุด

สรุป: LinkedList เทียบกับ ArrayList

ประเด็นสำคัญ:

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

คำถามที่พบบ่อย

บทเรียน “ข้อแลกเปลี่ยนระหว่าง LinkedList กับ ArrayList” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “ข้อแลกเปลี่ยนระหว่าง LinkedList กับ ArrayList” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Java Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Java Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “ข้อแลกเปลี่ยนระหว่าง LinkedList กับ ArrayList”

เปรียบเทียบประสิทธิภาพการแทรก การลบ และการเข้าถึงแบบสุ่ม เพื่อเลือกชนิดรายการที่เหมาะสม คุณปฏิบัติ Java Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Java Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Java Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน

บทเรียน “ข้อแลกเปลี่ยนระหว่าง LinkedList กับ ArrayList” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน Java Academy นี้ได้ไหม

ได้ บทเรียน Java Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. โครงสร้างภายในของ LinkedList
  2. การทำงานของ Deque: สแตกและคิว
  3. ข้อแลกเปลี่ยนระหว่าง LinkedList กับ ArrayList
  4. PriorityQueue สำหรับการประมวลผลตามลำดับ
← กลับไปที่ Java Academy