ArrayList ในรูปภาพ

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

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

อันดับแรก มาดูกันว่าการเพิ่มองค์ประกอบใหม่จะมีลักษณะอย่างไร ลำดับแรกของธุรกิจคือการตรวจสอบว่าอาร์เรย์ภายในมีพื้นที่เพียงพอในอาร์เรย์ภายในหรือไม่ และองค์ประกอบอื่นจะพอดีหรือไม่ หากมีที่ว่าง องค์ประกอบใหม่จะถูกเพิ่มที่ส่วนท้ายของรายการ เมื่อเราพูดว่า "ท้ายสุด" เราไม่ได้หมายถึงตำแหน่งสุดท้ายในอาร์เรย์ (ซึ่งคงจะแปลก) เราหมายถึงตำแหน่งต่อจากองค์ประกอบปัจจุบันล่าสุด ดัชนีของมันจะcars.size()เป็น รายการของเราว่างเปล่าในขณะนี้ ( cars.size() == 0) ดังนั้น องค์ประกอบใหม่จะถูกเพิ่มที่ตำแหน่ง 0

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

ที่ชัดเจนเพียงพอ จะเกิดอะไรขึ้นถ้าเราไปแทรกกลางระหว่างองค์ประกอบอื่นๆ

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");
  
   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
  
   cars.add(1, ford);// add ford to cell 1, which is already occupied
}

ก่อนอื่นให้ตรวจสอบว่ามีพื้นที่เพียงพอในอาร์เรย์หรือไม่ หากมีที่ว่างเพียงพอองค์ประกอบต่างๆ จะถูกเลื่อนไปทางขวาโดยเริ่มจากตำแหน่งที่เราแทรกองค์ประกอบใหม่ เรากำลังแทรกที่ตำแหน่ง 1 กล่าวคือ องค์ประกอบจากตำแหน่ง 3 จะถูกคัดลอกไปยังตำแหน่ง 4 องค์ประกอบ 2 ไปยังตำแหน่ง 3 และองค์ประกอบ 1 ไปยังตำแหน่ง 2 จากนั้นองค์ประกอบใหม่ของเราจะถูกแทรกเข้า แทนที่ องค์ประกอบก่อนหน้า (bugatti) ได้ถูกคัดลอกจากที่นั่นไปยังตำแหน่งใหม่แล้ว ทีนี้มาดูกันว่ากระบวนการนี้เกิดขึ้นได้อย่างไรหากไม่มีที่สำหรับแทรกองค์ประกอบใหม่ลงในอาร์เรย์ โดยธรรมชาติแล้ว อันดับแรกต้องตรวจสอบดูว่ามีพื้นที่ว่างเพียงพอหรือไม่ หากมีที่ว่างไม่เพียงพอ อาร์เรย์ใหม่จะถูกสร้างขึ้นภายในArrayListซึ่งขนาดคือขนาดของอาร์เรย์เก่าคูณ 1.5 บวก 1 ในกรณีของเรา ขนาดของอาร์เรย์ใหม่จะเป็น 16 องค์ประกอบปัจจุบันทั้งหมดจะถูกคัดลอกไปยังที่นั่นทันที อาร์เรย์เก่าจะถูกลบโดยตัวเก็บขยะ และจะเหลือเพียงอาร์เรย์ใหม่ที่ขยายแล้วเท่านั้น ขณะนี้มีที่ว่างสำหรับองค์ประกอบใหม่ เรากำลังแทรกที่ตำแหน่ง 3 ซึ่งถูกครอบครอง ตอนนี้ขั้นตอนที่คุ้นเคยเริ่มต้นขึ้น องค์ประกอบทั้งหมด เริ่มต้นด้วยดัชนี 3 ถูกเลื่อนไปทางขวา 1 ตำแหน่ง และเพิ่มองค์ประกอบใหม่อย่างเงียบๆ และการใส่ก็เสร็จเรียบร้อย! และเราก็เสร็จสิ้นการแทรก ตอนนี้เรามาพูดถึงการลบรายการ . คุณจะจำได้ว่าเราประสบปัญหาเมื่อทำงานกับอาร์เรย์: การลบองค์ประกอบทำให้เกิด "ช่องโหว่" ในอาร์เรย์ในการลบแต่ละครั้ง และเราต้องเขียนโค้ดของเราเองทุกครั้งเพื่อทำการเปลี่ยนแปลงนี้ ArrayList ใช้หลักการเดียวกัน แต่ใช้กลไกนี้แล้ว หน้าตาเป็นแบบนี้ และในที่สุดเราก็ได้สิ่งที่เราต้องการ องค์ประกอบlamboถูกลบออกไปแล้ว ที่นี่เราลบองค์ประกอบออกจากตรงกลาง เห็นได้ชัดว่าการลบองค์ประกอบออกจากส่วนท้ายของรายการนั้นเร็วกว่า เนื่องจากองค์ประกอบนั้นจะถูกลบออกอย่างง่ายดายโดยไม่จำเป็นต้องเปลี่ยนองค์ประกอบอื่นๆ ทั้งหมด เรามาคุยกันอีกครั้งเกี่ยวกับขนาดของอาร์เรย์ภายในและวิธีจัดเรียงในหน่วยความจำ การขยายอาร์เรย์ต้องใช้ทรัพยากรบางอย่าง ดังนั้นอย่าสร้างไฟล์ArrayListด้วยขนาดเริ่มต้น หากคุณแน่ใจว่าจะต้องมีองค์ประกอบอย่างน้อย 100 รายการ อาร์เรย์ภายในจะต้องขยาย6 เท่าเมื่อคุณแทรกองค์ประกอบที่ 100 และองค์ประกอบทั้งหมดจะต้องถูกเลื่อนในแต่ละครั้ง

