Web
Analytics Made Easy - StatCounter

Doubly Linked Lists (With Code in C, C++, Java, and Python)

Introduction

A doubly linked list is a linear data structure where each node has a link to the next node as well as to the previous node. Each component of a doubly linked list has three components.

  1. prev: It is a pointer that points to the previous node in the list.
  2. data: It holds the actual data.
  3. next: It is a pointer that points to the next node in the list.

Since each node has pointers in both the direction, doubly linked list can be traversed in both forward and backward directions. Figure 1 shows an example of a doubly linked list containing 2 items.

Fig 1: An example of a doubly linked list

The first node is pointed by a pointer called head and the last node is pointed by a pointer called tail. The first node does not have a previous pointer and the last node does not have the next pointer.

Operations on a doubly linked list

Insert at the head

  1. Create a new node with the item to be inserted. Initially set both prev and next pointer to null.
  2. Set next pointer of the new node to head.
  3. Set the prev pointer of head to the new node.
  4. Set head pointer to the new node.

Fig 2: Insertion at the head

Insert at the tail

  1. Create a new node with the item to be inserted. Initially set both prev and next pointer to null.
  2. Set next pointer of tail to the new node.
  3. Set prev pointer of the new node to tail.
  4. Set tail pointer to the new node.

Fig 3: Insertion at the tail

Insert at the middle

  1. Create a new node with the item to be inserted. Initially set both prev and next pointer to null.
  2. Seek through the list until you find a node after which you want to insert the new node. Call this node D and node next to it N.
  3. Set D’s next pointer to the new node and new node’s prev pointer to D.
  4. Set the new node’s next pointer to N and N’s prev pointer to the new node.

Fig 4: Insertion at the middle (Steps 1 and 2 are combined into 1)

Find the item in the list

  1. Start with head or tail. Call it curr.
  2. If curr has the item you are looking for, return the item.
  3. Proceeds to the next node. If you started with head use the next pointer to go to the next item otherwise use prev pointer.
  4. Repeat step 2 and 3 until you get null pointer. In case you get to the null pointer, you have come to the end and item is not on the list.

Remove the item at the head

(Note: for all the delete operations, the node needs to be destroyed in order to free the memory. Some languages like Java, Python, etc has a garbage collector that handles this automatically while other languages like C, C++ does not have such a mechanism and programmer has to destroy it explicitly).

  1. Find the next node of the head and call it N.
  2. Set the prev pointer of N to null.
  3. Set both the pointers of the head to null.
  4. Destroy the node pointed by head and set the head pointer to N.

Fig 5: Deletion at the head

Remove the item at the tail

  1. Find the previous node of the tail and call it N.
  2. Set the next pointer of N to null.
  3. Set both the pointers of the tail to null.
  4. Destroy the node pointed by tail and set the tail pointer to N.

Fig 6: Deletion at the tail

Remove item anywhere in the list

  1. Seek through the list until you found the desired node. Call it D.
  2. Set D’s previous node’s next pointer to D’s next node and set D’s next node’s prev pointer to D’s previous node.
  3. Set both the pointers of D to null.
  4. Destroy the node pointed by D.

Fig 7: Deletion at the middle

Complexities

The table below shows the operation and corresponding complexity of all the operations discussed above.

OperationComplexity
Insert at the headO(1)
Insert at the tailO(1)
Insert at the middleO(n)
Delete at the headO(1)
Delete at the tailO(1)
Delete at the middleO(n)
Search the listO(n)

Implementation in C, C++, Java, and Python

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
// C implementation of doubly linked list
#include <stdio.h>
#include <stdlib.h>



// data structure for Node
// data -> the actual value
// next -> address of the next node
struct Node {
int data;
struct Node *next;
struct Node *prev;
};

typedef struct Node *NodePtr;

// global variables head and tail
NodePtr head = NULL;
NodePtr tail = NULL;

// check if the list is empty
int isEmpty() {
return head == NULL;
}

