链表

英文: Linked List.

一种链式的存储结构, 因此存储单元不一定是连续的. 链表可分为三类:

• 单向链表.
• 双向链表.
• 环形链表.

实现

template <typename T>
class Linked {
private:
    struct Node {
        T     value;
        Node* next = nullptr;
    };

public:
    using value_type = T;

    ~Linked() { clear(); }

    void insert(const value_type& value) {
        auto node = new Node();
        node->value = value;
        node->next = head_;
        head_ = node;
    }

    void remove(std::size_t pos) {
        if(pos == 0 && head_) {
            delete head_;
            head_ = nullptr;
            return;
        }
        auto prev = head_;
        for(std::size_t i = 0; i < pos - 1; i++)
            prev = prev->next;
        const auto node = prev->next;
        prev->next = node->next;
        delete node;
    }

    void clear() {
        auto curr = head_;
        while(curr) {
            const auto node = curr;
            curr = curr->next;
            delete node;
        }
    }

    bool empty() const noexcept { return size() == 0; }

    std::size_t size() const noexcept {
        std::size_t size = 0;
        auto curr = head_;
        while(curr) {
            size++;
            curr = curr->next;
        }
        return size;
    }

private:
    Node* head_ = nullptr;
};

评论