Khóa học C++

Appearance

List - Danh sách liên kết đôi ​

📖 Giới thiệu ​

List là container dựa trên danh sách liên kết đôi (doubly linked list). Không như vector, list không cung cấp truy cập ngẫu nhiên nhưng cho phép chèn/xóa hiệu quả ở bất kỳ vị trí nào.

Ví dụ đơn giản đầu tiên ​

cpp
#include <iostream>
#include <list>
using namespace std;

int main() {
    // Tạo list
    list<int> numbers = {10, 20, 30};
    
    // Thêm phần tử
    numbers.push_front(5);   // Thêm đầu
    numbers.push_back(40);   // Thêm cuối
    
    // Hiển thị
    cout << "List: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    // Xóa phần tử
    numbers.pop_front();     // Xóa đầu
    numbers.pop_back();      // Xóa cuối
    
    cout << "Sau khi xóa: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

🔧 Cú pháp ​

Khai báo List ​

cpp
#include <list>

list<int> empty_list;                    // List rỗng
list<int> sized_list(5);                // 5 phần tử mặc định
list<int> init_list(5, 10);             // 5 phần tử, giá trị 10
list<int> copy_list{1, 2, 3, 4, 5};     // Khởi tạo với list

Các phương thức cơ bản ​

cpp
// Thêm/xóa
list.push_front(value);     // Thêm đầu
list.push_back(value);      // Thêm cuối
list.pop_front();           // Xóa đầu
list.pop_back();            // Xóa cuối
list.insert(iterator, value); // Chèn tại vị trí
list.erase(iterator);       // Xóa tại vị trí

// Truy cập
list.front();               // Phần tử đầu
list.back();                // Phần tử cuối

// Thông tin
list.size();                // Số phần tử
list.empty();               // Kiểm tra rỗng
list.clear();               // Xóa tất cả

// Đặc biệt
list.sort();                // Sắp xếp
list.reverse();             // Đảo ngược
list.unique();              // Xóa phần tử trùng lặp liên tiếp
list.merge(other_list);     // Hợp nhất hai list đã sắp xếp

💻 Ví dụ minh họa ​

Ví dụ 1: Hệ thống quản lý playlist nhạc ​

cpp
#include <iostream>
#include <list>
#include <string>
#include <algorithm>
using namespace std;

struct BaiHat {
    string ten;
    string ca_si;
    int thoi_luong; // giây
    
    BaiHat(string t, string cs, int tl) : ten(t), ca_si(cs), thoi_luong(tl) {}
    
    void hien_thi() const {
        int phut = thoi_luong / 60;
        int giay = thoi_luong % 60;
        cout << "♪ " << ten << " - " << ca_si << " [" << phut << ":" 
             << (giay < 10 ? "0" : "") << giay << "]" << endl;
    }
    
    string dinh_dang_thoi_gian() const {
        int phut = thoi_luong / 60;
        int giay = thoi_luong % 60;
        return to_string(phut) + ":" + (giay < 10 ? "0" : "") + to_string(giay);
    }
};

class MusicPlayer {
private:
    list<BaiHat> playlist;
    list<BaiHat>::iterator current_song;
    bool dang_phat;
    
public:
    MusicPlayer() : dang_phat(false) {
        cout << "🎵 Khởi tạo Music Player" << endl;
    }
    
    void them_bai_hat(const string& ten, const string& ca_si, int thoi_luong) {
        playlist.emplace_back(ten, ca_si, thoi_luong);
        cout << "✅ Đã thêm: " << ten << " - " << ca_si << endl;
        
        if (playlist.size() == 1) {
            current_song = playlist.begin();
        }
    }
    
    void them_bai_hat_dau(const string& ten, const string& ca_si, int thoi_luong) {
        playlist.emplace_front(ten, ca_si, thoi_luong);
        current_song = playlist.begin();
        cout << "⬆️ Đã thêm vào đầu danh sách: " << ten << endl;
    }
    
    void xoa_bai_hat(const string& ten) {
        auto it = find_if(playlist.begin(), playlist.end(),
                         [&ten](const BaiHat& bh) { return bh.ten == ten; });
        
        if (it != playlist.end()) {
            bool is_current = (it == current_song);
            playlist.erase(it);
            cout << "🗑️ Đã xóa: " << ten << endl;
            
            if (is_current && !playlist.empty()) {
                current_song = playlist.begin();
            }
        } else {
            cout << "❌ Không tìm thấy bài hát: " << ten << endl;
        }
    }
    
    void phat_nhac() {
        if (playlist.empty()) {
            cout << "❌ Playlist trống!" << endl;
            return;
        }
        
        dang_phat = true;
        cout << "▶️ Đang phát: ";
        current_song->hien_thi();
    }
    
    void dung_nhac() {
        dang_phat = false;
        cout << "⏸️ Đã dừng phát nhạc" << endl;
    }
    
    void bai_tiep_theo() {
        if (playlist.empty()) {
            cout << "❌ Playlist trống!" << endl;
            return;
        }
        
        ++current_song;
        if (current_song == playlist.end()) {
            current_song = playlist.begin(); // Quay lại đầu
            cout << "🔄 Quay lại đầu playlist" << endl;
        }
        
        if (dang_phat) {
            cout << "⏭️ Chuyển bài: ";
            current_song->hien_thi();
        }
    }
    
    void bai_truoc() {
        if (playlist.empty()) {
            cout << "❌ Playlist trống!" << endl;
            return;
        }
        
        if (current_song == playlist.begin()) {
            current_song = prev(playlist.end()); // Đến cuối
            cout << "🔄 Chuyển đến cuối playlist" << endl;
        } else {
            --current_song;
        }
        
        if (dang_phat) {
            cout << "⏮️ Bài trước: ";
            current_song->hien_thi();
        }
    }
    
    void xao_tron() {
        if (playlist.size() < 2) return;
        
        vector<BaiHat> temp(playlist.begin(), playlist.end());
        random_shuffle(temp.begin(), temp.end());
        
        playlist.clear();
        for (const auto& bh : temp) {
            playlist.push_back(bh);
        }
        
        current_song = playlist.begin();
        cout << "🔀 Đã xáo trộn playlist" << endl;
    }
    
    void sap_xep_theo_ten() {
        playlist.sort([](const BaiHat& a, const BaiHat& b) {
            return a.ten < b.ten;
        });
        current_song = playlist.begin();
        cout << "📝 Đã sắp xếp theo tên bài hát" << endl;
    }
    
    void sap_xep_theo_ca_si() {
        playlist.sort([](const BaiHat& a, const BaiHat& b) {
            return a.ca_si < b.ca_si;
        });
        current_song = playlist.begin();
        cout << "👤 Đã sắp xếp theo ca sĩ" << endl;
    }
    
    void sap_xep_theo_thoi_luong() {
        playlist.sort([](const BaiHat& a, const BaiHat& b) {
            return a.thoi_luong < b.thoi_luong;
        });
        current_song = playlist.begin();
        cout << "⏱️ Đã sắp xếp theo thời lượng" << endl;
    }
    
    void hien_thi_playlist() {
        if (playlist.empty()) {
            cout << "📋 Playlist trống!" << endl;
            return;
        }
        
        cout << "\n🎵 PLAYLIST (" << playlist.size() << " bài)" << endl;
        cout << string(50, '-') << endl;
        
        int index = 1;
        for (auto it = playlist.begin(); it != playlist.end(); ++it, ++index) {
            cout << index << ". ";
            if (it == current_song) {
                cout << "➤ ";
            } else {
                cout << "  ";
            }
            it->hien_thi();
        }
        cout << string(50, '-') << endl;
    }
    
    void thong_tin_hien_tai() {
        if (playlist.empty()) {
            cout << "❌ Playlist trống!" << endl;
            return;
        }
        
        cout << "\n🎧 ĐANG PHÁT:" << endl;
        cout << "Trạng thái: " << (dang_phat ? "▶️ Đang phát" : "⏸️ Đã dừng") << endl;
        cout << "Bài hiện tại: ";
        current_song->hien_thi();
    }
    
    void thong_ke() {
        if (playlist.empty()) {
            cout << "📊 Không có dữ liệu!" << endl;
            return;
        }
        
        int tong_thoi_luong = 0;
        for (const auto& bh : playlist) {
            tong_thoi_luong += bh.thoi_luong;
        }
        
        int gio = tong_thoi_luong / 3600;
        int phut = (tong_thoi_luong % 3600) / 60;
        int giay = tong_thoi_luong % 60;
        
        cout << "\n📊 THỐNG KÊ PLAYLIST" << endl;
        cout << "Số bài hát: " << playlist.size() << endl;
        cout << "Tổng thời lượng: " << gio << "h " << phut << "m " << giay << "s" << endl;
        cout << "Thời lượng trung bình: " << (tong_thoi_luong / playlist.size()) << " giây" << endl;
    }
    
    list<BaiHat> tim_theo_ca_si(const string& ca_si) {
        list<BaiHat> ket_qua;
        
        copy_if(playlist.begin(), playlist.end(), back_inserter(ket_qua),
                [&ca_si](const BaiHat& bh) {
                    return bh.ca_si.find(ca_si) != string::npos;
                });
        
        cout << "🔍 Tìm thấy " << ket_qua.size() << " bài của " << ca_si << endl;
        return ket_qua;
    }
};

int main() {
    cout << "=== MUSIC PLAYER APPLICATION ===" << endl;
    
    MusicPlayer player;
    
    // Thêm nhạc vào playlist
    cout << "\n--- Thêm bài hát ---" << endl;
    player.them_bai_hat("Shape of You", "Ed Sheeran", 234);
    player.them_bai_hat("Blinding Lights", "The Weeknd", 201);
    player.them_bai_hat("Watermelon Sugar", "Harry Styles", 174);
    player.them_bai_hat("Don't Start Now", "Dua Lipa", 183);
    player.them_bai_hat("Perfect", "Ed Sheeran", 263);
    
    // Hiển thị playlist
    player.hien_thi_playlist();
    
    // Test phát nhạc
    cout << "\n--- Test phát nhạc ---" << endl;
    player.phat_nhac();
    player.thong_tin_hien_tai();
    
    // Chuyển bài
    cout << "\n--- Chuyển bài ---" << endl;
    player.bai_tiep_theo();
    player.bai_tiep_theo();
    player.bai_truoc();
    
    // Sắp xếp
    cout << "\n--- Sắp xếp ---" << endl;
    player.sap_xep_theo_ca_si();
    player.hien_thi_playlist();
    
    // Tìm kiếm
    cout << "\n--- Tìm kiếm ---" << endl;
    auto bai_ed_sheeran = player.tim_theo_ca_si("Ed Sheeran");
    
    // Thống kê
    player.thong_ke();
    
    // Test xóa và thêm đầu
    cout << "\n--- Thao tác nâng cao ---" << endl;
    player.them_bai_hat_dau("New Song", "New Artist", 180);
    player.hien_thi_playlist();
    
    player.xoa_bai_hat("Perfect");
    player.hien_thi_playlist();
    
    return 0;
}

🏋️ Thực hành ​

Bài tập 1: Undo/Redo System ​

Tạo class CommandHistory với list để:

  • Lưu trữ lịch sử commands
  • Undo: quay lại command trước
  • Redo: thực hiện lại command

Bài tập 2: Train Simulation ​

Tạo class Train với list cars:

  • Thêm/xóa toa tàu ở đầu/cuối
  • Di chuyển toa tàu giữa các vị trí
  • Tính tổng trọng lượng

Bài tập 3: Text Editor Buffer ​

Tạo class TextBuffer với list:

  • Chèn/xóa ký tự hiệu quả
  • Cursor navigation
  • Find/replace operations

📋 Tóm tắt ​

  1. List: Container dựa trên doubly linked list

  2. Ưu điểm:

    • Chèn/xóa O(1) ở bất kỳ vị trí nào (nếu có iterator)
    • Không invalidate iterators khi thêm/xóa
    • Bidirectional iteration
    • Splice operations hiệu quả

  3. Nhược điểm:

    • Không có random access
    • Memory overhead (con trỏ)
    • Cache performance kém hơn vector

  4. Khi nào dùng:

    • Thường xuyên chèn/xóa giữa
    • Không cần random access
    • Cần stable iterators

Bài tiếp theo: Stack - Tìm hiểu về LIFO data structure.

Khóa học C++ miễn phí

Copyright © 2024 zukahai