Basic Data Structuresบทที่ 6Array

Array แบบเริ่มจากศูนย์: ครบพื้นฐานที่ต้องใช้จริง

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

1) Array คืออะไร

Array คือโครงสร้างข้อมูลแบบลำดับ (ordered collection) ที่เก็บข้อมูลหลายตัวไว้ในตัวแปรเดียว และเข้าถึงแต่ละสมาชิกด้วยตำแหน่ง (index)

ใช้บ่อยมากกับงานที่ต้องอ่านข้อมูลหลายรายการ เช่น คะแนน, รายการสินค้า, ประวัติธุรกรรม หรือผลลัพธ์จาก API

Recap: ถ้าข้อมูลมีลำดับและต้องเข้าถึงตามตำแหน่งบ่อย Array มักเป็นตัวเลือกแรกที่ดี

2) โครงสร้างการเก็บข้อมูลของ Array

Mental model แบบง่าย: นึกภาพข้อมูลวางเรียงเป็นช่องติดกันเป็นแถว เมื่อต้องอ่านตำแหน่งใดตำแหน่งหนึ่งจึงไปหาได้เร็ว

แต่ถ้าแทรกหรือลบตรงกลาง สมาชิกถัดไปต้องเลื่อนตำแหน่งตาม ซึ่งเป็นเหตุผลว่าทำไมบาง operation จึงช้ากว่า

Recap: Array เร็วเรื่องเข้าถึงตำแหน่ง แต่ช้าลงเมื่อมีการขยับข้อมูลจำนวนมาก

3) Index และการเข้าถึงข้อมูล

Index คือหมายเลขตำแหน่งของสมาชิก โดยทั่วไปเริ่มจาก 0 ดังนั้นสมาชิกตัวแรกคือ index 0

Index AccessTS

เข้าถึงค่าด้วย index โดยตรง

const fruits = ["apple", "banana", "orange"];

const first = fruits[0]; // "apple"
const second = fruits[1]; // "banana"

Recap: อ่านค่าตาม index เป็นงาน O(1) เพราะไปยังตำแหน่งเป้าหมายได้ทันที

4) การอ่านค่าและแก้ไขค่าใน Array

เมื่อรู้ index แล้ว เราอ่านหรือเขียนทับค่าได้ทันที จึงเหมาะกับงานที่มีตำแหน่งเป้าหมายชัดเจน

Read + UpdateTS

อ่านค่าจาก index และเขียนทับตำแหน่งเดิม

function readAndUpdate(scores: number[]) {
  const target = scores[2]; // read
  scores[2] = target + 5; // update
  return scores[2];
}

Recap: read/update ตาม index ปกติเป็น O(1)

5) การวนลูปเพื่ออ่านข้อมูลใน Array

ถ้าต้องประมวลผลทุกสมาชิก เช่น หาผลรวมหรือค่าสูงสุด เราต้องวนลูปผ่านข้อมูลหนึ่งรอบ

for vs for...ofTS

เลือกใช้ตามว่าต้องการ index ด้วยหรือไม่

const values = [10, 20, 30];

for (let i = 0; i < values.length; i += 1) {
  console.log(i, values[i]); // ได้ทั้ง index และ value
}

for (const value of values) {
  console.log(value); // เน้นอ่านค่าอย่างเดียว
}

Recap: การวนอ่านครบทุกตัวมักเป็น O(n)

6) การเพิ่มและลบข้อมูลในตำแหน่งต่าง ๆ

ท้ายอาเรย์

`push` และ `pop` โดยรวมเร็ว (O(1) amortized)

ต้น/กลางอาเรย์

`unshift`, `shift`, `splice` มักเป็น O(n) เพราะข้อมูลหลายตัวต้องเลื่อนตำแหน่ง

Insert / DeleteTS

สังเกตว่าตำแหน่งที่เปลี่ยนมีผลต่อประสิทธิภาพ

const arr = [10, 20, 30];

arr.push(40); // [10, 20, 30, 40]
arr.pop(); // [10, 20, 30]

