Home | Projects | Notes > Data Structures & Algorithms > Doubly-Linked Lists

Doubly-Linked Lists

Introduction

A doubly linked list is a linear data structure where each node contains a data value, a pointer to the next node, and a pointer to the previous node. This bidirectional linkage allows traversal in both forward and backward directions. It is particularly useful when two-way navigation or efficient deletion from both ends is required.

Pros:

• Bidirectional Traversal: Can move both forward and backward through the list.

• Efficient Insertions/Deletions: O(1) insertion or removal from both ends or given nodes (with pointer access).

• Flexible Memory Usage: Dynamically grows and shrinks at runtime.

Cons:

• Higher Memory Overhead: Each node stores two pointers (next and prev), doubling pointer storage compared to a singly linked list.

• More Complex Management: Insertions and deletions require careful pointer updates in both directions.

• Less Cache-Friendly: Like singly linked lists, nodes are non-contiguous in memory.

Compared to Singly-Linked Lists:

• Better: Easier to delete nodes from the middle, supports reverse traversal.

• Worse: Slightly more memory usage and pointer management complexity.

Implementation (C++)

Header (dlist.hpp)

46
1
//==============================================================================
2
// File     : doubly_linked_list.h
3
// Brief    : Interface for Doubly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : May 17, 2023
6
//==============================================================================
7

8
#ifndef DOUBLY_LINKED_LIST_H
9
#define DOUBLY_LINKED_LIST_H
10

11
// Class for list nodes
12
class Node
13
{
14
public:
15
    int value;
16
    Node *next;
17
    Node *prev;
18

19
    Node(int value);                    // Constructor
20
};
21

22
// Class for doubly-linked lists
23
class DoublyLinkedList
24
{
25
public:    
26
    // Public interface
27
    DoublyLinkedList(int value);        // Constructor
28
    void append(int value);             // Add a node at the end
29
    void prepend(int value);            // Add a node at the front
30
    bool insert(int index, int value);  // Insert a node into the given index position
31
    void deleteNode(int index);         // Delete a node with the given index position
32
    void deleteLast();                  // Delete the last node
33
    void deleteFirst();                 // Delete the first node
34
    Node* get(int index);               // Get the node value of the given index position
35
    bool set(int index, int value);     // Set the node value of the given index position
36
    void reverse();                     // Reverse the list
37
    void printList();                   // Print the list
38
    ~DoublyLinkedList();                // Destructor
39

40
private:
41
    Node *head;
42
    Node *tail;
43
    int length;
44
};
45

46
#endif  // DOUBLY_LINKED_LIST_H

Source (dlist.cpp)

316
1
//==============================================================================
2
// File     : doubly_linked_list.h
3
// Brief    : Implementation of Doubly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : May 17, 2023
6
//==============================================================================
7

8
#include <iostream>
9
#include <cstdlib>      // EXIT_FAILURE
10
#include "doubly_linked_list.h"
11

12
using namespace std;
13

14
//------------------------------------------------------------------------------
15
// Implementation of Node class interface
16
//------------------------------------------------------------------------------
17

18
// Constructor
19
Node::Node(int value)
20
{
21
    this->value = value;
22
    next = nullptr;
23
    prev = nullptr;
24
}
25

26
//------------------------------------------------------------------------------
27
// Implementation of DoublyLinkedList class interface
28
//------------------------------------------------------------------------------
29

30
// Constructor
31
// T = O(1)
32
DoublyLinkedList::DoublyLinkedList(int value)
33
{
34
    Node *newNode = new Node(value);
35
    head = newNode;
36
    tail = newNode;
37
    length = 1;
38
}
39

40
// Add a node at the end
41
// T = O(1)
42
void DoublyLinkedList::append(int value) 
43
{
44
    Node *newNode = new Node(value);
45

46
    // Insert a node into an empty list
47
    if (length == 0)    // (head == nullptr) or (tail == nullptr)
48
    {   
49
        head = newNode;
50
        tail = newNode;
51
    }   
52
    // Insert a node into a non-empty list
53
    else
54
    {   
55
        tail->next = newNode;
56
        newNode->prev = tail;
57
        tail = newNode;
58
    }   
59

60
    length++;
61
}
62

