双向环形链表的增删改查c++完整实现

Category： DSA

写在前面

最后写一下双向循环链表吧, 跟前面的没啥太大区别, 注意取余操作以及循环跳出的条件.

代码: GitHub;

节点类-链表类

节点类

和双向链表一模一样.

class ListNode {
public:
    int val;
    ListNode* prev; // 前驱结点
    ListNode* next; // 后继结点
    ListNode() : ListNode(0, nullptr, nullptr) {}
    ListNode(int x) : ListNode(x, nullptr, nullptr) {}
    ListNode(int x, ListNode* _next) : ListNode(x, nullptr, _next) {}

    // 委托构造
    ListNode(int x, ListNode* _prev, ListNode* _next)
        : val(x), prev(_prev), next(_next) {}
};

环形链表类

class RingDoubleLinkedList {
public:
    RingDoubleLinkedList() : head(nullptr) {}
    RingDoubleLinkedList(int head_val) : head(new ListNode(head_val)) {
        head->prev = head;
        head->next = head; // 一个节点成环
    }
    RingDoubleLinkedList(int head_val, vector<int> rest);
    RingDoubleLinkedList(vector<int> nodes);
    ~RingDoubleLinkedList();

    void print();
    ListNode* first();
    ListNode* last();
    int len();

    // visit by pos
    /* int& operator[](int pos); */
    ListNode* operator[](int pos);
    ListNode* visit(int pos);

    // insert by pos
    void insert(int pos, int val);
    void append(int val);

    // delete by pos
    void pop(int pos);
    void pop_front();

    // delete by value
    void remove(int val, int cnt = 1);           // delete val cnt times
    void modify(int val, int node, int cnt = 1); // modify val->node cnt times
    int find(int node);                          // not found:-1


private:
    ListNode* head;
};

构造函数-析构函数

RingDoubleLinkedList::RingDoubleLinkedList(int head_val, vector<int> rest) {
    head = new ListNode(head_val);
    auto cur = head;
    for (auto i : rest) {
        cur->next = new ListNode(i);
        cur->next->prev = cur;
        cur = cur->next;
    }
    cur->next = head;
    head->prev = cur;
}

RingDoubleLinkedList::RingDoubleLinkedList(vector<int> nodes) {
    if (nodes.empty()) return;
    head = new ListNode(nodes[0]);
    auto cur = head;
    for (auto i = nodes.begin() + 1; i != nodes.end(); i++) {
        cur->next = new ListNode(*i);
        cur->next->prev = cur;
        cur = cur->next;
    }
    cur->next = head;
    head->prev = cur;
}

RingDoubleLinkedList::~RingDoubleLinkedList() {
    if (head == nullptr) return;
    ListNode *dummy = new ListNode(0, head), *tmp;
    while (head->next != dummy->next) {
        tmp = head->next;
        cout << head->val << " ";
        delete head;
        head = tmp;
    }
    cout << head->val << " ";
    delete head;
    head = nullptr;
    cout << "deleted...\n";
    delete dummy;
}

辅助函数

输出格式化

ostream& operator<<(ostream& os, ListNode* lp) {
    if (lp == nullptr) return os << "∅" << endl;
    ListNode* cur = lp;

    auto num_len = [](int num) {
        size_t ans{};
        while (num) ++ans, num /= 10;
        return ans;
    };

    size_t show_len = 4 + num_len(cur->val);
    os << cur->val << " <=> ";
    while (cur->next != lp) {
        os << cur->next->val << " <=> ";
        show_len += num_len(cur->next->val) + 5;
        cur = cur->next;
    }
    os << "||"s << endl;
    os << R"(/\)" << string(show_len - 1, ' ') << "||"s << endl;
    os << "||" << string(show_len - 1, '=') << "||"s;
    return os << endl;
}

void RingDoubleLinkedList::print() { cout << head; }

链表长度

int RingDoubleLinkedList::len() {
    int size = 1;
    auto cur = head;
    while (cur->next != head) ++size, cur = cur->next;

    return size;
}

头尾结点

ListNode* RingDoubleLinkedList::first() { return head; }

ListNode* RingDoubleLinkedList::last() { return head->prev; }

遍历环形链表

ListNode* RingDoubleLinkedList::operator[](int pos) {
    if (head == nullptr)
        cout << "Attempt to get value from a NULL RingDoubleLinkedList\n";

    pos = pos < 0 ? pos % len() + len() : pos % len();

    auto cur = head;
    while (pos--) cur = cur->next;
    return cur;
}

ListNode* RingDoubleLinkedList::visit(int pos) { return this->operator[](pos); }

增加节点

指定位置添加

void RingDoubleLinkedList::insert(int pos, int val) {
    if (head == nullptr) {
        head = new ListNode(val);
        head->next = head;
        head->prev = head;
        return;
    }
    pos = pos < 0 ? pos % len() + len() : pos % len();
    if (pos == 0) { // change head
        auto cur = head;
        head = new ListNode(val, cur->prev, cur);
        cur->prev->next = head;
        cur->prev = head;
    } else {
        auto pre = visit(pos - 1);
        auto cur = pre->next;
        pre->next = new ListNode(val, pre, cur);
        cur->prev = pre->next;
    }
}

void RingDoubleLinkedList::append(int val) { insert(0, val); }

与单向环形链表一样, 这里还是存在一个问题, 当从head为空节点的状态添加(append)了一次节点, 然后再添加(append)第二个, 就会导致头结点发生变化.

删除节点