arr.unshift(5); // [5, 10, 20, 30]
arr.splice(2, 0, 15); // [5, 10, 15, 20, 30]
arr.splice(1, 1); // [5, 15, 20, 30]

Recap: เพิ่ม/ลบท้ายมักเร็วกว่า เพิ่ม/ลบต้นหรือกลาง

7) การค้นหาข้อมูลใน Array

Linear Search (ข้อมูลทั่วไป)

ไล่เทียบทีละตัวจนเจอหรือครบอาเรย์ ใช้ได้กับข้อมูลที่ยังไม่ sorted

Complexity: O(n)

Binary Search (ต้อง sorted ก่อน)

หารช่วงค้นหาครึ่งหนึ่งทุกครั้ง จึงเร็วขึ้นมากเมื่อข้อมูลใหญ่

Complexity: O(log n)

Linear Search ExampleTS

วิธีค้นหาแบบพื้นฐานที่สุดใน Array

function linearSearch(values: number[], target: number) {
  for (let i = 0; i < values.length; i += 1) {
    if (values[i] === target) return i;
  }
  return -1;
}

Recap: ถ้าข้อมูลยังไม่เรียงลำดับ Linear Search คือ baseline ที่ชัดที่สุด

8) Time Complexity ของ Array

Access by index

O(1)

รู้ตำแหน่งแล้วเข้าถึงได้ทันที

Update by index

O(1)

เขียนทับตำแหน่งเดิม

Traversal

O(n)

ต้องอ่านข้อมูลทีละสมาชิก

Search (unsorted)

O(n)

ไล่ตรวจจนเจอหรือครบทุกตัว

Insert/Delete end

O(1) amortized

โดยทั่วไปเร็ว แต่บางครั้งมีค่าขยายความจุ

Insert/Delete middle

O(n)

มีต้นทุน shift ข้อมูล

หมายเหตุเรื่อง amortized ของ `push`

ส่วนใหญ่ `push` เร็วระดับ O(1) แต่บางครั้งต้องขยายความจุภายใน แล้วคัดลอกข้อมูล จึงเรียกผลเฉลี่ยระยะยาวว่า O(1) amortized

9) Static Array vs Dynamic Array

Static Array

ขนาดคงที่ตั้งแต่เริ่ม ใช้ได้ดีเมื่อรู้จำนวนข้อมูลล่วงหน้า

Tradeoff: หน่วยความจำคาดเดาง่าย แต่ยืดหยุ่นน้อย

ตัวอย่างภาษา: เช่น C/C++ array ขนาดตายตัว

Dynamic Array

ขยาย/ย่อขนาดได้ตามการใช้งานจริง

Tradeoff: ยืดหยุ่นสูง แต่ตอนขยายอาจมีต้นทุนคัดลอกข้อมูล

ตัวอย่างภาษา: เช่น JavaScript Array, Python list, Java ArrayList

Recap: static คาดเดาได้ง่าย, dynamic ยืดหยุ่นกว่าในงานแอปพลิเคชันทั่วไป

10) ข้อดีและข้อจำกัดของ Array

ข้อดี

เข้าถึงข้อมูลตาม index เร็ว (O(1))
โครงสร้างเรียบง่าย อ่านโค้ดง่าย
รองรับงานวนลูปและคำนวณเชิงสรุปได้ดี

ข้อจำกัด

เพิ่ม/ลบต้นหรือกลางมีต้นทุนสูงขึ้น (O(n))
ค้นหาในข้อมูลไม่เรียงลำดับยังเป็น O(n)
บางคำสั่ง mutate ข้อมูลเดิมจนเกิดบั๊กได้ง่าย

11) Multi-dimensional Array

Multi-dimensional Array คืออาเรย์ที่เก็บอาเรย์อีกที รูปแบบที่เจอบ่อยคือ 2D array (ตาราง row x column)

2D ArrayTS

เหมาะกับโจทย์ตาราง, เกมกระดาน, แผนที่กริด

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];

const value = matrix[1][2]; // 6 (row 1, col 2)

