ทั้งสองเก็บลำดับ แต่มี โปรไฟล์ต้นทุนตรงข้าม อาร์เรย์ คือหน่วยความจำต่อเนื่องที่มีการจัดทำดัชนี O(1); รายการที่เชื่อมโยง คือโหนดที่กระจายตัวเชื่อมต่อด้วยตัวชี้ โดยมีการแทรก/ลบ O(1) ที่ปลาย แต่ไม่มีการจัดทำดัชนี
ทั้งสองเก็บลำดับ แต่มี โปรไฟล์ต้นทุนตรงข้าม อาร์เรย์ คือหน่วยความจำต่อเนื่องที่มีการจัดทำดัชนี O(1); รายการที่เชื่อมโยง คือโหนดที่กระจายตัวเชื่อมต่อด้วยตัวชี้ โดยมีการแทรก/ลบ O(1) ที่ปลาย แต่ไม่มีการจัดทำดัชนี
| ปฏิบัติการ | อาร์เรย์ (แบบไดนามิก) | รายการที่เชื่อมโยง |
|---|
| การเข้าถึงตามดัชนี | O(1) | O(n) |
| การค้นหา | O(n) | O(n) |
| แทรก/ลบที่ส่วนหัว | O(n) | O(1) |
| แทรก/ลบที่ส่วนท้าย | O(1) amortized | O(1) พร้อมตัวชี้ส่วนท้าย |
| แทรก/ลบในตรงกลาง | O(n) | O(n) ค้นหา + O(1) การต่อ |
| オーバーヘッド메모리ี | ต่ำ | สูง (ตัวชี้ต่อโหนด) |
| ตำแหน่งแคช | ยอดเยี่ยม | ไม่ดี |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
ในทางปฏิบัติอาร์เรย์มีชัยชนะส่วนใหญ่เพราะตำแหน่งแคชช่วยให้ความแตกต่าง Big-O สำหรับขนาดปกติ
การรู้ทั้งสองข้างช่วยให้คุณสามารถแสดงความคิดเห็นเลือกของคุณในการสัมภาษณ์แทนที่จะเลือกอย่างตาบอด — และอธิบาย ทำไม "O(1) แทรก" ไม่บ่อยเอาชนะอาร์เรย์ต่อเนื่อง