针对位置的删除

void RingDoubleLinkedList::pop(int pos) {
    if (head == nullptr) {
        cout << "Attempt to delete a NULL RingDoubleLinkedList!" << endl;
        return;
    }
    pos = pos < 0 ? pos % len() + len() : pos % len();
    if (len() == 1) {
        delete head;
        head = nullptr;
        return;
    }
    auto cur = head;
    while (--pos > 0) cur = cur->next; // 只判断 pos 不为零不行
    auto tmp = cur->next;              // 待删除节点
    cur->next = cur->next->next;
    cur->next->prev = cur;
    delete tmp;
}
void RingDoubleLinkedList::pop_front() { pop(0); }

针对值的删除

void RingDoubleLinkedList::remove(int val, int cnt) {
    int idx;
    do {
        if ((idx = find(val)) == -1) {
            cout << "can not find val " << val << " to delete\n";
            break;
        } else
            pop(idx);
    } while (--cnt);
}

cnt表示删除一个元素多少次

修改元素

// modify val->node cnt times
void RingDoubleLinkedList::modify(int val, int node, int cnt) {
    int idx;
    do {
        if ((idx = find(val)) == -1) {
            cout << "can not find val " << val << " to modify\n";
            break;
        } else {
            /* visit(idx)->val = node; */
            /* (*this)[idx]->val = node; */
            this->operator[](idx)->val = node;
        }
    } while (--cnt);
}

查找元素

int RingDoubleLinkedList::find(int node) {
    if (head == nullptr) return -1;
    if (head->val == node) return 0;
    auto cur = head;
    int pos{};
    while (cur->next != head) {
        if (cur->val == node) return pos;
        ++pos;
        cur = cur->next;
    }
    return -1;
}

主函数-测试

#include "Ring_Double_Linked_List.hpp"

// === test func === ===//
void test_ctor() {
    RingDoubleLinkedList ll1(12);
    ll1.print();

    RingDoubleLinkedList ll2(1, {2, 3, 4});
    ll2.print();

    RingDoubleLinkedList ll3({1, 2, 3, 4});
    ll3.print();
    /* 12 <=> || */
    /* /\     || */
    /* ||=====|| */
    /* 1 <=> 2 <=> 3 <=> 4 <=> || */
    /* /\                      || */
    /* ||======================|| */
    /* 1 <=> 2 <=> 3 <=> 4 <=> || */
    /* /\                      || */
    /* ||======================|| */
    /* 1 2 3 4 deleted... */
    /* 1 2 3 4 deleted... */
    /* 12 deleted... */
}

void test_fundamental() {
    RingDoubleLinkedList ll1({1, 2, 3, 4});
    cout << ll1.len() << endl;
    cout << ll1.first()->val << endl;
    cout << ll1.last()->val << endl;
    /* 4 */
    /* 1 */
    /* 4 */
    /* 1 2 3 4 deleted... */
}

void test_operator_at() {
    RingDoubleLinkedList ll1({1, 2, 3, 4});
    cout << ll1[-10]->val << endl;     // 3
    cout << ll1[0]->val << endl;       // 1
    cout << ll1[2]->val << endl;       // 3
    cout << ll1[9]->val << endl;       // 2
    cout << ll1.visit(9)->val << endl; // 2
}

void test_insert_1() {
    RingDoubleLinkedList ll1;
    ll1.append(20);
    ll1.append(30);
    ll1.insert(-1, 2);
    ll1.print();
    /* 30 <=> 2 <=> 20 <=> || */
    /* /\                  || */
    /* ||==================|| */
    /* 30 2 20 deleted... */
}

void test_insert_2() {
    RingDoubleLinkedList ll1({1, 2, 3, 4});
    ll1.insert(1, 2);
    ll1.print();
    /* 1 <=> 2 <=> 2 <=> 3 <=> 4 <=> || */
    /* /\                            || */
    /* ||============================|| */
    /* 1 2 2 3 4 deleted... */
}

void test_pop_1() {
    RingDoubleLinkedList ll1({1, 2, 3, 4});
    ll1.pop(1);
    ll1.pop(1);
    ll1.pop(1);
    /* ll1.pop(1); */
    ll1.pop_front();
    ll1.print(); // ∅
}

void test_find() {
    RingDoubleLinkedList ll1({1, 2, 3, 4});
    cout << ll1.find(1) << endl; // 0
    cout << ll1.find(3) << endl; // 2
    cout << ll1.find(5) << endl; //-1
}

void test_remove_modify() {
    RingDoubleLinkedList ll1({1, 1, 3, 4});
    ll1.modify(1, 23, 2);
    ll1.remove(23, 1);
    ll1.print();
    /* 23 <=> 3 <=> 4 <=> || */
    /* /\                 || */
    /* ||=================|| */
    /* 23 3 4 deleted... */
}


int main(int argc, char* argv[]) {
    /* test_ctor(); */
    /* test_fundamental(); */
    /* test_operator_at(); */
    /* test_insert_1(); */
    /* test_insert_2(); */
    /* test_pop_1(); */
    /* test_find(); */
    test_remove_modify();
    return 0;
}

小结

可以看出, 只有一些基本部分变了, 其他的函数实现都是与双向链表类似的, 并且写好了pop和insert函数之后, 其他的类似函数直接调用现有的成员函数就行, 还是很方便的.

上篇牛客网acm模式输入输出11道题目的c++解答(c标准io版)

下篇Linux下socket编程之unix Domain的c S示例