Fundamental of Data Structures
โครงสร้างข้อมูลพื้นฐานและการประยุกต์

2 การใช้งานคลาส Arrays, อาร์เรย์แบบยืดหยุ่น และฟังก์ชันเรียกตัวเอง

1. Array พื้นฐานใน Java

// Declaration & Initialization
int[] arr = new int[5];         // [0,0,0,0,0] (default 0)
int[] arr2 = {10, 20, 30};     // shorthand initialization

// Access: O(1) - ความลับคือ memory contiguous
int x = arr2[1];  // 20

// 2D Array
int[][] matrix = new int[3][4]; // 3 rows, 4 cols
matrix[0][0] = 1;

// Arrays utility class
import java.util.Arrays;
Arrays.sort(arr2);           // เรียง ascending
Arrays.fill(arr, 99);        // ใส่ค่า 99 ทุก element
System.out.println(Arrays.toString(arr2)); // "[10, 20, 30]"
int idx = Arrays.binarySearch(arr2, 20); // หาด้วย Binary Search (ต้องเรียงก่อน)

2. Dynamic Array (ArrayList)

Array ธรรมดามีขนาดคงที่ — Dynamic Array แก้ปัญหานี้ด้วยการ "ขยายตัวเอง" เมื่อเต็ม:

class DynamicArray {
    private int[] data;
    private int size;     // จำนวน element จริง
    private int capacity; // ขนาดของ array ที่จอง

    public DynamicArray(int initialCap) {
        capacity = initialCap;
        data = new int[capacity];
        size = 0;
    }

    public void add(int value) {
        if (size == capacity) {
            grow(); // ขยายก่อน!
        }
        data[size++] = value;
    }

    private void grow() {
        capacity *= 2; // ขยายเป็น 2 เท่า (Amortized O(1))
        int[] newData = new int[capacity];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
        System.out.println("Grew to capacity: " + capacity);
    }

    public int get(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        return data[index];
    }
    
    public int size() { return size; }
}

3. Recursion — ฟังก์ชันเรียกตัวเอง

ทุก Recursive function ต้องมี 2 ส่วน:

• 🛑 Base Case — เงื่อนไขหยุด (ป้องกัน infinite loop → StackOverflow)
• 🔄 Recursive Step — เรียกตัวเองด้วยปัญหาที่เล็กลง

// Factorial: n! = n × (n-1)!
public static long factorial(int n) {
    if (n <= 1) return 1;            // Base Case
    return n * factorial(n - 1);    // Recursive Step
}
// factorial(4) = 4 × factorial(3) = 4 × 3 × 2 × 1 = 24

// Fibonacci: fib(n) = fib(n-1) + fib(n-2)
public static int fib(int n) {
    if (n <= 1) return n;             // Base Case: fib(0)=0, fib(1)=1
    return fib(n-1) + fib(n-2);      // Recursive Step (O(2^n) -- ช้า!)
}

// String Reverse
public static String reverse(String s) {
    if (s.isEmpty()) return s;        // Base Case
    return reverse(s.substring(1)) + s.charAt(0); // Recursive Step
}
// reverse("ABC") = reverse("BC") + 'A' = "CBA"

public static int sum(int n) {
    if (n <= 0) return 0;        // Base Case
    return n + sum(n - 1);       // Recursive Step
}

// ผิด! ไม่มี Base Case
public static int bad(int n) {
    return n + bad(n - 1); // เรียกไม่หยุด → StackOverflow!
}

// ถูก
public static int good(int n) {
    if (n <= 0) return 0; // Base Case ต้องมี!
    return n + good(n - 1);
}

3 โครงสร้างข้อมูล Singly Linked List (รายการเชื่อมโยงเดี่ยว)

1. โครงสร้างและการจัดสรรหน่วยความจำแรม (Memory Layout vs Array)

พวกเรามาดูก่อนครับว่า **Singly Linked List** แตกต่างจาก **Array** อย่างไรในหน่วยความจำแรม:

• Array (หน่วยความจำต่อเนื่อง): จองพื้นที่บล็อกแรมติดกันเป็นพืด ข้อดีคือคำนวณตำแหน่งได้ทันทีทำให้เข้าถึงดัชนีใดๆ ได้เร็ว O(1) (เรียกว่า Random Access) แต่ข้อเสียคือต้องระบุขนาดล่วงหน้า และขยายขนาดไม่ได้ง่ายๆ
• Linked List (หน่วยความจำกระจัดกระจาย): โหนดของลิงก์ลิสต์แต่ละโหนดสามารถสร้างกระจัดกระจายอยู่ที่ใดก็ได้ในแรมกองส่วน Heap โดยแต่ละโหนดจะเชื่อมต่อกันด้วย **พอยน์เตอร์ตัวชี้ (Reference pointer)** ชี้ตามกันไปทีละตัว ทำให้ขยายขนาดได้ยืดหยุ่นไม่มีข้อจำกัด