63
// Add a node at the front
64
// T = O(1)
65
void DoublyLinkedList::prepend(int value)
66
{
67
    Node *newNode = new Node(value);
68

69
    // Insert a node into an empty list
70
    if (length == 0)
71
    {
72
        head = newNode;
73
        tail = newNode;
74
    }
75
    // Insert a node into a non-empty list
76
    else
77
    {
78
        newNode->next = head;
79
        head->prev = newNode;
80
        head = newNode;
81
    }
82

83
    length++;
84
}
85

86
// Insert a node into the given index position
87
// T = O(n)
88
bool DoublyLinkedList::insert(int index, int value)
89
{
90
    // Validity check for index
91
    if (index < 0 || index > length)
92
        return false;
93

94
    // Insert a node at front (prepend)
95
    if (index == 0)
96
    {
97
        prepend(value);
98
        return true;
99
    }
100

101
    // Insert a node at the end (append)
102
    if (index == length)
103
    {
104
        append(value);
105
        return true;
106
    }
107

108
    // Insert a node somewhere in the middle
109
    Node *newNode = new Node(value);
110
    Node *before = get(index - 1);
111
    Node *after = before->next;
112
    newNode->prev = before;
113
    newNode->next = after;
114
    before->next = newNode;
115
    after->prev = newNode;
116

117
    length++;
118

119
    return true;
120
}
121

122
// Delete a node with the given index position
123
// T = O(n)
124
void DoublyLinkedList::deleteNode(int index)
125
{
126
    // Validity check for index
127
    if (index < 0 || index >= length)
128
        return;
129

130
    // Delete the first node
131
    if (index == 0)
132
        return deleteFirst();   // Available only when return types are the same
133

134
    // Delete the last node
135
    if (index == length - 1)
136
        return deleteLast();
137

138
    // Delete the node from somewhere in the middle
139
    Node *delNode = get(index);
140
    delNode->prev->next = delNode->next;
141
    delNode->next->prev = delNode->prev;
142
    delete delNode;
143

144
    length--;
145
}
146

147
// Delete the last node
148
// T = O(1)
149
void DoublyLinkedList::deleteLast()
150
{
151
    // Do not allow delete operation on an empty list
152
    if (length == 0)
153
    {
154
        cout << "ERROR: Cannot delete from an empty list. Terminating!" << endl;
155
        exit(EXIT_FAILURE);
156
    }
157

158
    Node *delNode = tail;
159

160
    // If only 1 node in the list
161
    if (length == 1)
162
    {
163
        head = nullptr;
164
        tail = nullptr;
165
    }
166
    // If 2+ nodes in the list
167
    else
168
    {
169
        tail = tail->prev;
170
        tail->next = nullptr;
171
    }
172

173
    delete delNode;
174

175
    length--;
176
}
177

178
// Delete the first node
179
// T = O(1)
180
void DoublyLinkedList::deleteFirst()
181
{
182
    // Do not allow delete operation on an empty list
183
    if (length == 0)
184
    {
185
        cout << "ERROR: Cannot delete from an empty list. Terminating!" << endl;
186
        exit(EXIT_FAILURE);
187
    }
188

189
    Node *delNode = head;
190

191
    // If only 1 node in the list
192
    if (length == 1)
193
    {
194
        head = nullptr;
195
        tail = nullptr;
196
    }
197
    // If 2+ nodes in the list
198
    else
199
    {
200
        head = head->next;
201
        head->prev = nullptr;
202
    }
203

204
    delete delNode;
205

206
    length--;
207
}
208