// Insert 'value' at the front of the list
void insertAtFront(int value) {
NodePtr node = malloc(sizeof(NodePtr));
node->data = value;
node->next = NULL;
node->prev = NULL;

if (isEmpty()) {
head = node;
tail = node;
} else {
node->next = head;
head->prev = node;
head = node;
}

}

// insert value at the back of the linked list
void insertAtBack(int value) {
NodePtr node = malloc(sizeof(NodePtr));
node->data = value;
node->next = NULL;
node->prev = NULL;

if (isEmpty()) {
head = node;
tail = node;
} else {
tail->next = node;
node->prev = tail;
tail = node;
}
}

// inserts value after key
NodePtr insertAfter(int key, int value) {
NodePtr node = malloc(sizeof(NodePtr));
node->data = value;
node->next = NULL;
node->prev = NULL;

// find the position of key
NodePtr currPtr = head;
while (currPtr != NULL && currPtr->data != key) {
currPtr = currPtr->next;
}

// if key is not there, raise error
if (currPtr == NULL) {
printf("%s", "key not found");
} else if (currPtr->next == NULL) {
// if key is the last node, insert right after it
currPtr->next = node;
node->prev = currPtr;
tail = node;
} else {
// insert between key and item next to key
NodePtr nextPtr = currPtr->next;
currPtr->next = node;
node->prev = currPtr;
node->next = nextPtr;
nextPtr->prev = node;
}
}

// returns the data at first node
int topFront() {
if (isEmpty()) {
printf("%s", "List is empty");
} else {
return head->data;
}
}

// returns the data at last node
int topBack() {
if (isEmpty()) {
printf("%s", "List is empty");
} else if (head->next == NULL) {
return head->data;
} else {
NodePtr currPtr = head;
while (currPtr->next != NULL) {
currPtr = currPtr->next;
}
return currPtr->data;
}
}

// removes the item at front of the linked list and return
int popFront() {
int item;
if (isEmpty()) {
printf("%s", "List is empty");
return -99999;
} else {
item = head->data;
if (head->next != NULL) {
head->next->prev = NULL;
}
NodePtr next = head->next;
free(head);
head = next;
}

return item;
}

// remove the item at the list of the linked list and return
int popBack() {
int item;
if (isEmpty()) {
printf("%s", "List is empty");
return -99999;
} else {
item = tail->data;
if (tail->prev != NULL) {
tail->prev->next = NULL;
}
NodePtr prev = tail->prev;
tail->prev = NULL;
free(tail);
tail = prev;

}

return item;
}

// removes an item with value 'key'
void delete(int key) {
if (isEmpty()) {
printf("%s", "List is empty");
return;
}

// get to the position of key
NodePtr currPtr = head;
while(currPtr != NULL && currPtr->data != key) {
currPtr = currPtr->next;
}

if (currPtr == NULL) {
printf("%s", "Key is not found in the list");
return;
}

if (currPtr->prev == NULL) {
// this is the first item
popFront();

} else if (currPtr->next == NULL) {
// this is the last item
popBack();

} else {
// anywhere in between first and last
NodePtr nextPtr = currPtr->next;
NodePtr prevPtr = currPtr->prev;
nextPtr->prev = prevPtr;
prevPtr->next = nextPtr;
currPtr->next = NULL;
currPtr->prev = NULL;
free(currPtr);
currPtr = NULL;

}
}

// print the linked list
void print() {
NodePtr currPtr = head;
while (currPtr != NULL) {
printf("%d", currPtr->data);
printf(" ");
currPtr = currPtr->next;
}
printf("\n");
}

// print the linked list
void printReverse() {
NodePtr currPtr = tail;
while (currPtr != NULL) {
printf("%d", currPtr->data);
printf(" ");
currPtr = currPtr->prev;
}
printf("\n");
}

// check if a key is in the list
int find(int key) {
if (isEmpty()) {
return 0;
}

NodePtr currPtr = head;
while (currPtr != NULL && currPtr->data != key) {
currPtr = currPtr->next;
}

if (currPtr == NULL) {
return 0;
}

return 1;
}

