tags: C++ DSA LinkedList
写在前面
写一下双向链表的增删改查, 用C++实现.
完整代码可以看我的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 DoubleLinkedList {
public:
DoubleLinkedList() : head(nullptr) {}
DoubleLinkedList(int head_val) : head(new ListNode(head_val)) {}
DoubleLinkedList(int head_val, vector<int> rest);
DoubleLinkedList(vector<int> nodes);
~DoubleLinkedList();
void print();
ListNode* first();
ListNode* last();
int len();
ListNode* operator[](int pos);
ListNode* visit(int pos);
ListNode* rvisit(int pos);
void insert(int pos, int val);
void append(int val);
void add2head(int val);
void pop(int pos);
void pop_back();
void pop_front();
void remove(int val, int cnt = 1);
void modify(int val, int node, int cnt = 1);
int find(int node);
int rfind(int node);
private:
ListNode* head;
};
这里实现与之前写的单链表类似, 基本的增删改查肯定要有, 然后还有一个打印函数, (不然用重载的operator<<访问私有成员头结点不太好)
然后对于删除给出了基于位置的和基于值的两种实现, 直接调用已有的成员函数即可, 减少代码量.
然后是一个从右向左查找的rfind函数(事实上比较鸡肋, 需要先遍历到最后一个节点然后开始找).
还有一个重载的operator[], 以及visit函数, 用来基于位置找节点(指针).
一些辅助函数
双向链表格式化输出
ostream& operator<<(ostream& os, ListNode* lp) {
if (lp == nullptr) return os << "∅" << endl;
os << "∅ <== ";
ListNode* cur = lp;
while (cur != nullptr) {
os << cur->val << (cur->next ? " <=> " : " ==> ");
cur = cur->next;
}
os << "∅";
return os << endl;
}
采用连字字体看起来就很舒服.
void DoubleLinkedList::print() { cout << head; }
双向链表长度
int DoubleLinkedList::len() {
int size = 0;
auto cur = head;
while (cur) ++size, cur = cur->next;
return size;
}
头尾结点
ListNode* DoubleLinkedList::first() { return head; }
ListNode* DoubleLinkedList::last() {
auto cur = head;
while (cur->next) cur = cur->next;
return cur;
}
遍历(找节点指针)
ListNode* DoubleLinkedList::operator[](int pos) {
if (head == nullptr) {
cerr << "Attempt to get value from a NULL DoubleLinkedList\n";
exit(1);
}
if (pos > len() - 1 || pos < 0) {
cerr << "Wrong pos!\n";
exit(1);
}
auto cur = head;
while (pos--) cur = cur->next;
return cur;
}
ListNode* DoubleLinkedList::visit(int pos) { return this->operator[](pos); }
ListNode* DoubleLinkedList::rvisit(int rpos) {
if (head == nullptr) {
cerr << "Attempt to get value from a NULL DoubleLinkedList\n";
exit(1);
}
if (rpos > len() - 1 || rpos < 0) {
cerr << "Wrong rpos!\n";
exit(1);
}
auto cur = visit(len() - 1);
while (rpos--) cur = cur->prev;
return cur;
}
构造函数/析构函数
这里和单链表实现一样, 给出了三个构造函数, 一个通过初值列实现, 另外两个直接读取vector, 还是比较方便的.
DoubleLinkedList::DoubleLinkedList(int head_val, vector<int> rest) {
head = new ListNode(head_val);
ListNode *cur = head, *nxt = nullptr;
for (auto i : rest) {
nxt = new ListNode(i);
cur->next = nxt;
nxt->prev = cur;
cur = cur->next;
}
}
DoubleLinkedList::DoubleLinkedList(vector<int> nodes) {
if (nodes.empty()) {
cout << "Empty Data Source!\n";
return;
}
head = new ListNode(nodes[0]);
auto cur = head;
for (auto i = nodes.begin() + 1; i < nodes.end(); i++) {
auto nxt = new ListNode(*i);
cur->next = nxt;
nxt->prev = cur;
cur = cur->next;
}
}
DoubleLinkedList::~DoubleLinkedList() {
ListNode* cur;
while (head->next) {
cur = head->next;
cout << head->val << " ";
delete head;
head = cur;
}
cout << head->val << " ";
delete head;
cout << "deleted...\n";
}
对于析构函数, 没什么好说的, 跟单链表一样, 主要说一下构造函数, 由于是双向链表, 那么就一定要注意prev指针.
一般来说, 每次添加一个新节点, 都要链接四根指针, 分别是前驱节点的next, 当前节点的prev和next, 后继结点的prev, 缺一不可.
添加节点
void DoubleLinkedList::insert(int pos, int val) {
if (pos >= len()) {
auto cur = last(), nxt = new ListNode(val);
cur->next = nxt;
nxt->prev = cur;
} else if (pos <= 0) {
auto cur = head;
head = new ListNode(val);
head->next = cur;
cur->prev = head;
} else {
auto pre = head;
while (--pos) pre = pre->next;
auto cur = pre->next;
pre->next = new ListNode(val, pre, cur);
}
}
void DoubleLinkedList::add2head(int val) { insert(0, val); }
void DoubleLinkedList::append(int val) { insert(len(), val); }
删除节点
void DoubleLinkedList::pop(int pos) {
if (head == nullptr) {
cout << "Attempt to delete a NULL DoubleLinkedList!" << endl;
} else if (head->next == nullptr) {
delete head;
head = nullptr;
} else {
if (pos >= len() - 1) {
auto cur = rvisit(1), tmp = cur->next;
delete tmp;
cur->next = nullptr;
} else if (pos <= 0) {
auto cur = head->next;
delete head;
head = cur;
} else {
auto cur = visit(pos - 1);
auto nxt = cur->next->next, tmp = cur->next;
cur->next = nxt;
delete tmp;
}
}
}
void DoubleLinkedList::pop_front() { pop(0); }
void DoubleLinkedList::pop_back() { pop(len()); }
void DoubleLinkedList::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);
}
修改节点
void DoubleLinkedList::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 {
(*this)[idx]->val = node;
}
} while (--cnt);
}
查找节点
int DoubleLinkedList::find(int node) {
if (head == nullptr) return -1;
auto cur = head;
int pos{};
while (cur) {
if (cur->val == node) return pos;
++pos;
cur = cur->next;
}
return -1;
}
int DoubleLinkedList::rfind(int node) {
auto cur = last();
if (cur == nullptr) return -1;
int pos{};
while (cur) {
if (cur->val == node) return pos;
++pos;
cur = cur->prev;
}
return -1;
}
主函数: 测试
#include "Double_Linked_List.hpp"
void test_ctor() {
DoubleLinkedList ll1(12);
ll1.print();
DoubleLinkedList ll2(1, {2, 3, 4});
ll2.print();
DoubleLinkedList ll3({1, 2, 3, 4});
ll3.print();
}
void test_fundamental() {
DoubleLinkedList ll1({1, 2, 3, 4});
cout << "ll1=";
ll1.print();
cout << "len(ll1)=" << ll1.len() << endl;
cout << "first: " << ll1.first()->val << endl;
cout << "last: " << ll1.last()->val << endl;
cout << "visit(1) : " << ll1.visit(1)->val << endl;
cout << "rvisit(1) : " << ll1.rvisit(1)->val << endl;
}
void test_insert() {
DoubleLinkedList ll1({1, 2, 3, 4});
ll1.print();
ll1.insert(0, 3);
ll1.insert(5, 3);
ll1.insert(2, 3);
ll1.print();
}
void test_pop() {
DoubleLinkedList ll1({0, 1, 2, 3, 4});
ll1.pop(12);
ll1.pop(-1);
ll1.pop(1);
ll1.print();
}
void test_find_pop() {
DoubleLinkedList ll1({1, 2, 3, 4});
ll1.append(5);
ll1.pop(0);
ll1.pop_back();
ll1.insert(4, 12);
ll1.add2head(9);
cout << "ll1.find(2):" << ll1.find(2) << endl;
cout << "ll1.rfind(12):" << ll1.rfind(12) << endl;
ll1.print();
}
void test_operator_at_modify() {
DoubleLinkedList ll1({1, 2, 3, 4});
ll1.append(1);
ll1.remove(1, 3);
ll1.print();
cout << "ll1[0]=" << ll1[0]->val << endl;
ll1.add2head(1);
ll1.modify(1, 11, 3);
ll1.print();
}
int main(int argc, char* argv[]) {
test_fundamental();
return 0;
}
小结
会了单链表, 双向链表也就会了, 注意指针的删除释放内存等操作即可, 都是细节.
如果有什么问题欢迎评论区留言.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
