Array เป็นบล็อกหน่วยความจำที่ต่อเนื่องกันซึ่งเก็บองค์ประกอบของประเภทเดียวกัน โดยมีดัชนีตั้งแต่ 0 เนื่องจากองค์ประกอบอยู่ติดกัน ที่อยู่ขององค์ประกอบ i จึงคำนวณได้โดยตรงเป็น base + i * elementSize ซึ่งให้ O(1) การเข้าถึงแบบสุ่ม
index: 0 1 2 3 4
+-----+-----+-----+-----+-----+
arr = | 10 | 20 | 30 | 40 | 50 |
+-----+-----+-----+-----+-----+
address: base +4 +8 +12 +16 (4-byte ints)
arr = [10, 20, 30, 40, 50]
x = arr[3] # O(1) — direct index math
arr.append(60) # amortized O(1) (dynamic array)
arr.insert(0, 5) # O(n) — shift every element right
arr.pop(0) # O(n) — shift every element left
| การดำเนินการ | เวลา |
|---|---|
| การเข้าถึงตามดัชนี | O(1) |
| การค้นหา (ไม่เรียงลำดับ) | O(n) |
| เพิ่มข้อมูล (ไดนามิก) | O(1) ผ่อนปรน |
| แทรก/ลบที่ด้านหน้า/กลาง | O(n) |
Arrays เป็นพื้นฐานของโครงสร้างอื่นๆ ส่วนใหญ่ — สตริง ตารางแฮช heaps และรายการไดนามิกทั้งหมดสร้างขึ้นจากพวกเขา
Locality ของ cache ของพวกเขามักทำให้ array Big-O "ช้า" เอาชนะโครงสร้างที่อยู่บนพื้นฐานของตัวชี้ "เร็ว" ในเกณฑ์มาตรฐานในโลกแห่งความเป็นจริง