209
// Get the node value of the given index position
210
// T = O(n)
211
Node* DoublyLinkedList::get(int index)
212
{
213
    // Validity check for index
214
    if (index < 0 || index >= length)
215
        return nullptr;
216

217
    Node *temp = head;
218

219
    // Search for the node
220

221
    /* This would still work, but optimization can be done!
222
    for (int i = 0; i < index; i++)
223
        temp = temp->next;
224
    */
225

226
    // If the index is within the first half of the list
227
    if (index < length / 2)
228
    {
229
        // Start searching from the head
230
        for (int i = 0; i < index; i++)
231
            temp = temp->next;
232
    }
233
    // If the index is within the second half of the list
234
    else
235
    {
236
        // Start searching from the tail
237
        temp = tail;
238
        for (int i = length - 1; i > index; i--)
239
            temp = temp->prev;
240
    }
241

242
    return temp;
243
}
244

245
// Set the node value of the given index position
246
// T = O(n)
247
bool DoublyLinkedList::set(int index, int value)
248
{
249
    // Get the node
250
    Node *temp = get(index);
251

252
    // Set the value
253
    if (temp)
254
    {
255
        temp->value = value;
256
        return true;
257
    }
258

259
    return false;
260
}
261

262
// Reverse the list
263
// T = O(n)
264
void DoublyLinkedList::reverse()
265
{
266
    // Swap head and tail
267
    Node *curr = head;
268
    head = tail;
269
    tail = curr;
270

271
    Node *temp = nullptr;   // Temporary pointer to be used for swaping prev & next pointers
272

273
    // Iteratively swap prev and next pointers
274
    while (curr)
275
    {   
276
        // Swap prev and next
277
        temp = curr->prev;
278
        curr->prev = curr->next;
279
        curr->next = temp;
280

281
        // Advance curr
282
        curr = curr->prev;
283
    }   
284
}
285

286
// Print the list
287
// T = O(n)
288
void DoublyLinkedList::printList()
289
{
290
    Node *temp = head;
291

292
    while (temp)
293
    {
294
        cout << temp->value << " ";
295
        temp = temp->next;
296
    }
297

298
    cout << endl;
299
}
300

301
// Destructor
302
// T = O(n)
303
DoublyLinkedList::~DoublyLinkedList()
304
{
305
    // head, tail, length will be destroyed by default, but the nodes will not.
306
    // So, make sure to delete them manually in the destructor.
307

308
    Node *temp = head;
309

310
    while (head)
311
    {
312
        head = head->next;
313
        delete temp;
314
        temp = head;
315
    }
316
}

Test Driver

57
1
//==============================================================================
2
// File     : main.cpp
3
// Brief    : Test driver for Doubly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : May 17, 2023
6
//==============================================================================
7

8
#include <iostream>
9
#include "doubly_linked_list.h"
10

11
using namespace std;
12

13
int main(int argc, char *argv[])
14
{
15
    // Create a doubly-linked list
16
    DoublyLinkedList *dll = new DoublyLinkedList(2);
17
    
18
    // Prepend
19
    dll->prepend(1);
20

21
    // Append
22
    dll->append(4);
23
    dll->append(5);
24
    dll->append(6);
25

26
    // Insert (insert 3 at index 2)
27
    dll->insert(2, 3);  
28

29
    // Print the list
30
    dll->printList();       // 1 2 3 4 5 6
31

32
    // Delete first
33
    dll->deleteFirst();
34

35
    // Delete last
36
    dll->deleteLast();
37

38
    // Delete from the middle (index 1)
39
    dll->deleteNode(1);
40

41
    // Print the list
42
    dll->printList();       // 2 4 5
43

44
    // Set (value of the node at index 1 to 10)
45
    dll->set(1, 10);
46

47
    // Get (value of the node at index 1 to 10)
48
    cout << dll->get(1)->value << endl; // 10
49

50
    // Reverse the list
51
    dll->reverse();
52

53
    // Print the list
54
    dll->printList();       // 5 10 2
55

56
    return 0;
57
}

4
1
1 2 3 4 5 6 
2
2 4 5 
3
10
4
5 10 2