ความแตกต่างระหว่าง Array List และ Linked List ความแตกต่างระหว่าง

ข้อมูลมีการจัดเก็บอย่างไร?

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

อาร์เรย์แบบไดนามิกและรายการที่เชื่อมโยง

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

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

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

ขนาดของรายการอาร์เรย์เริ่มต้นและรายการที่เชื่อมโยง

ด้วยรายการอาร์เรย์แม้รายการว่างจะต้องมีขนาด 10 แต่มีรายการที่เชื่อมโยงกันเราไม่จำเป็นต้องมีพื้นที่มากนัก เราสามารถสร้างรายการที่เชื่อมต่อว่างเปล่าที่มีขนาดเท่ากับ 0. ต่อมาเราสามารถเพิ่มขนาดได้ตามที่ต้องการ

การดึงข้อมูล

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

End of Data

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

Reverse Traversal

รายการที่เชื่อมโยงช่วยให้เราสามารถท่องไปในทิศทางย้อนกลับได้ด้วยความช่วยเหลือของ descendingiterator () อย่างไรก็ตามเราไม่มีสถานที่ดังกล่าวในรายการอาร์เรย์ - การข้ามกลับเป็นการกลายเป็นปัญหาที่นี่

ไวยากรณ์

ให้เราดูไวยากรณ์ Java ของกลไกการเก็บข้อมูลทั้งสอง

การสร้างรายการอาร์เรย์:

arraylistsample list = new ArrayList ();

การเพิ่มวัตถุลงในอาร์เรย์รายการ:

Arraylistsample เพิ่ม (“name1”);

Arraylistsample เพิ่ม (“name2”);

นี่คือผลลัพท์ของ Array list - [name1, name2]

การสร้างรายการที่เชื่อมโยง:

รายการ linkedlistsample = new linkedList (); การเพิ่มวัตถุลงในรายการที่เชื่อมโยง:

Linkedlistsample เพิ่ม (“NAME3”); Linkedlistsample เพิ่ม (“NAME4”);

นี่คือผลที่ได้จากรายการที่เชื่อมโยงจะเป็นอย่างไร - [name3, name4]

ซึ่งจะดีกว่าสำหรับการดำเนินการค้นหาหรือการค้นหา

รายการอาร์เรย์ใช้เวลา O (1) เพื่อเรียกค้นข้อมูลใด ๆ ในขณะที่รายการที่เชื่อมโยงจะใช้เวลา O (n) สำหรับการค้นหาข้อมูล n th 999 ดังนั้นรายการอาร์เรย์จะใช้เวลาคงที่สำหรับการค้นหาข้อมูลเสมอ แต่ในรายการที่เชื่อมโยงเวลาที่ใช้ขึ้นอยู่กับตำแหน่งของข้อมูล ดังนั้นรายการอาร์เรย์จึงเป็นทางเลือกที่ดีกว่าสำหรับการดำเนินการค้นหาหรือการค้นหา

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

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

เร็วกว่านี้?

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

เมื่อใดควรใช้รายการอาร์เรย์และรายการที่เชื่อมโยง

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

ลองดูความแตกต่างในรูปแบบตาราง S

ใช้การจัดเก็บข้อมูลตามลำดับ

ใช้การจัดเก็บข้อมูลที่ไม่ต่อเนื่อง

2 < การจัดเก็บข้อมูลภายใน	การจัดเก็บข้อมูลภายใน	การบำรุงรักษาอาร์เรย์แบบไดนามิกภายใน
รักษารายการที่เชื่อมโยง	3
การใช้หน่วยความจำ	ต้องการพื้นที่หน่วยความจำเพียงสำหรับข้อมูล	ต้องใช้พื้นที่หน่วยความจำสำหรับข้อมูล	ต้องการพื้นที่ว่างอย่างน้อย 10 รายการ
ไม่ต้องการพื้นที่และเราสามารถสร้างรายการที่เชื่อมโยงกับรายการที่ว่างเปล่าขนาด	5	การเรียกค้นข้อมูล	คำนวณเช่นตำแหน่งข้อมูลแรก + 'n' โดยที่ 'n' คือลำดับของข้อมูลในรายการ Array
Traversal ตั้งแต่ครั้งแรกหรือครั้งสุดท้ายจนกว่าจะถึงข้อมูลที่ต้องการ	6 < End of Data	ค่า Null จะทำเครื่องหมายปลาย	Null Pointer จะทำเครื่องหมาย
7	Reverse Traversal	ไม่อนุญาต	อนุญาตด้วยความช่วยเหลือของ descendingiterator)
8	การสร้างรายชื่อไวยากรณ์	รายการ arraylistsample = new Array รายการ ();	list linkedlistsample = new linkedList ();
9	การเพิ่มวัตถุ	Arraylistsample เพิ่ม (“name1”);	Linkedlistsample เพิ่ม (“NAME3”);
10	รับหรือค้นหา	ใช้เวลา O (1) และมีประสิทธิภาพที่ดีขึ้น	ใช้เวลา O (n) และประสิทธิภาพขึ้นอยู่กับตำแหน่งของข้อมูล
11	แทรกหรือเพิ่ม	ใช้เวลา O (1) ยกเว้นเมื่ออาร์เรย์เต็ม	ใช้เวลา O (1) ในทุกสถานการณ์
12	การลบหรือลบ	ใช้เวลา O (n) ใช้เวลา O (n)	13
เมื่อใช้?	เมื่อมีการดำเนินการเกี่ยวกับ Get หรือ Search จำนวนมาก ความพร้อมใช้งานของหน่วยความจำควรจะสูงขึ้นแม้ในช่วงเริ่มต้น	เมื่อมีการแทรกหรือลบจำนวนมากและความพร้อมใช้งานหน่วยความจำไม่จำเป็นต้องต่อเนื่อง	แนะนำ ความแตกต่างระหว่าง Kung Fu และ Wushu: Kung Fu vs. Wushu ความแตกต่างระหว่าง Kung Pao และ General Tso Kung Fu และ Taekwondo: ความแตกต่างระหว่าง Kung Fu และ Taekwondo