Recap: 2D array คือการใช้ index หลายชั้น เช่น `matrix[row][col]`

12) เทคนิคพื้นฐานที่ใช้กับ Array

Two Pointers

ใช้กับ: เทียบหัว-ท้าย, ลบซ้ำ, ย้ายค่าตามเงื่อนไข

Rule: ใช้ pointer ซ้าย/ขวาเพื่อลดการวนซ้ำซ้อน

Prefix Sum

ใช้กับ: ตอบคำถามผลรวมช่วง [l, r] หลายครั้ง

Rule: เตรียมข้อมูลสะสมล่วงหน้า แล้วตอบ query เร็วขึ้น

Sliding Window

ใช้กับ: หาช่วงยาวสุด/สั้นสุดตามเงื่อนไข

Rule: ขยายและหดหน้าต่างแทนการเริ่มคำนวณใหม่ทุกครั้ง

Technique ExampleTS

เริ่มจาก pattern ที่สั้นและใช้ซ้ำได้หลายโจทย์

// Two pointers: palindrome
function isPalindrome(nums: number[]) {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    if (nums[left] !== nums[right]) return false;
    left += 1;
    right -= 1;
  }
  return true;
}

13) โจทย์ฝึก Array ระดับเริ่มต้น

Exercise 1: เขียน `getValueAtIndex(arr, index)`

โจทย์: คืนค่าที่ตำแหน่ง index และคืน undefined ถ้า index ไม่ถูกต้อง

Hint: ลองเช็กเงื่อนไข `index < 0` หรือ `index >= arr.length` ก่อนเข้าถึงค่า

Exercise 2: เขียน `sumArray(arr)`

โจทย์: คืนผลรวมของตัวเลขทั้งหมดในอาเรย์

Hint: เริ่ม `total = 0` แล้ววนลูปบวกค่าทีละตัว

Exercise 3: เขียน `insertAtIndex(arr, index, value)` แบบไม่แก้ต้นฉบับ

โจทย์: คืนอาเรย์ใหม่ที่แทรก value ในตำแหน่ง index

Hint: ใช้ `slice` แยกส่วนซ้าย/ขวา แล้วประกอบกลับด้วย spread

Exercise 4: เขียน `findFirstEvenIndex(arr)`

โจทย์: คืน index ของเลขคู่ตัวแรก ถ้าไม่เจอคืน -1

Hint: ใช้ลูป `for` และ `return` ทันทีเมื่อเจอเงื่อนไข

ฝึกต่อใน Session Lab

ใช้หน้า Lab เพื่อลงมือทำจริงและตรวจผลหลายเคสอัตโนมัติ

ไปหน้า Array Lab

14) ข้อผิดพลาดที่พบบ่อยในการใช้ Array

Off-by-one

ปัญหา: เขียนเงื่อนไขลูปผิด เช่น `i <= arr.length` ทำให้เกินขอบเขต

วิธีป้องกัน: จำแพตเทิร์นพื้นฐาน: `for (let i = 0; i < arr.length; i += 1)`

Index out of range

ปัญหา: เข้าถึงตำแหน่งติดลบหรือเกินขนาดโดยไม่ตรวจ

วิธีป้องกัน: ทำ guard clause ก่อนอ่านค่า โดยเฉพาะในฟังก์ชันที่รับ index จากภายนอก

Mutate โดยไม่ตั้งใจ

ปัญหา: ใช้ `sort`, `splice`, `reverse` แล้วกระทบข้อมูลต้นฉบับ

วิธีป้องกัน: ถ้าต้องการ immutable update ให้ copy ก่อน เช่น `const cloned = [...arr]`

ประเมิน Complexity ผิด

ปัญหา: คิดว่า `splice` หรือ `shift` เร็วเท่า `push` ในทุกกรณี

วิธีป้องกัน: จำว่า operation ที่ทำให้สมาชิกจำนวนมากขยับตำแหน่งมักเป็น O(n)

Recap ของทั้งบท

