C++ 雙向鏈表完整實現指南：從核心結構到核心操作

雙向鏈表資料結構

雙向鏈表在單向鏈表節點基礎上，增加一個指向前驅節點的指標：

struct Node {
    DataType _data;
    Node* _next;   // 指向後繼節點
    Node* _front;  // 指向前驅節點
};

雙向鏈表以空間換時間，支援雙向遍歷，但插入刪除需維護兩個指標，指標操作順序嚴格不可錯誤。

核心操作圖解

插入操作

刪除操作

C++ 完整實現程式碼

typedef int DataType;

class LinkList;
class Node {
    friend class LinkList;
    friend std::ostream& operator<<(std::ostream& os, Node& n);
public:
    Node(DataType x) : _data(x), _next(nullptr), _front(nullptr) {}
private:
    DataType _data;
    Node* _next;
    Node* _front;
};

std::ostream& operator<<(std::ostream& os, Node& n) {
    os << n._data;
    return os;
}

class LinkList {
    friend std::ostream& operator<<(std::ostream& os, LinkList& list);
public:
    LinkList() : _head(nullptr), _tail(nullptr) {}
    ~LinkList() {
        Node* cur = _head;
        while (cur) {
            Node* del = cur;
            cur = cur->_next;
            delete del;
        }
    }

    // 尾插
    void PushBack(DataType x) {
        Node* newNode = new Node(x);
        if (_tail) {
            _tail->_next = newNode;
            newNode->_front = _tail;
            _tail = newNode;
        } else {
            _head = _tail = newNode;
        }
    }

    // 尾刪
    void PopBack() {
        if (!_head && !_tail) {
            std::cout << "鏈表已空不可尾刪" << std::endl;
            return;
        }
        if (_head == _tail) {
            delete _head;
            _head = _tail = nullptr;
        } else {
            Node* tmp = _tail;
            _tail = _tail->_front;
            _tail->_next = nullptr;
            delete tmp;
        }
    }

    // 頭插
    void PushFront(DataType x) {
        Node* newNode = new Node(x);
        if (_head) {
            newNode->_next = _head;
            _head->_front = newNode;
            _head = newNode;
        } else {
            _head = _tail = newNode;
        }
    }

    // 頭刪
    void PopFront() {
        if (!_head && !_tail) {
            std::cout << "鏈表已空不可頭刪" << std::endl;
            return;
        }
        if (_head == _tail) {
            delete _head;
            _head = _tail = nullptr;
        } else {
            Node* del = _head;
            _head = _head->_next;
            _head->_front = nullptr;
            delete del;
        }
    }

    // 查找
    Node* FindNum(DataType x) {
        Node* cur = _head;
        while (cur) {
            if (cur->_data == x) return cur;
            cur = cur->_next;
        }
        return nullptr;
    }

    // 指定位置後插入
    void Insert(Node* pos, DataType x) {
        Node* newNode = new Node(x);
        if (pos->_next) {
            newNode->_front = pos;
            newNode->_next = pos->_next;
            pos->_next->_front = newNode;
            pos->_next = newNode;
        } else {
            pos->_next = newNode;
            newNode->_front = pos;
            _tail = newNode;
        }
    }

    // 指定位置前插入
    void Insert(int, Node* pos, DataType x) {
        Node* newNode = new Node(x);
        if (pos->_front) {
            newNode->_next = pos;
            pos->_front->_next = newNode;
            newNode->_front = pos->_front;
            pos->_front = newNode;
        } else {
            newNode->_next = pos;
            pos->_front = newNode;
            _head = newNode;
        }
    }

    // 刪除指定值節點
    void Remove(DataType& x) {
        Node* pos = FindNum(x);
        if (!pos) return;

        if (!pos->_front && pos->_next) {           // 刪除頭節點
            _head = pos->_next;
            _head->_front = nullptr;
        } else if (pos->_front && !pos->_next) {    // 刪除尾節點
            _tail = pos->_front;
            _tail->_next = nullptr;
        } else {                                    // 刪除中間節點
            pos->_front->_next = pos->_next;
            pos->_next->_front = pos->_front;
        }
        delete pos;
    }

    // 刪除所有指定值
    void RemoveAll(DataType& x) {
        Node* cur = _head;
        while (cur) {
            Node* next = cur->_next;
            if (cur->_data == x) Remove(x);
            cur = next;
        }
    }

    // 排序（氣泡排序）
    void Sort() {
        bool flag = true;
        Node* tail = nullptr;
        while (flag) {
            flag = false;
            for (Node* cur = _head; cur && cur->_next != tail; cur = cur->_next) {
                if (cur->_data > cur->_next->_data) {
                    std::swap(cur->_data, cur->_next->_data);
                    flag = true;
                }
            }
            tail = cur;
        }
    }

    // 刪除指定節點
    void Erase(Node* pos) {
        if (!pos) return;
        if (!pos->_front && pos->_next) {
            _head = pos->_next;
            _head->_front = nullptr;
        } else if (pos->_front && !pos->_next) {
            _tail = pos->_front;
            _tail->_next = nullptr;
        } else {
            pos->_front->_next = pos->_next;
            pos->_next->_front = pos->_front;
        }
        delete pos;
    }

    // 輸出運算子
    friend std::ostream& operator<<(std::ostream& os, LinkList& list) {
        for (Node* cur = list._head; cur; cur = cur->_next)
            os << *cur << " ";
        return os;
    }

private:
    Node* _head;
    Node* _tail;
};

實現心得與建議

若節點結構定義為 struct 而非 class，可避免大量 friend 宣告，更好地保持封裝性。實作時務必注意指標操作順序，建議配合圖解逐步驗證。