Doubly Linked List | C++ Implementation
The nodes in a linked list are connected through pointers. Pointers represent the address of a location in a memory. The order in a linked list is determined by a pointer in each node. A node in a doubly linked list contains a data item and a node pointer to the next node. In a singly linked list we can traverse only in one direction.
The first node of the linked list is the head and the last node is the tail. If head is NULL then the list is empty.
In C++, a node can be defined using struct, which contain a data item and a pointer to next node.
1
2
3
4
5
6
struct Node
{
T data;
Node * next;
Node(T val): data(val), next(nullptr){}
};
Node(T val): data(val), next(nullptr), prev(nullptr) {} is the constructor for the struct Node which is used to initialise data, next and prev. T means it is a generic struct and data can store values of all data types.
To declare head: Node *head, *tail;
In the above fig. Node containing 5 is head and node containing 15 is tail.
Implementation
The three basic operations supported by a linked list are searching, insertion and deletion.
Searching
The search function for doubly linked list is same as the search function for singly linked list.
Related: Singly Linked List
In the search function a value is passed as an argument and its node is returned if found, otherwise a message says “No such element in the list” and nullptr is returned.
The function starts searching from the head to the last node and passed value is matched with every node’s data item.
Here is the code for iterative search.
1
2
3
4
5
6
7
8
9
10
11
12
13
struct Node *search(T n)
{ //returns node of the given value
Node *node = head;
while(node != nullptr)
{
if(node->data == n)
return node;
node = node->next;
}
std::cerr << "No such element in the list \n";
return nullptr;
}
Insertion
We can insert a node at front or at back of the linked list. When we insert a node at front the next node pointer points to the head of the list and then the node is made new head of the list. The value to be inserted is passed as an argument and a new node is created containing the value.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insertFront(T val)
{
Node *node = new Node(val);
Node *tmp = head;
if (head == nullptr)
{
head = node;
tail = node;
}
else
{
node->next = head;
head = node;
node->next->prev = node;
}
}
When we insert a node at the back of the list, node is added after the tail and then the node becomes tail of the list.
1
2
3
4
5
6
7
8
9
void insertBack(T val)
{
Node *node = new Node(val);
if(tail->next == nullptr)
{
tail->next = node;
tail = node;
}
}
Deletion
In deleteNode function the value is entered which is to be deleted. The function search the node containing the value using search function and then the node is deleted.
If the searched node is head then node next to head is made head and then the searched node is deleted. The node is deleted only if the value exists means if (node != nullptr).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void deleteVal(T val)
{
Node* find = findVal(val);
Node *tmp = head;
if(tmp == find)
{
head = tmp->next;
}
else
{
while(find != nullptr)
{
if(tmp->next == find)
{
tmp->next = find->next;
find->next->prev = tmp;
delete find;
return;
}
tmp = tmp->next;
}
}
}
C++ Implementation of 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
template<class T>
class DoublyLinkedList
{
struct Node
{
T data;
Node* next;
Node* prev;
Node(T val): data(val), next(nullptr), prev(nullptr) {}
};
Node *head, *tail;
public:
DoublyLinkedList(): head(nullptr), tail(nullptr) {}
~DoublyLinkedList()
{
Node *tmp = nullptr;
while (head)
{
tmp = head;
head = head->next;
delete tmp;
}
head = nullptr;
}
DoublyLinkedList(const DoublyLinkedList<T> & dll) = delete;
DoublyLinkedList& operator=(DoublyLinkedList const&) = delete;
void insertFront(T val)
{
Node *node = new Node(val);
Node *tmp = head;
if (head == nullptr)
{
head = node;
tail = node;
}
else
{
node->next = head;
head = node;
node->next->prev = node;
}
}
void insertBack(T val)
{
Node *node = new Node(val);
if(tail->next == nullptr)
{
tail->next = node;
tail = node;
}
}
void deleteVal(T val)
{
Node* find = findVal(val);
Node *tmp = head;
if(tmp == find)
{
head = tmp->next;
}
else
{
while(find != nullptr)
{
if(tmp->next == find)
{
tmp->next = find->next;
find->next->prev = tmp;
delete find;
return;
}
tmp = tmp->next;
}
}
}
template <class U>
friend std::ostream & operator<<(std::ostream & os, const DoublyLinkedList<U> & dll){
dll.display(os);
return os;
}
private:
Node *findVal(T n) //returns node of the given number
{
Node *node = head;
while(node != nullptr)
{
if(node->data == n)
return node;
node = node->next;
}
std::cerr << "No such element in the list \n";
return nullptr;
}
void display(std::ostream& out = std::cout) const
{
Node *node = head;
while(node != nullptr)
{
out << node->data << " ";
node = node->next;
}
}
};
int main(){
DoublyLinkedList<int> l1;
l1.insertFront(3);
l1.insertBack(5);
l1.insertBack(12);
l1.insertFront(6);
l1.insertBack(88);
std::cout<<l1<<"\n";
l1.deleteVal(11);
std::cout<<l1<<"\n";
return 0;
}
View this code on Github
Get this post in pdf - Doubly Linked List
Reference:
Introduction to Algorithms
The Algorithm Design Manual
Data Structures and Algorithms Made Easy
You may also like:
Move all Odd numbers after Even numbers in Singly Linked List
Merge two sorted Linked List (in-place)
Split Singly Circular Linked List
Doubly Circular Linked List
Reverse the Linked List
Finding Length of Loop in Linked List