#include <iostream>
using namespace std;
template<typename T>
class DoubleLinkedList
{
struct Node
{
T value;
Node *prev;
Node *next;
Node(T val, Node *next = nullptr, Node *prev = nullptr) :
value(val), prev(prev), next(next) {}
};
Node *head;
Node *tail;
public:
DoubleLinkedList(Node *head = nullptr) : head(head) {
if (head == nullptr) {
tail = nullptr;
return;
}
Node *tmp;
for (tmp = head; tmp->next != nullptr; tmp = tmp->next);
tail = tmp;
}
void addfront(T val) {
Node *newnode = new Node(val, head);
if (head == nullptr) {
head = tail = newnode;
return;
}
newnode->next = head;
head->prev = newnode;
head = newnode;
}
void addend(T val) {
Node *newnode = new Node(val, nullptr, tail);
if (head == nullptr) {
head = tail = newnode;
return;
}
tail->next = newnode;
newnode->prev = tail;
tail = newnode;
}
void del(T val) {
for (Node *tmp = head; tmp != nullptr; tmp = tmp->next) {
if (tmp->value == val) {
if (tmp != head)
tmp->prev->next = tmp->next;
else
head = tmp->next;
if (tmp->next != nullptr)
tmp->next->prev = tmp->prev;
else
tail = tmp->prev;
// print();
delete tmp;
break;
}
}
}
void print()
{
for (Node *tmp = head; tmp != nullptr; tmp = tmp->next)
std::cout << tmp->value << ", ";
std::cout << "\n";
}
~DoubleLinkedList() {
Node *tmp, *next;
for (tmp = head; tmp != nullptr; tmp = tmp->next) {
next = tmp->next;
delete tmp;
}
}
};
int main()
{
DoubleLinkedList<int> numlist;
for (int i = 0; i < 10; i++)
numlist.addend(i);
numlist.print();
numlist.del(0);
numlist.print();
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdGVtcGxhdGU8dHlwZW5hbWUgVD4KY2xhc3MgRG91YmxlTGlua2VkTGlzdAp7CglzdHJ1Y3QgTm9kZQoJewogICAgCVQgdmFsdWU7CgkgICAgTm9kZSAqcHJldjsKICAgIAlOb2RlICpuZXh0OwoKCSAgICBOb2RlKFQgdmFsLCBOb2RlICpuZXh0ID0gbnVsbHB0ciwgTm9kZSAqcHJldiA9IG51bGxwdHIpIDogCiAgICAJCXZhbHVlKHZhbCksIHByZXYocHJldiksIG5leHQobmV4dCkge30KCX07CgogICAgTm9kZSAqaGVhZDsKICAgIE5vZGUgKnRhaWw7CnB1YmxpYzoKICAgIERvdWJsZUxpbmtlZExpc3QoTm9kZSAqaGVhZCA9IG51bGxwdHIpIDogaGVhZChoZWFkKSB7CiAgICAgICAgaWYgKGhlYWQgPT0gbnVsbHB0cikgewogICAgICAgICAgICB0YWlsID0gbnVsbHB0cjsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KICAgICAgICBOb2RlICp0bXA7CiAgICAgICAgZm9yICh0bXAgPSBoZWFkOyB0bXAtPm5leHQgIT0gbnVsbHB0cjsgdG1wID0gdG1wLT5uZXh0KTsKICAgICAgICB0YWlsID0gdG1wOwogICAgfQoKICAgIHZvaWQgYWRkZnJvbnQoVCB2YWwpIHsKICAgICAgICBOb2RlICpuZXdub2RlID0gbmV3IE5vZGUodmFsLCBoZWFkKTsKICAgICAgICBpZiAoaGVhZCA9PSBudWxscHRyKSB7CiAgICAgICAgICAgIGhlYWQgPSB0YWlsID0gbmV3bm9kZTsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KICAgICAgICBuZXdub2RlLT5uZXh0ID0gaGVhZDsKICAgICAgICBoZWFkLT5wcmV2ID0gbmV3bm9kZTsKICAgICAgICBoZWFkID0gbmV3bm9kZTsKICAgIH0KCiAgICB2b2lkIGFkZGVuZChUIHZhbCkgewogICAgICAgIE5vZGUgKm5ld25vZGUgPSBuZXcgTm9kZSh2YWwsIG51bGxwdHIsIHRhaWwpOyAKICAgICAgICBpZiAoaGVhZCA9PSBudWxscHRyKSB7CiAgICAgICAgICAgIGhlYWQgPSB0YWlsID0gbmV3bm9kZTsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KICAgICAgICB0YWlsLT5uZXh0ID0gbmV3bm9kZTsKICAgICAgICBuZXdub2RlLT5wcmV2ID0gdGFpbDsKICAgICAgICB0YWlsID0gbmV3bm9kZTsKICAgICAgICAKICAgIH0KCiAgICB2b2lkIGRlbChUIHZhbCkgewogICAgICAgIGZvciAoTm9kZSAqdG1wID0gaGVhZDsgdG1wICE9IG51bGxwdHI7IHRtcCA9IHRtcC0+bmV4dCkgewogICAgICAgICAgICBpZiAodG1wLT52YWx1ZSA9PSB2YWwpIHsKICAgICAgICAgICAgICAgIGlmICh0bXAgIT0gaGVhZCkKICAgICAgICAgICAgICAgICAgICB0bXAtPnByZXYtPm5leHQgPSB0bXAtPm5leHQ7CiAgICAgICAgICAgICAgICBlbHNlIAogICAgICAgICAgICAgICAgICAgIGhlYWQgPSB0bXAtPm5leHQ7CiAgICAgICAgICAgICAgICBpZiAodG1wLT5uZXh0ICE9IG51bGxwdHIpCiAgICAgICAgICAgICAgICAgICAgdG1wLT5uZXh0LT5wcmV2ID0gdG1wLT5wcmV2OwogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHRhaWwgPSB0bXAtPnByZXY7CiAgICAgICAgICAgICAgICAvLyBwcmludCgpOwogICAgICAgICAgICAgICAgZGVsZXRlIHRtcDsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIHZvaWQgcHJpbnQoKQogICAgewogICAgICAgIGZvciAoTm9kZSAqdG1wID0gaGVhZDsgdG1wICE9IG51bGxwdHI7IHRtcCA9IHRtcC0+bmV4dCkKICAgICAgICAgICAgc3RkOjpjb3V0IDw8IHRtcC0+dmFsdWUgPDwgIiwgIjsKICAgICAgICBzdGQ6OmNvdXQgPDwgIlxuIjsKICAgIH0KCiAgICB+RG91YmxlTGlua2VkTGlzdCgpIHsKICAgICAgICBOb2RlICp0bXAsICpuZXh0OwogICAgICAgIGZvciAodG1wID0gaGVhZDsgdG1wICE9IG51bGxwdHI7IHRtcCA9IHRtcC0+bmV4dCkgewogICAgICAgICAgICBuZXh0ID0gdG1wLT5uZXh0OwogICAgICAgICAgICBkZWxldGUgdG1wOwogICAgICAgIH0KICAgIH0KfTsKCmludCBtYWluKCkKewogICAgRG91YmxlTGlua2VkTGlzdDxpbnQ+IG51bWxpc3Q7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IDEwOyBpKyspCiAgICAgICAgbnVtbGlzdC5hZGRlbmQoaSk7CiAgICBudW1saXN0LnByaW50KCk7CiAgICBudW1saXN0LmRlbCgwKTsKICAgIG51bWxpc3QucHJpbnQoKTsKfQ==
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
1, 2, 3, 4, 5, 6, 7, 8, 9,