Doubly Linked List

Doubly Linked Lists / Slide 2

Motivation
 Doubly linked lists are useful for playing video
and sound files with “rewind” and instant
“replay”
 They are also useful for other linked data
where “require” a “fast forward” of the data as
needed
Doubly Linked Lists / Slide 3

 list using an array:

 Knowledge of list size
 Access is easy (get the ith element)
 Insertion/Deletion is harder
 list using ‘singly’ linked lists:
 Insertion/Deletion is easy
 Access is harder

 But, can not ‘go back’!

Doubly Linked Lists / Slide 4

Doubly Linked Lists

In a Doubly Linked-List each item points to both its
predecessor and successor
 prev points to the predecessor
 next points to the successor

10 20 40 55 70

Head
Cur->prev Cur Cur->next
Doubly Linked List Definition
struct Node{
int data;
Node* next;
Node* prev;
};
typedef Node* NodePtr;
Doubly Linked Lists / Slide 6

Doubly Linked List Operations

 insertNode(NodePtr& Head, int item)
//add new node to ordered doubly linked
//list

 deleteNode(NodePtr& Head, int item)

//remove a node from doubly linked list

 SearchNode(NodePtr Head, int item)

 Print(nodePtr Head, int item)

Doubly Linked Lists / Slide 7

Deleting a Node
 Delete a node Cur (not at front or rear)

(Cur->prev)->next = Cur->next;
(Cur->next)->prev = Cur->prev;
delete Cur;

10 20 40 55 70

Head
Cur
Doubly Linked Lists / Slide 8

void deleteNode(NodePtr& head, int item) {

NodePtr cur;
cur = searchNode(head, item);

if (head==NULL) { …
} Empty case
else if (cur->prev == NULL) { …
}
else if (cur->next==NULL) { … At-the-beginning case
}
else { At-the-end case
(cur->prev)->next = cur->next;
General
(cur->next)->prev = cur->prev; case
delete cur;
}
}

A systematic way is to start from all these cases, then try to simply the codes, …
Doubly Linked Lists / Slide 9

Inserting a Node
 Insert a node New before Cur (not at front or
rear)
New->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New;

10 20 55 70

Head 40
Cur

New
Doubly Linked Lists / Slide 10

void insertNode(NodePtr& head, int item) {

NodePtr cur;
cur = searchNode(head, item);

if (head==NULL) { …
}
else if (cur->prev == NULL) { …
}
else if (cur->next==NULL) { …
}
else {
blablabla …
}
}

Many special cases to consider.

Doubly Linked Lists / Slide 11

Many different linked lists …

 singly linked lists
 Without ‘dummy’
 With dummy
 circular

 doubly linked lists

 Without ‘dummy’
 With dummy

Using ‘dummy’ is a matter of personal preference!

+ simplify codes (not that much 
- Less logically sounds
Doubly Linked Lists / Slide 12

singly linked list

Head
2010 20 40 55 70

(singly) circular linked list

10 20 40 55 70
Rear
(regular) doubly linked list
10 20 40 55 70
Head

doubly linked list with dummy

Dummy
10 20 40 55 70
Head
Doubly Linked Lists / Slide 13

Doubly Linked Lists

with Dummy Head Node

 To simplify insertion and deletion by avoiding

special cases of deletion and insertion at front
and rear, a dummy head node is added at the
head of the list
 The last node also points to the dummy head
node as its successor
Doubly Linked Lists / Slide 14

Idea of ‘dummy’ object

‘dummy object’ is also called a ‘sentinel’, it allows the simplification of
special cases, but confuses the emptyness NULL!

 Instead of pointing to NULL, point to the ‘dummy’!!!

 Skip over the dummy for the real list

Dummy Head Node

10 20 40 55 70

Head
Doubly Linked Lists / Slide 15

Empty list:

Dummy Head Node

Head

Head->next = head; compared with head=NULL;

operations Doubly linked with dummy Singly linked

void createHead(NodePtr& head){

head = new Node;
head->next = head; NodePtr head=NULL;
head->prev = head;
}

NodePtr head;
createHead(head);

NodePtr cur=head;

creation
NodePtr cur=head;
cur=cur->next;

cur=head;
cur=head; // dummy head

cur=NULL; // or head=NULL;

reference

Start from

Empty test
Print the whole list:

void print(NodePtr head){

NodePtr cur=head->next;
while(cur != head){
cout << cur->data << " ";
cur = cur->next;
}
}
 Searching a node
(returning NULL if not found the element):

NodePtr searchNode(NodePtr head, int item){

NodePtr cur = head->next;

while ((cur != head) && (item != cur->data))

cur=cur->next;

if (cur == head) cur = NULL; // we didn’t find

return cur;
}

End of the list, empty

Doubly Linked Lists / Slide 19

Deleting a Node
 Delete a node Cur at front
(Cur->prev)->next = Cur->next;
(Cur->next)->prev = Cur->prev;
delete Cur;

Dummy Head Node

10 20 40 55 70

Head Cur
Doubly Linked Lists / Slide 20

 Delete a node Cur in the middle

(Cur->prev)->next = Cur->next;
(Cur->next)->prev = Cur->prev;
delete Cur; // same as delete front!

Dummy Head Node

10 20 40 55 70

Cur
Head
Doubly Linked Lists / Slide 21

 Delete a node Cur at rear

(Cur->prev)->next = Cur->next;
(Cur->next)->prev = Cur->prev;
delete Cur; // same as delete front and middle!

Dummy Head Node

10 20 40 55 70

Head Cur
void deleteNode(NodePtr head, int item){
NodePtr cur;
cur = searchNode(head, item);
if(cur != NULL){
cur->prev->next = cur->next;
cur->next->prev = cur->prev;

delete cur;
}
}

If we found the element, it does not mean any emptyness!

Doubly Linked Lists / Slide 23

Inserting a Node
 Insert a Node New after dummy node and
before Cur
New->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New;

Dummy Head Node

20
10
Head New Cur
Doubly Linked Lists / Slide 24

 Insert a Node New at Rear (with Cur pointing

to dummy head)
New->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New;

Dummy Head Node

10 20 40 55 70

Cur Head New

Doubly Linked Lists / Slide 25

 Insert a Node New in the middle and before

Cur New->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New;

Dummy Head Node

10 20 55
40

New Cur
Head
Doubly Linked Lists / Slide 26

 Insert a Node New to Empty List (with Cur

pointing to dummy head node)
New->next = Cur;
New->prev = Cur->prev;
Cur->prev = New;
(New->prev)->next = New;

Dummy Head Node

20

Head Cur New

 void insertNode(NodePtr head, int item){
NodePtr newp, cur;
newp = new Node;
creation
newp->data = item;

cur = head->next;
location while ((cur != head)&&(!(item<=cur->data)))
cur = cur->next;

newp->next = cur;
newp->prev = cur->prev;
insertion cur->prev = newp;
(newp->prev)->next = newp;
}

It is similar to, but different from SearchNode!

(it returns NULL if no element)
void main(){
NodePtr Head, temp;

createHead(Head);
insertNode(Head, 3); Result is
insertNode(Head, 5); 235
insertNode(Head, 2);
123578
print(Head);
insertNode(Head, 7); 12358
insertNode(Head, 1); Data is contained in the list
insertNode(Head, 8);
print(Head);
deleteNode(Head, 7);
deleteNode(Head, 0);
print(Head);
temp = searchNode(Head, 5);
if(temp !=NULL)
cout<<" Data is contained in the list"<<endl;
else
cout<<" Data is NOT contained in the list"<<endl;
}