แนะนำคอลเลกชัน LinkedList

1. ประวัติของLinkedList

Java มี Java คลาสคอลเลกชันอื่นที่สืบทอดมาจากภาษา C ++ นี่คือLinkedListคลาสซึ่งใช้ "รายการที่เชื่อมโยง"

ภายนอก a LinkedListดูเหมือนจะเหมือนกับ a ArrayList. คลาสLinkedListมีเมธอดเดียวกับArrayListคลาส โดยหลักการแล้ว คุณสามารถใช้ a LinkedListแทน an ArrayListและทุกอย่างจะทำงานได้

เหตุใดเราจึงต้องการคลาสรายการอื่น

คำตอบมีทุกอย่างที่เกี่ยวข้องกับโครงสร้างภายในของLinkedListชั้นเรียน แทนที่จะเป็นอาร์เรย์ จะใช้ รายการที่เชื่อมโยงเป็น สองเท่า เราจะอธิบายให้ทราบในภายหลัง

โครงสร้างภายในที่แตกต่างกันของ คลาสLinkedListทำให้แทรกองค์ประกอบตรงกลางรายการได้เร็วที่สุด

บนอินเทอร์เน็ต คุณมักจะพบการเปรียบเทียบของArrayListและLinkedListคลาส:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

ทุกอย่างชัดเจนเพียงพอ: หากคุณต้องการแทรกองค์ประกอบในรายการบ่อยๆ ให้ใช้LinkedList; ถ้าไม่ค่อยใช้ ArrayList แต่ความเป็นจริงแตกต่างกันเล็กน้อย

2. ไม่มีใครใช้LinkedList

ไม่มีใครใช้LinkedList.

แม้แต่ผู้เขียนชั้นLinkedListเรียนก็ทวีตเมื่อเร็ว ๆ นี้: "มีใครใช้จริง ๆ ไหมLinkedListฉันเขียนมัน แต่ฉันไม่เคยใช้เลย"

แล้วข้อตกลงคืออะไร?

อย่างแรกชั้นArrayListเรียนเริ่มสามารถแทรกองค์ประกอบต่างๆ ลงตรงกลางรายการได้อย่างรวดเร็ว เมื่อแทรกองค์ประกอบตรงกลางรายการ คุณต้องเลื่อนองค์ประกอบทั้งหมดหลังจุดแทรกไป 1 ไปทางท้ายรายการ สิ่งนี้เคยใช้เวลา

แต่ตอนนี้ทุกอย่างเปลี่ยนไป องค์ประกอบทั้งหมดของอาร์เรย์อยู่ใกล้กันในบล็อกหน่วยความจำเดียวกัน ดังนั้นการดำเนินการเพื่อเลื่อนองค์ประกอบจึงดำเนินการโดยคำสั่งระดับต่ำที่รวดเร็วมาก:System.arraycopy()

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

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

หากคุณเพียงเพิ่มองค์ประกอบให้กับLinkedListวัตถุภายในลูป การแทรกอย่างรวดเร็วแต่ละครั้งจะมาพร้อมกับการดำเนินการ "รับองค์ประกอบ" ที่ช้า

ความจริงอยู่ใกล้กว่านี้มาก:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

เหตุใดจึงได้รับองค์ประกอบจากLinkedListการดำเนินการที่ช้าเช่นนี้

LinkedListคุณสามารถตอบคำถามนี้ได้หลังจากทำความคุ้นเคยกับ โครงสร้างแล้วเล็กน้อย

3. LinkedListมีโครงสร้าง อย่างไร

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

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

นี่คือลักษณะของรายการดังกล่าวในหน่วยความจำ:

ส่วนหัวและส่วนท้าย (เซลล์ที่มีพื้นหลังสีเทา) คือ ตัวแปร firstและlastซึ่งเก็บการอ้างอิงถึงNodeวัตถุ

ตรงกลาง คุณมีห่วงโซ่ของNodeวัตถุ (วัตถุ ไม่ใช่ตัวแปร) แต่ละรายการประกอบด้วยสามฟิลด์:

• prev— เก็บข้อมูลอ้างอิง (ลิงค์) ไปยังNodeวัตถุก่อนหน้า (เซลล์ที่มีพื้นหลังสีเหลือง)
• value— เก็บค่าขององค์ประกอบนี้ของรายการ (เซลล์ที่มีพื้นหลังสีเขียว)
• next— เก็บข้อมูลอ้างอิง (ลิงก์) ไปยังNodeวัตถุถัดไป (เซลล์ที่มีพื้นหลังสีน้ำเงิน)

วัตถุที่สอง (ที่อยู่ F24) คือวัตถุถัดไป ( next) สำหรับวัตถุแรกและวัตถุก่อนหน้า ( prev) สำหรับวัตถุที่สาม ฟิลด์สีเหลืองของวัตถุที่สามมีที่อยู่ F24 และฟิลด์สีน้ำเงินของวัตถุแรกมีที่อยู่ F24

ลูกศรจากวัตถุชิ้นแรกและชิ้นที่สามชี้ไปยังวัตถุชิ้นที่สองเดียวกัน ดังนั้นการวาดลูกศรแบบนี้จึงถูกต้องกว่า

4. แทรกองค์ประกอบลงในรายการที่เชื่อมโยง

ในการเพิ่มคนในสายแบบนี้ คุณเพียงแค่ต้องได้รับอนุญาตจากคนสองคนที่ยืนอยู่ข้างกัน คนแรกจำผู้มาใหม่ว่า "คนที่อยู่ข้างหลังฉัน" และคนที่สองจะจำพวกเขาในฐานะ

สิ่งที่คุณต้องทำคือเปลี่ยนการอ้างอิงของวัตถุที่อยู่ใกล้เคียงทั้งสอง:

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

การลบองค์ประกอบนั้นง่ายกว่า: ถ้าเราต้องการลบ เช่น ออบเจ็กต์ที่ 100 จากรายการ เราเพียงแค่เปลี่ยนฟิลด์nextสำหรับออบเจ็กต์ที่ 99 เพื่อให้ชี้ไปที่ออบเจ็กต์ที่ 101 และเปลี่ยนฟิลด์prevสำหรับออบเจ็กต์ที่ 101 คัดค้านเพื่อให้ชี้ไปที่ 99 แค่นั้นแหละ.

แต่การจะได้วัตถุชิ้นที่ 100 นั้นไม่ใช่เรื่องง่าย

5. ลบองค์ประกอบออกจากรายการ

ในการรับองค์ประกอบที่ 100 ของรายการที่เชื่อมโยง คุณต้อง:

รับวัตถุที่ 1: คุณทำได้โดยใช้firstตัวแปรในLinkedListวัตถุ ฟิลด์nextของวัตถุที่ 1 เก็บการอ้างอิงถึงวัตถุที่ 2 นั่นคือวิธีที่เราได้วัตถุชิ้นที่สอง วัตถุชิ้นที่ 2 มีการอ้างอิงถึงวัตถุชิ้นที่ 3 เป็นต้น

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

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

นั่นคือสิ่งที่เรากำลังเผชิญอยู่

เหตุใดเราจึงสอนคุณว่าLinkedListการทำงาน ช้านี้ทำงานอย่างไร

ในระหว่างการสัมภาษณ์งาน คุณจะถูกถามว่าLinkedListแตกต่างจากArrayList . อย่างแน่นอน.