โครงสร้างของโหนด (Node Structure):

ประกอบด้วย 2 ส่วนหลักคือ:

1. Data (ส่วนข้อมูล): เก็บข้อมูลวัตถุ เช่น วัตถุ Student, ตัวเลข, หรือตัวอักษร
2. Next (ส่วนตัวชี้): เป็นพอยน์เตอร์อ้างอิงตำแหน่งแรมที่เก็บตัวแปรชี้ไปยัง **โหนดตัวถัดไป** ในรายการ โดยโหนดสุดท้ายสุดของลิสต์ ตัวชี้ Next จะเก็บค่าว่างเปล่าเป็น `null`

2. ตารางเปรียบเทียบประสิทธิภาพเชิงเวลา (Time Complexity Comparison)

3. อัลกอริทึมการจัดการโหนด (Linked List Algorithms)

• การเพิ่มข้อมูลที่หัว (Prepend): สร้างโหนดใหม่ ➜ ชี้โหนดใหม่ไปที่ head ปัจจุบัน ➜ อัปเดต head ให้ชี้มาที่โหนดใหม่ (ทำงานในเวลาคงที่ O(1))
• การเพิ่มข้อมูลที่ท้าย (Append): สร้างโหนดใหม่ ➜ วนลูปตรวจสอบจากหัวไปเรื่อยๆ จนเจอโหนดที่ next == null (โหนดท้ายสุด) ➜ ชี้ Next ของโหนดท้ายนั้นมาที่โหนดใหม่
• การลบโหนดใดๆ (Delete Node): ค้นหาโหนดเป้าหมายโดยถือพอยน์เตอร์ตัวก่อนหน้า (Previous Node) ➜ สั่งเปลี่ยนตัวชี้ Next ของตัวก่อนหน้าให้ข้ามข้ามไปชี้โหนดถัดไปของตัวที่ต้องการลบ (โหนดเป้าหมายจะหลุดการเชื่อมต่อและโดน Garbage Collector เคลียร์แรมทิ้งอัตโนมัติ)

🏋️ โจทย์ซ้อมการไล่พอยน์เตอร์ (Conceptual Practice)

ลองมาไล่ทิศทางชี้ของพอยน์เตอร์ในแรมผ่านโจทย์วิเคราะห์สถานการณ์เพื่อสอบทฤษฎีกันครับ:

curr.next = curr.next.next;  // A.next = B.next (ซึ่งชี้ไปที่ C)

if (head == null) return; // ดักตรวจลิสต์ว่างเปล่า
head = head.next;         // เลื่อนตำแหน่งหัว (ถ้ามีโหนดเดียวก็จะชี้ไป null ถูกต้อง)

4 ลิงก์ลิสต์สองทิศทางและโครงสร้างสแตก (Doubly Linked List & Stack ADT)

1. Doubly Linked List (DLL)

แต่ละ Node มี 3 ส่วน: prev pointer, data, และ next pointer

null ← [prev|10|next] ↔ [prev|20|next] ↔ [prev|30|next] → null
         head                                       tail

2. DLL vs Singly Linked List

class DNode {
    int data;
    DNode prev, next;
    DNode(int data) { this.data = data; }
}

class DoublyLinkedList {
    DNode head, tail;

    // O(1) — เพิ่มหน้า
    public void addFirst(int data) {
        DNode newNode = new DNode(data);
        if (head == null) { head = tail = newNode; return; }
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }

    // O(1) — ลบท้าย (DLL ทำได้ LL เดี่ยวทำไม่ได้ O(1))
    public void removeLast() {
        if (tail == null) return;
        if (head == tail) { head = tail = null; return; }
        tail = tail.prev;
        tail.next = null;
    }
}

3. Stack ADT (Abstract Data Type)

Stack คือโครงสร้างข้อมูล LIFO (Last In, First Out) — อันสุดท้ายที่เข้าคืออันแรกที่ออก

4. การประยุกต์ใช้ Stack: Infix → Postfix

Infix: A + B * C → Postfix: ABC*+ (ไม่ต้องใช้วงเล็บ!)

/* Algorithm สำหรับ Infix → Postfix:
   1. อ่านสัญลักษณ์ทีละตัว
   2. ถ้าเป็น operand (ตัวเลข/ตัวอักษร) → output ทันที
   3. ถ้าเป็น '(' → push ลง stack
   4. ถ้าเป็น ')' → pop จนเจอ '(' แล้ว discard '('
   5. ถ้าเป็น operator → pop operator ที่ priority >= ตัวเอง แล้ว push ตัวเอง
   6. เมื่ออ่านหมดแล้ว → pop ทุกอันที่เหลือใน stack
*/