int main() {
insertAtFront(23);
insertAtBack(25);
insertAtBack(44);
insertAfter(25, 39);
insertAfter(25, 233);
insertAfter(44, 45);
print();
int item = popFront();
printf("%d\n", item);
print();
item = popBack();
printf("%d\n", item);
print();
delete(233);
print();
// operations
return 0;
}
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
// C++ implementation of doubly linked list
#include <iostream>

using namespace std;

// data structure for Node
// data -> the actual value
// next -> address of the next node
struct Node {
int data;
Node *next;
Node *prev;
};

typedef Node *NodePtr;

class MyLinkedList {
private:
NodePtr head;
NodePtr tail;

public:
MyLinkedList() {
head = nullptr;
tail = nullptr;

}

// Insert 'value' at the front of the list
void insertAtFront(int value) {
NodePtr node = new Node;
node->data = value;
node->next = nullptr;
node->prev = nullptr;

if (isEmpty()) {
head = node;
tail = node;
} else {
node->next = head;
head->prev = node;
head = node;
}
}

// insert value at the back of the linked list
void insertAtBack(int value) {
NodePtr node = new Node;
node->data = value;
node->next = nullptr;

if (isEmpty()) {
head = node;
tail = node;
} else {
tail->next = node;
node->prev = tail;
tail = node;
}
}

// inserts value after key
void insertAfter(int key, int value) {
NodePtr node = new Node;
node->data = value;
node->next = nullptr;

// find the position of key
NodePtr currPtr = head;
while (currPtr != nullptr && currPtr->data != key) {
currPtr = currPtr->next;
}

// if key is not there, raise error
if (currPtr == nullptr) {
cout<<"key not found";
} else if (currPtr->next == nullptr) {
// if key is the last node, insert right after it
currPtr->next = node;
node->prev = currPtr;
tail = node;
} else {
// insert between key and item next to key
NodePtr nextPtr = currPtr->next;
currPtr->next = node;
node->prev = currPtr;
node->next = nextPtr;
nextPtr->prev = node;
}
}

// returns the data at first node
int topFront() {
if (isEmpty()) {
cout<<"List is empty"<<endl;
} else {
return head->data;
}
}

// returns the data at last node
int topBack() {
if (isEmpty()) {
cout<<"List is empty"<<endl;
} else if (head->next == nullptr) {
return head->data;
} else {
NodePtr currPtr = head;
while (currPtr->next != nullptr) {
currPtr = currPtr->next;
}
return currPtr->data;
}
}

// removes the item at front of the linked list and return
int popFront() {
int item;
if (isEmpty()) {
cout<<"List is empty"<<endl;
return -99999;
} else {
NodePtr nextPtr = head->next;
if (nextPtr->next != nullptr) {
nextPtr->prev = nullptr;
}
item = head->data;
// remove head
delete head;

// make nextptr head
head = nextPtr;
}

return item;
}

// remove the item at the list of the linked list and return
int popBack() {
int item;
if (isEmpty()) {
cout<<"List if empty"<<endl;
return -99999;
} else {
item = tail->data;
NodePtr prev = tail->prev;
if (prev != nullptr) {
prev->next = nullptr;
}

tail->prev = nullptr;
delete tail;
tail = prev;
}

return item;
}

// removes an item with value 'key'
void remove(int key) {
if (isEmpty()) {
cout<<"list is empty"<<endl;
return;
}

// get to the position of key
NodePtr currPtr = head;
while(currPtr != nullptr && currPtr->data != key) {
currPtr = currPtr->next;
}

if (currPtr == nullptr) {
cout<<"Key is not found in the list"<<endl;
return;
}

if (currPtr->prev == nullptr) {
// this is the first item
popFront();

} else if (currPtr->next == nullptr) {
// this is the last item
popBack();
} else {
// anywhere in between first and last
NodePtr nextPtr = currPtr->next;
NodePtr prevPtr = currPtr->prev;
nextPtr->prev = prevPtr;
prevPtr->next = nextPtr;

currPtr->next = nullptr;
currPtr->prev = nullptr;
delete currPtr;
currPtr = nullptr;
}
}

// print the linked list
void print() {
NodePtr currPtr = head;
while (currPtr != nullptr) {
cout<<currPtr->data<<" ";
currPtr = currPtr->next;
}
cout<<endl;
}

void printReverse() {
NodePtr currPtr = tail;
while (currPtr != nullptr) {
cout<<currPtr->data<<" ";
currPtr = currPtr->prev;
}
cout<<endl;
}

// check if the list is empty
bool isEmpty() {
return head == nullptr;
}

// check if a key is in the list
bool find(int key) {
if (isEmpty()) {
return false;
}

NodePtr currPtr = head;
while (currPtr != nullptr && currPtr->data != key) {
currPtr = currPtr->next;
}

if (currPtr == nullptr) {
return false;
}

return true;
}
};