ถ้าจำหลักการ 4 อย่างนี้ได้ คุณจะใช้ Array ได้มั่นใจขึ้นมาก: เข้าใจ index, ระวังการ shift เมื่อแทรก/ลบกลาง, เลือกเทคนิคให้เหมาะโจทย์, และคุมเรื่อง mutation ให้ชัดเจน

Basic Data Structuresบทที่ 6Array

Array แบบเริ่มจากศูนย์: ครบพื้นฐานที่ต้องใช้จริง

1) Array คืออะไร

2) โครงสร้างการเก็บข้อมูลของ Array

Recap: Array เร็วเรื่องเข้าถึงตำแหน่ง แต่ช้าลงเมื่อมีการขยับข้อมูลจำนวนมาก

3) Index และการเข้าถึงข้อมูล

Index AccessTS

เข้าถึงค่าด้วย index โดยตรง

const fruits = ["apple", "banana", "orange"];

const first = fruits[0]; // "apple"
const second = fruits[1]; // "banana"

Recap: อ่านค่าตาม index เป็นงาน O(1) เพราะไปยังตำแหน่งเป้าหมายได้ทันที

4) การอ่านค่าและแก้ไขค่าใน Array

Read + UpdateTS

อ่านค่าจาก index และเขียนทับตำแหน่งเดิม

function readAndUpdate(scores: number[]) {
  const target = scores[2]; // read
  scores[2] = target + 5; // update
  return scores[2];
}

Recap: read/update ตาม index ปกติเป็น O(1)

5) การวนลูปเพื่ออ่านข้อมูลใน Array

for vs for...ofTS

เลือกใช้ตามว่าต้องการ index ด้วยหรือไม่

const values = [10, 20, 30];

for (let i = 0; i < values.length; i += 1) {
  console.log(i, values[i]); // ได้ทั้ง index และ value
}

for (const value of values) {
  console.log(value); // เน้นอ่านค่าอย่างเดียว
}

Recap: การวนอ่านครบทุกตัวมักเป็น O(n)

6) การเพิ่มและลบข้อมูลในตำแหน่งต่าง ๆ

ท้ายอาเรย์

`push` และ `pop` โดยรวมเร็ว (O(1) amortized)

ต้น/กลางอาเรย์

`unshift`, `shift`, `splice` มักเป็น O(n) เพราะข้อมูลหลายตัวต้องเลื่อนตำแหน่ง

Insert / DeleteTS

สังเกตว่าตำแหน่งที่เปลี่ยนมีผลต่อประสิทธิภาพ

const arr = [10, 20, 30];

arr.push(40); // [10, 20, 30, 40]
arr.pop(); // [10, 20, 30]

arr.unshift(5); // [5, 10, 20, 30]
arr.splice(2, 0, 15); // [5, 10, 15, 20, 30]
arr.splice(1, 1); // [5, 15, 20, 30]

Recap: เพิ่ม/ลบท้ายมักเร็วกว่า เพิ่ม/ลบต้นหรือกลาง

7) การค้นหาข้อมูลใน Array

Linear Search (ข้อมูลทั่วไป)

ไล่เทียบทีละตัวจนเจอหรือครบอาเรย์ ใช้ได้กับข้อมูลที่ยังไม่ sorted

Complexity: O(n)

Binary Search (ต้อง sorted ก่อน)

หารช่วงค้นหาครึ่งหนึ่งทุกครั้ง จึงเร็วขึ้นมากเมื่อข้อมูลใหญ่

Complexity: O(log n)

Linear Search ExampleTS

วิธีค้นหาแบบพื้นฐานที่สุดใน Array

function linearSearch(values: number[], target: number) {
  for (let i = 0; i < values.length; i += 1) {
    if (values[i] === target) return i;
  }
  return -1;
}

Recap: ถ้าข้อมูลยังไม่เรียงลำดับ Linear Search คือ baseline ที่ชัดที่สุด

8) Time Complexity ของ Array

Access by index

O(1)

รู้ตำแหน่งแล้วเข้าถึงได้ทันที

Update by index

