WikiDoubly Linked List

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field. The beginning and ending nodes’ previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders. [Wikipedia]

Here is my implementation for doubly linked list:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class DoublyLinkedList {
public:
    typedef struct _Node {
        int key;
        int value;
        _Node* prev;
        _Node* next;
    } Node;
    
    DoublyLinkedList();
    ~DoublyLinkedList();
    
    void add(Node* node); // the new node will be added right after the head.
    void remove(Node* node);
    Node* pop_tail(); // pop the last node.
    void move_to_head(Node* node); // move an existing node right after the head.
    
private:
    Node* head = nullptr;
    Node* tail = nullptr;
};

DoublyLinkedList::DoublyLinkedList() {
    head = new Node {-1, -1, nullptr, nullptr};
    tail = new Node {-1, -1, nullptr, nullptr};

    head->next = tail;
    tail->prev = head;
}

DoublyLinkedList::~DoublyLinkedList() {
    while (head) {
        auto tmp = head->next;
        delete head;
        head = tmp;
    }
}

void DoublyLinkedList::add(Node* node) {
    node->next = head->next;
    head->next->prev = node;
    head->next = node;
    node->prev = head;
}

void DoublyLinkedList::remove(Node *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    delete node;
}

DoublyLinkedList::Node* DoublyLinkedList::pop_tail() {
    auto node_pop = tail->prev;
    node_pop->prev->next = tail;
    tail->prev = node_pop->prev;
    return node_pop;
}

void DoublyLinkedList::move_to_head(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    
    add(node);
}

▲