อาร์เรย์แบบไดนามิกใน Java

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

อาร์เรย์แบบไดนามิกในหลักสูตร JavaRush

หัวข้อนี้ครอบคลุมอย่างชาญฉลาดและชัดเจนที่ระดับ 7และบางส่วนที่ระดับ 8ของหลักสูตร JavaRush ในภารกิจ Java Syntax ในระหว่างการบรรยายหลายครั้งและปัญหามากถึง 18 ข้อ ประเด็นสำคัญต่างๆ จะถูกกล่าวถึง ประเภทของอาร์เรย์ไดนามิก และความแตกต่างระหว่างประเด็นเหล่านั้น รวมถึงประสิทธิภาพด้วย หัวข้อนี้มีความสำคัญอย่างยิ่ง เนื่องจากอาร์เรย์แบบไดนามิกช่วยบรรเทาอาการซึมเศร้า ปวดหัว และประหยัดเวลาได้อย่างไม่น่าเชื่อ

อาร์เรย์แบบไดนามิกคืออะไร?

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

เหตุใดเราจึงต้องมีอาร์เรย์แบบไดนามิก

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

1. สร้างอาร์เรย์ขนาดใหญ่ที่น่าจะครอบคลุมความต้องการได้ 100%
2. สร้างอาร์เรย์แบบคงที่ที่จะทำหน้าที่เป็นบัฟเฟอร์
3. ใช้โครงสร้างไดนามิกอื่นๆ เช่น เซต

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

อาร์เรย์แบบไดนามิกทำอะไรใน Java?

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

ArrayList, LinkedList - แนวคิดและกฎการดำเนินงาน

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

• เช่นเดียวกับอาร์เรย์แบบคงที่ มันถูกจัดทำดัชนีจาก 0;
• การแทรกที่ส่วนท้ายและการเข้าถึงโดยดัชนีทำได้รวดเร็วมาก - O(1);
• หากต้องการแทรกองค์ประกอบที่จุดเริ่มต้นหรือตรงกลาง คุณจะต้องคัดลอกองค์ประกอบทั้งหมดไปทางขวาหนึ่งเซลล์ แล้ววางองค์ประกอบใหม่ในตำแหน่งที่ต้องการ
• การเข้าถึงตามค่าขึ้นอยู่กับจำนวนองค์ประกอบ - O(n);
• ต่างจากอาร์เรย์แบบคลาสสิกตรงที่สามารถเก็บค่าว่างได้

ในกรณีของ LinkedList ทุกอย่างจะซับซ้อนขึ้นเล็กน้อย: ขึ้นอยู่กับรายการที่เชื่อมโยงแบบทวีคูณ กล่าวคือ ในเชิงโครงสร้างแล้วอาเรย์ Java แบบไดนามิก นี้ คืออ็อบเจ็กต์ที่กระจัดกระจายจำนวนหนึ่งซึ่งอ้างอิงถึงกันและกัน อธิบายด้วยภาพง่ายกว่าครับ ภายใน LinkedList เรามีวัตถุหลักHeadซึ่งเก็บข้อมูลเกี่ยวกับจำนวนองค์ประกอบ เช่นเดียวกับลิงก์ไปยังองค์ประกอบแรกและสุดท้าย: ตอนนี้ฟิลด์size = 0คือfirstและ last = nullแต่ละองค์ประกอบที่เพิ่มลงในรายการนี้คือเนื้อหาของออบเจ็กต์ภายในที่แยกจากกัน มาเพิ่มองค์ประกอบกันJohnny: ตอนนี้เรามีโหนดที่มีค่า “จอห์นนี่” สำหรับองค์ประกอบหลัก ลิงก์ไปยังองค์ประกอบแรกและองค์ประกอบสุดท้ายจะชี้ไปที่โหนดใหม่ วัตถุนี้ยังมีลิงก์ไปยังองค์ประกอบก่อนหน้าและถัดไป ลิงก์ไปยังรายการก่อนหน้าจะเป็นโมฆะเสมอ เนื่องจากนี่คือองค์ประกอบแรก และลิงก์ไปยังรายการถัดไปจะเป็นโมฆะเสมอ เนื่องจากยังไม่มีอยู่ มาแก้ไขปัญหานี้: เพิ่มองค์ประกอบใหม่ด้วยค่า "วัตสัน" ซึ่งกลายเป็นองค์ประกอบที่สอง โปรดทราบว่าองค์ประกอบแรกมีช่องnextที่ชี้ไปยังองค์ประกอบถัดไป และองค์ประกอบใหม่มีช่องpreviousที่ชี้ไปยังองค์ประกอบก่อนหน้า สำหรับองค์ประกอบหลัก ลิงก์ไปยังองค์ประกอบสุดท้ายจะชี้ไปที่โหนดใหม่ แผนภาพต่อไปนี้แสดงวิธีการเพิ่มองค์ประกอบตรงกลางรายการ: มีการเพิ่มองค์ประกอบใหม่ “Hamish” แล้ว หากต้องการแทรกไว้ตรงกลางรายการ เพียงกำหนดลิงก์ให้กับองค์ประกอบใหม่ ดังแสดงในรูป ภาพประกอบเหล่านี้จะอธิบายกระบวนการของรายการที่เชื่อมโยงแบบทวีคูณที่ระดับบนสุด โดยไม่ต้องลงรายละเอียด เพื่อสรุปเรื่องราวเกี่ยวกับ LinkedList เราสามารถใช้กฎต่างๆ ในการทำงานได้:

• เช่นเดียวกับอาร์เรย์ มันถูกจัดทำดัชนีจาก 0;
• การเข้าถึงองค์ประกอบแรกและองค์ประกอบสุดท้ายไม่ได้ขึ้นอยู่กับจำนวนองค์ประกอบ - O(1);
• การรับองค์ประกอบตามดัชนี การแทรกหรือการลบจากตรงกลางรายการขึ้นอยู่กับจำนวนองค์ประกอบ - O(n);
• คุณสามารถใช้กลไกตัววนซ้ำ: จากนั้นการแทรกและการลบจะเกิดขึ้นในเวลาคงที่
• ต่างจากอาเรย์คลาสสิกตรงที่สามารถเก็บค่าว่างได้

ตัวอย่างโค้ด

เรามาดูตัวอย่างกัน ข้อมูลโค้ดประกอบด้วยตัวอย่างสำหรับทั้ง ArrayList และ LinkedList

การสร้าง

// Создаем новый список
ArrayList<String> arrayList = new ArrayList<>();
// Создается новый список и указывается начальный размер внутреннего массива
ArrayList<String> arrayListLarge = new ArrayList<>(100000);

// Создаем новый LinkedList
LinkedList<String> linkedList = new LinkedList<>();

การเพิ่มองค์ประกอบ

// Новый элемент добавляется в конец
arrayList.add("Johhny");
// Новый элемент добавляется в указанную позицию (в данном случае — в начало)
arrayList.add(0, "Watson");

// Новый элемент добавляется в конец двусвязного списка
linkedList.add("Java");
// Новый элемент добавляется в нулевую позицию списка:
linkedList.addFirst("I think");
// Новый элемент добавляется в конец списка
linkedList.addLast("language");
// Новый элемент добавляется в указанную позицию
linkedList.add(2, "is a terrific");

// Получение размера списков
int arraySize = arrayList.size(); // 2
int linkedSize = linkedList.size(); // 4

เมื่อมองแวบแรก เมธอด add()AND addLast()จะทำงานเหมือนกัน แต่เมธอดadd()มาที่ LinkedList จากอินเทอร์เฟซListและวิธีการนั้นaddLastมาจากอินเทอร์เฟDequeซ LinkedList ใช้อินเทอร์เฟซทั้งสองนี้ แนวทางปฏิบัติที่ดีในกรณีนี้คือการใช้วิธีการที่เหมาะสมกับบริบทมากที่สุด หากใช้ LinkedList เป็นคิว วิธีที่ดีที่สุดคือใช้ส่วนขยายaddLast. หากใช้ LinkedList เป็นรายการ จะเหมาะสมที่จะใช้add().

การลบองค์ประกอบ

// Удаление element по индексу
arrayList.remove(0);
// Удаление element по значению
arrayList.remove("Johnny");

// Удаление первого element в списке
linkedList.removeFirst();
// Удаление первого element в списке, фактически вызов предыдущего метода
linkedList.remove();
// Удаление последнего element в списке
linkedList.removeLast();
// Удаление первого вхождения element в список
linkedList.removeFirstOccurrence("language");
// Удаление последнего вхождения element в список
linkedList.removeLastOccurrence("Java");
// Удаление по индексу
linkedList.remove(2);

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

การเข้าถึงองค์ประกอบและการค้นหารายการ

// Доступ к элементу по индексу
String arrayElement = arrayList.get(2);
// Поиск element по значению
int arrayIndex = arrayList.indexOf("Watson");
// Поиск последнего индекса вхождения element в список
int lastArrayIndex = arrayList.lastIndexOf("Watson");

// Доступ по индексу
String linkedElement = linkedList.get(3);
// Получение первого element
String firstLinkedElement = linkedList.getFirst();
// Получение последнего element
String lastLinkedElement = linkedList.getLast();

// Поиск element по значению
int linkedIndex = linkedList.indexOf("Java");
// Поиск последнего индекса вхождения element в список
int lastLinkedIndex = linkedList.lastIndexOf("Java");

เดินเป็นวง

// Использование обычного цикла
for(int i = 0; i<arrayList.size(); i++) {
  String value = arrayList.get(i);
  System.out.println(value);
}

for(int i = 0; i<linkedList.size(); i++) {
  String value = linkedList.get(i);
  System.out.println(value);
}

// Использование цикла for-each
for(String s : arrayList) {
  System.out.println(s);
}

for(String s : linkedList) {
  System.out.println(s);
}

นี่มันคุ้มค่าที่จะพูดคำสองสามคำเกี่ยวกับการค้นหา นักพัฒนามือใหม่หลายคนเมื่อค้นหาองค์ประกอบในรายการให้เริ่มการค้นหาแบบวนซ้ำเปรียบเทียบองค์ประกอบทั้งหมดกับองค์ประกอบที่ค้นหาแม้ว่าจะมีวิธีการindexOf()และlastIndexOf()ก็ตาม คุณยังสามารถใช้วิธีนี้contains()เพื่อรับความจริงที่ว่าองค์ประกอบนั้นอยู่ในรายการ:

boolean isContainsSherlock = arrayList.contains("Sherlock");
boolean isContainsPhp = linkedList.contains("Php");

ลิงค์สำหรับอ่านเพิ่มเติม

1. มีบทความดีๆเกี่ยวกับการลบองค์ประกอบออกจาก ArrayList เนื่องจากนี่คืออาร์เรย์ Java แบบไดนามิกจึงมีรายละเอียดปลีกย่อยมากมายในการลบองค์ประกอบ
2. รายละเอียดการ ทำงาน ของ ArrayList แสดงไว้ ที่นี่
3. ข้อมูลเพิ่มเติมเล็กน้อยเกี่ยวกับ LinkedList
4. บทความสองสามบทความจาก Habr เกี่ยวกับArrayListและLinkedList