O(1)

เขียนทับตำแหน่งเดิม

Traversal

O(n)

ต้องอ่านข้อมูลทีละสมาชิก

Search (unsorted)

O(n)

ไล่ตรวจจนเจอหรือครบทุกตัว

Insert/Delete end

O(1) amortized

โดยทั่วไปเร็ว แต่บางครั้งมีค่าขยายความจุ

Insert/Delete middle

O(n)

มีต้นทุน shift ข้อมูล

หมายเหตุเรื่อง amortized ของ `push`

9) Static Array vs Dynamic Array

Static Array

ขนาดคงที่ตั้งแต่เริ่ม ใช้ได้ดีเมื่อรู้จำนวนข้อมูลล่วงหน้า

Tradeoff: หน่วยความจำคาดเดาง่าย แต่ยืดหยุ่นน้อย

ตัวอย่างภาษา: เช่น C/C++ array ขนาดตายตัว

Dynamic Array

ขยาย/ย่อขนาดได้ตามการใช้งานจริง

Tradeoff: ยืดหยุ่นสูง แต่ตอนขยายอาจมีต้นทุนคัดลอกข้อมูล

ตัวอย่างภาษา: เช่น JavaScript Array, Python list, Java ArrayList

Recap: static คาดเดาได้ง่าย, dynamic ยืดหยุ่นกว่าในงานแอปพลิเคชันทั่วไป

10) ข้อดีและข้อจำกัดของ Array

ข้อดี

เข้าถึงข้อมูลตาม index เร็ว (O(1))
โครงสร้างเรียบง่าย อ่านโค้ดง่าย
รองรับงานวนลูปและคำนวณเชิงสรุปได้ดี

ข้อจำกัด

เพิ่ม/ลบต้นหรือกลางมีต้นทุนสูงขึ้น (O(n))
ค้นหาในข้อมูลไม่เรียงลำดับยังเป็น O(n)
บางคำสั่ง mutate ข้อมูลเดิมจนเกิดบั๊กได้ง่าย

11) Multi-dimensional Array

2D ArrayTS

เหมาะกับโจทย์ตาราง, เกมกระดาน, แผนที่กริด

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];

const value = matrix[1][2]; // 6 (row 1, col 2)

Recap: 2D array คือการใช้ index หลายชั้น เช่น `matrix[row][col]`

12) เทคนิคพื้นฐานที่ใช้กับ Array

Two Pointers

ใช้กับ: เทียบหัว-ท้าย, ลบซ้ำ, ย้ายค่าตามเงื่อนไข

Rule: ใช้ pointer ซ้าย/ขวาเพื่อลดการวนซ้ำซ้อน

Prefix Sum

ใช้กับ: ตอบคำถามผลรวมช่วง [l, r] หลายครั้ง

Rule: เตรียมข้อมูลสะสมล่วงหน้า แล้วตอบ query เร็วขึ้น

Sliding Window

ใช้กับ: หาช่วงยาวสุด/สั้นสุดตามเงื่อนไข

Rule: ขยายและหดหน้าต่างแทนการเริ่มคำนวณใหม่ทุกครั้ง

Technique ExampleTS

เริ่มจาก pattern ที่สั้นและใช้ซ้ำได้หลายโจทย์

// Two pointers: palindrome
function isPalindrome(nums: number[]) {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    if (nums[left] !== nums[right]) return false;
    left += 1;
    right -= 1;
  }
  return true;
}

13) โจทย์ฝึก Array ระดับเริ่มต้น

Exercise 1: เขียน `getValueAtIndex(arr, index)`

โจทย์: คืนค่าที่ตำแหน่ง index และคืน undefined ถ้า index ไม่ถูกต้อง

Hint: ลองเช็กเงื่อนไข `index < 0` หรือ `index >= arr.length` ก่อนเข้าถึงค่า

Exercise 2: เขียน `sumArray(arr)`

โจทย์: คืนผลรวมของตัวเลขทั้งหมดในอาเรย์

Hint: เริ่ม `total = 0` แล้ววนลูปบวกค่าทีละตัว