// ตัวอย่าง: "A+B*C"
// อ่าน A → output: A
// อ่าน + → push: [+]
// อ่าน B → output: AB
// อ่าน * → * > + → push: [+,*]
// อ่าน C → output: ABC
// หมด → pop * แล้ว + → output: ABC*+

// ลบ node N ใน DLL (O(1)):
N.prev.next = N.next;   // ข้าม N ไปข้างหน้า
N.next.prev = N.prev;   // ข้าม N ไปข้างหลัง
// N จะถูก GC เก็บ

5 โครงสร้างข้อมูลคิวแบบวงกลมและตัวจัดเก็บ (Queue ADT & Circular Queue)

1. Queue ADT (First In, First Out)

Queue = คิวต่อแถว — คนที่มาก่อนได้รับบริการก่อน

2. ปัญหาของ Linear Queue กับ Array

// Linear Queue ปัญหา: "False Full"
// [_][_][_][10][20] → dequeue 2 ครั้ง → [_][_][_][_][20]
// front=4, rear=4 ดูเหมือนเต็มแต่มีช่องว่างหน้า!
//                                         ↑front

// แก้ด้วย Circular Queue: ใช้ index แบบ modulo %

3. Circular Queue (แก้ปัญหา False Full)

class CircularQueue {
    int[] data;
    int front, rear, size, capacity;
    
    CircularQueue(int capacity) {
        this.capacity = capacity;
        data = new int[capacity];
        front = rear = size = 0;
    }
    
    // เต็มหรือว่าง?
    boolean isFull()  { return size == capacity; }
    boolean isEmpty() { return size == 0; }
    
    // ใส่ที่ท้าย
    void enqueue(int val) {
        if (isFull()) throw new RuntimeException("Queue Full!");
        data[rear] = val;
        rear = (rear + 1) % capacity;  // ← กุญแจสำคัญ! Wrap around
        size++;
    }
    
    // เอาออกจากหน้า
    int dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue Empty!");
        int val = data[front];
        front = (front + 1) % capacity;  // ← Wrap around
        size--;
        return val;
    }
}

6 คิวจัดลำดับความสำคัญและโครงสร้างโครงต้นไม้ฮีป (Priority Queue & Heaps)

1. Priority Queue ADT

Priority Queue คือ Queue ที่ให้บริการตาม Priority (ลำดับความสำคัญ) ไม่ใช่ลำดับการมาถึง

• Min-Priority Queue — element ที่มี priority น้อยสุดออกก่อน
• Max-Priority Queue — element ที่มี priority มากสุดออกก่อน

2. Binary Heap

Heap คือ Complete Binary Tree ที่มี Heap-Order Property:

• Max-Heap: Parent ≥ Children ทุก node
• Min-Heap: Parent ≤ Children ทุก node
• Shape Property: เติม node จากซ้ายไปขวาในแต่ละ level (Complete Binary Tree)

3. Array Representation (สำคัญมาก!)

เก็บ Heap เป็น Array โดยไม่ต้องใช้ pointer!

       90          ← index 0
      /   \
    75     80       ← index 1, 2
   /  \   /
  40  60 70        ← index 3, 4, 5

Array: [90, 75, 80, 40, 60, 70]
Index:   0   1   2   3   4   5

สูตร (สำคัญ!):
- Left child ของ i  → index 2i + 1
- Right child ของ i → index 2i + 2
- Parent ของ i      → index (i - 1) / 2  (integer division)

4. Heap Operations

// Heapify-Up (bubble-up): หลัง insert
// ใส่ element ใหม่ที่ท้าย แล้ว swap กับ parent ถ้า > parent (Max-Heap)
void heapifyUp(int[] heap, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] > heap[parent]) {   // Max-Heap condition
            swap(heap, i, parent);
            i = parent;
        } else break;
    }
}

// Heapify-Down (sift-down): หลัง extractMax
// เอา root ออก ใส่ tail ที่ root แล้ว swap กับ child ที่ใหญ่กว่า
void heapifyDown(int[] heap, int i, int size) {
    while (2*i + 1 < size) {           // มี left child
        int largest = i;
        int left = 2*i + 1, right = 2*i + 2;
        if (left < size && heap[left] > heap[largest])   largest = left;
        if (right < size && heap[right] > heap[largest]) largest = right;
        if (largest == i) break;       // ถูกที่แล้ว
        swap(heap, i, largest);
        i = largest;
    }
}