List ใน C++ STL: คู่มือการใช้งาน std::list ครบถ้วน

List ใน C++ คืออะไร?

std::list เป็น container ที่เก็บข้อมูลแบบลำดับ (sequential) จัดสรรหน่วยความจำแบบไม่ต่อเนื่อง (non-contiguous) เป็น **Doubly Linked List** รองรับการเพิ่ม/ลบจากทั้งสองปลาย และเดินได้ทั้ง 2 ทิศทาง

สำหรับ Singly Linked List ใช้ std::forward_list

ข้อดีของ List เทียบ Vector

• Insert/Delete ที่ตำแหน่งใดก็ได้เร็ว O(1) ถ้ามี iterator อยู่ที่ตำแหน่งนั้นแล้ว
• Iterator ไม่ถูกทำลาย (invalidate) เมื่อ insert/erase (ต่างจาก vector)

ข้อเสีย

• Random access ช้า O(n) - ไม่มี operator[] ต้องเดินจาก đầu/ท้าย
• Memory overhead มากกว่า (เก็บ pointer เพิ่ม)
• Cache locality แย่กว่า vector

ฟังก์ชันหลักของ std::list

เพิ่มข้อมูล

• push_front(val) - เพิ่มหน้าสุด
• push_back(val) - เพิ่มท้ายสุด
• insert(pos, count, val) - แทรกที่ iterator pos
• emplace_front(val), emplace_back(val), emplace(pos, val) - สร้าง object inplace

ลบข้อมูล

• pop_front(), pop_back()
• erase(pos), erase(first, last)
• remove(val) - ลบทุกตัวที่ == val
• remove_if(pred) - ลบตามเงื่อนไข predicate
• clear() - ลบทั้งหมด

เข้าถึงข้อมูล

• front(), back()
• size(), empty(), max_size()

Iterators

• begin(), end(), rbegin(), rend()
• cbegin(), cend(), crbegin(), crend() (const iterators)

การจัดเรียงและดำเนินการอื่นๆ

• reverse() - กลับลำดับ
• unique() - ลบ adjacent duplicates (ต้อง sort ก่อนถ้าอยากลบทุกตัวซ้ำ)
• sort() - เรียง (member function ไม่ใช่ std::sort)
• merge(other) - รวม 2 list ที่เรียงแล้ว
• splice(pos, other, ...) - ย้ายโหนดจาก list อื่นมา (O(1))
• swap(other) - สลับเนื้อหา
• resize(n, val)
• operator= - copy assignment

ตัวอย่างการใช้งาน

#include <bits/stdc++.h>
using namespace std;

int main() {
    list<int> lst = {3, 1, 4, 1, 5};
    
    lst.push_front(0);        // {0,3,1,4,1,5}
    lst.push_back(9);         // {0,3,1,4,1,5,9}
    lst.insert(next(lst.begin(), 2), 99); // {0,3,99,1,4,1,5,9}
    
    lst.remove(1);            // ลบทุก 1 → {0,3,99,4,5,9}
    lst.unique();             // ลบ adjacent dup (none here)
    lst.sort();               // {0,3,4,5,9,99}
    lst.reverse();            // {99,9,5,4,3,0}
    
    for (int x : lst) cout << x << " ";
    return 0;
}

สรุปเมื่อไหร่ควรใช้ list

• Insert/Delete บ่อยครั้งที่ตำแหน่งกลาง และมี iterator อยู่แล้ว
• ต้องการ splice/merge list บ่อย
• ไม่ต้องการ random access
• กรณีส่วนใหญ่ vector หรือ deque เร็วกว่าและเหมาะสมกว่า