int main() {
MyLinkedList list;
list.insertAtFront(34);
list.insertAtFront(44);
list.insertAtBack(52);
list.insertAtBack(22);
list.printReverse();
list.insertAfter(22, 33);
list.insertAfter(52, 100);
list.print();
cout<<list.popFront()<<endl;
list.print();
cout<<list.popBack()<<endl;
list.print();
list.remove(100);
list.printReverse();
// operations
return 0;
}
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
// Java implementation of Doubly linked list 

class Node {
int data;
Node next;
Node prev;

public Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}

public class MyLinkedList {
private Node head;
private Node tail;

public MyLinkedList() {
head = null;
tail = null;
}

// Insert 'value' at the front of the list
public void insertAtFront(int value) {
Node node = new Node(value);
if(isEmpty()) {
head = node;
tail = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
}

// insert value at the back of the linked list
public void insertAtBack(int value) {
Node node = new Node(value);
if (isEmpty()) {
head = node;
tail = node;
} else {
tail.next = node;
node.prev = tail;
tail = node;
}
}

// inserts value after key
public void insertAfter(int key, int value) {
Node node = new Node(value);

// find the position of key
Node curr = head;
while(null != curr && curr.data != key) {
curr = curr.next;
}

if (null == curr) {
System.out.println("Key not found");
return;
}

if(null == curr.next) {
curr.next = node;
node.prev = curr;
tail = node;
} else {
Node next = curr.next;
curr.next = node;
node.prev = curr;
node.next = next;
next.prev = node;
}
}

// returns the data at first node
public int topFront() {
if (isEmpty()) {
System.out.println("List is empty");
return -999999;
}

return head.data;
}

// returns the data at last node
public int topBack() {
if(isEmpty()) {
System.out.println("List is empty");
return -999999;
}

Node curr = head;
while(curr.next != null) {
curr = curr.next;
}

return curr.data;
}

// removes the item at front of the linked list and return
public int popFront() {
if (isEmpty()) {
System.out.println("List is empty");
return -999999;
}
int item = head.data;
Node next = head.next;
if (next != null) {
next.prev = null;
}
head = next;
return item;
}

// remove the item at the end of the list and return
public int popBack() {
if (isEmpty()) {
System.out.println("List is empty");
return -999999;
}
int item = tail.data;
Node prev = tail.prev;
if (prev != null) {
prev.next = null;
}
tail.prev = null;
tail = prev;
return item;
}

// removes an item with value 'key'
public void remove(int key) {
if (isEmpty()) {
System.out.println("List is empty");
return;
}

// find the position of the key
Node curr = head;

while(curr != null && curr.data != key) {
curr = curr.next;
}

if(curr == null) {
System.out.print("key not found");
return;
}

// if curr is head, delete the head
if (curr.prev == null) {
popFront();

} else if (curr.next == null) { // if curr is last item
popBack();

} else { //anywhere between first and last node
Node next = curr.next;
Node prev = curr.prev;

prev.next = next;
next.prev = prev;

curr.prev = null;
curr.next = null;
curr = null;
}


}

// check if the key is in the list
public boolean find(int key) {
if (isEmpty()) {
System.out.println("List is empty");
return false;
}

Node curr = head;
while(curr != null && curr.data != key) {
curr = curr.next;
}

if (curr == null) {
return false;
}

return true;
}

// check if the list is empty
public boolean isEmpty() {
return head == null;
}

// print all the items
public void print() {
if (isEmpty()) {
System.out.println("Nothing to display");
} else {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}

// print all the items
public void printReverse() {
if (isEmpty()) {
System.out.println("Nothing to display");
} else {
Node curr = tail;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.prev;
}
System.out.println();
}
}

public static void main(String [] args) {
MyLinkedList list = new MyLinkedList();
list.insertAtFront(33);
list.insertAtFront(55);
list.insertAtBack(12);
list.insertAtBack(3);
list.printReverse();
list.insertAfter(3, 44);
list.insertAfter(12, 50);
list.print();
System.out.println(list.popFront());
list.print();
System.out.println(list.popBack());
list.print();
list.remove(12);
list.printReverse();
}
}
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
# Python implementation of Doubly linked list 
import sys

class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None

class MyLinkedList:
def __init__(self):
self.head = None
self.tail = None

# Insert 'value' at the front of the list
def insert_at_front(self, value):
node = Node(value)
if self.is_empty():
self.head = node
self.tail = node
else:
node.next = self.head
self.head.prev = node
self.head = node

# insert value at the back of the linked list
def insert_at_back(self, value):
node = Node(value)
if self.is_empty():
self.head = node
else:
self.tail.next = node
node.prev = self.tail
self.tail = node

# inserts value after key
def insert_after(self, key, value):
node = Node(value)

# find the position of key
curr = self.head
while curr != None and curr.data != key:
curr = curr.next

if curr == None:
print 'Key not found'
return

if curr.next == None:
curr.next = node
node.prev = curr
self.tail = node
else:
next_node = curr.next
curr.next = node
node.prev = curr
node.next = next_node
next_node.prev = node

# returns the data at first node
def top_front(self):
if self.is_empty():
print 'List is empty'
return

return self.head.data

# returns the data at last node
def top_back(self):
if self.is_empty():
print 'List is empty'
return

curr = self.head
while curr.next != None:
curr = curr.next

return curr.data

# removes the item at front of the linked list and return
def pop_front(self):
if self.is_empty():
print 'List is empty'
return

next_node = self.head.next
if (next_node != None):
next_node.prev = None
item = self.head.data
self.head = next_node
return item

# remove the item at the end of the list and return
def pop_back(self):
if self.is_empty():
print 'List is empty'
return

item = self.tail.data
prev = self.tail.prev

if prev != None:
prev.next = None

self.tail.prev = None
self.tail = prev

return item

# removes an item with value 'key'
def remove(self, key):
if self.is_empty():
print 'List is empty'
return

# find the position of the key
curr = self.head

while curr != None and curr.data != key:
curr = curr.next

if curr == None:
print 'key not found'
return

# if curr is head, delete the head
if curr.prev == None:
self.pop_front()
elif curr.next == None: # if curr is last item
self.pop_back()
else: #anywhere between first and last node
next_node = curr.next
prev_node = curr.prev

prev_node.next = next_node
next_node.prev = prev_node

curr.next = None
curr.prev = None
curr = None

# check if the key is in the list
def find(self, key):
if self.is_empty():
print 'List is empty'
return False

curr = self.head
while curr != None and curr.data != key:
curr = curr.next

if curr == None:
return False

return True

# check if the list is empty
def is_empty(self):
return self.head == None

# print all the items
def printlist(self):
if self.is_empty():
print "Nothing to display"
else:
curr = self.head
while (curr != None):
sys.stdout.write(str(curr.data) + ' ')
curr = curr.next

print ''

def print_reverse(self):
if self.is_empty():
print "Nothing to display"
else:
curr = self.tail
while (curr != None):
sys.stdout.write(str(curr.data) + ' ')
curr = curr.prev

print ''

if __name__ == '__main__':
list = MyLinkedList()
list.insert_at_front(44)
list.insert_at_front(66)
list.insert_at_back(21)
list.insert_at_back(43)
list.print_reverse()
list.insert_after(43,49)
list.insert_after(21,33)
list.printlist()
print list.pop_front()
list.printlist()
print list.pop_back()
list.printlist()
list.remove(21)
list.print_reverse()