• จาก 10 องค์ประกอบเป็น 16
• จาก 16 องค์ประกอบเป็น 25
• จาก 25 ถึง 38
• จาก 38 ถึง 58
• จาก 58 เป็น 88
• จาก 88 เป็น 133 (เช่น ขนาดของอาร์เรย์เก่าคูณ 1.5 บวก 1)

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

ArrayList<Car> cars = new ArrayList<>(100);

ตอนนี้หน่วยความจำสำหรับอาร์เรย์ที่มีองค์ประกอบ 100 รายการจะได้รับการจัดสรรทั้งหมดในคราวเดียว ทำให้อาร์เรย์มีประสิทธิภาพมากขึ้น (ไม่จำเป็นต้องขยาย) กลยุทธ์นี้ยังมีด้านพลิก เมื่อคุณลบวัตถุออกจากArrayListขนาดของอาร์เรย์ภายในจะไม่ลดลงโดยอัตโนมัติ สมมติว่าเรามีArrayListอาร์เรย์ภายในที่สมบูรณ์ซึ่งมีองค์ประกอบ 88 รายการ: ขณะที่โปรแกรมทำงาน เราลบองค์ประกอบ 77 รายการ ดังนั้นจะเหลือเพียง 11 รายการ คุณเดาแล้วหรือยังว่าปัญหาคืออะไร เข้าใจแล้ว ใช้หน่วยความจำไม่เต็มประสิทธิภาพ! เราใช้เพียง 11 ตำแหน่งที่นี่ แต่เราได้จัดสรรหน่วยความจำสำหรับ 88 องค์ประกอบ ซึ่งมากกว่าที่เราต้องการถึง 8 เท่า! ในกรณีนี้ เราสามารถเพิ่มประสิทธิภาพการใช้หน่วยความจำของเราด้วยArrayListวิธีพิเศษของคลาส:trimToSize(). วิธีนี้ "ตัดแต่ง" ความยาวของอาร์เรย์ภายในให้เท่ากับจำนวนองค์ประกอบที่จัดเก็บอยู่ในนั้น ตอนนี้เราได้จัดสรรหน่วยความจำเท่าที่เราต้องการเท่านั้น! :)