Exercise 3: เขียน `insertAtIndex(arr, index, value)` แบบไม่แก้ต้นฉบับ

โจทย์: คืนอาเรย์ใหม่ที่แทรก value ในตำแหน่ง index

Hint: ใช้ `slice` แยกส่วนซ้าย/ขวา แล้วประกอบกลับด้วย spread

Exercise 4: เขียน `findFirstEvenIndex(arr)`

โจทย์: คืน index ของเลขคู่ตัวแรก ถ้าไม่เจอคืน -1

Hint: ใช้ลูป `for` และ `return` ทันทีเมื่อเจอเงื่อนไข

ฝึกต่อใน Session Lab

ใช้หน้า Lab เพื่อลงมือทำจริงและตรวจผลหลายเคสอัตโนมัติ

ไปหน้า Array Lab

14) ข้อผิดพลาดที่พบบ่อยในการใช้ Array

Off-by-one

ปัญหา: เขียนเงื่อนไขลูปผิด เช่น `i <= arr.length` ทำให้เกินขอบเขต

วิธีป้องกัน: จำแพตเทิร์นพื้นฐาน: `for (let i = 0; i < arr.length; i += 1)`

Index out of range

ปัญหา: เข้าถึงตำแหน่งติดลบหรือเกินขนาดโดยไม่ตรวจ

วิธีป้องกัน: ทำ guard clause ก่อนอ่านค่า โดยเฉพาะในฟังก์ชันที่รับ index จากภายนอก

Mutate โดยไม่ตั้งใจ

ปัญหา: ใช้ `sort`, `splice`, `reverse` แล้วกระทบข้อมูลต้นฉบับ

วิธีป้องกัน: ถ้าต้องการ immutable update ให้ copy ก่อน เช่น `const cloned = [...arr]`

ประเมิน Complexity ผิด

ปัญหา: คิดว่า `splice` หรือ `shift` เร็วเท่า `push` ในทุกกรณี

วิธีป้องกัน: จำว่า operation ที่ทำให้สมาชิกจำนวนมากขยับตำแหน่งมักเป็น O(n)

Recap ของทั้งบท

Data Structures & Algorithms

Array แบบเริ่มจากศูนย์: ครบพื้นฐานที่ต้องใช้จริง

1) Array คืออะไร

2) โครงสร้างการเก็บข้อมูลของ Array

3) Index และการเข้าถึงข้อมูล

4) การอ่านค่าและแก้ไขค่าใน Array

5) การวนลูปเพื่ออ่านข้อมูลใน Array

6) การเพิ่มและลบข้อมูลในตำแหน่งต่าง ๆ

7) การค้นหาข้อมูลใน Array

8) Time Complexity ของ Array

9) Static Array vs Dynamic Array

10) ข้อดีและข้อจำกัดของ Array

11) Multi-dimensional Array

12) เทคนิคพื้นฐานที่ใช้กับ Array

13) โจทย์ฝึก Array ระดับเริ่มต้น

14) ข้อผิดพลาดที่พบบ่อยในการใช้ Array

Loading

Data Structures & Algorithms

Array แบบเริ่มจากศูนย์: ครบพื้นฐานที่ต้องใช้จริง

1) Array คืออะไร

2) โครงสร้างการเก็บข้อมูลของ Array

3) Index และการเข้าถึงข้อมูล

4) การอ่านค่าและแก้ไขค่าใน Array

5) การวนลูปเพื่ออ่านข้อมูลใน Array

6) การเพิ่มและลบข้อมูลในตำแหน่งต่าง ๆ

7) การค้นหาข้อมูลใน Array

8) Time Complexity ของ Array

9) Static Array vs Dynamic Array

10) ข้อดีและข้อจำกัดของ Array

11) Multi-dimensional Array

12) เทคนิคพื้นฐานที่ใช้กับ Array

13) โจทย์ฝึก Array ระดับเริ่มต้น

14) ข้อผิดพลาดที่พบบ่อยในการใช้ Array