Data Structures & Algorithms

Lecture 4: Doubly Linked Lists

Dr. Muhammad Shahzad

muhammad.shehzad@seecs.edu.pk

Department Of Computing (DOC),

School of Electrical Engineering & Computer Science (SEECS),
National University of Sciences & Technology (NUST)

17/10/2016
 Recap

Linked structures
Singly Linked Lists

struct ListNode {
float value;
struct ListNode *next;
};

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 2

 Reversing a linked list

struct Node* reverse(struct Node* head) head

{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
{
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 3

 Reversing a linked list

struct Node* reverse(struct Node* head) head newHead

{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 4

 Reversing a linked list

struct Node* reverse(struct Node* head) head newHead

{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 5

 Reversing a linked list

struct Node* reverse(struct Node* head) head newHead

{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 6

 Reversing a linked list

struct Node* reverse(struct Node* head) head null newHead

{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 7

 Reversing a linked list

struct Node* reverse(struct Node* head) head null

{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
newHead tmpNext
{
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 8

 Reversing a linked list

struct Node* reverse(struct Node* head) head

null
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
newHead tmpNext
{
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 9

 Reversing a linked list

struct Node* reverse(struct Node* head) head

null
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
newHead tmpNext
{
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 10

 Reversing a linked list

struct Node* reverse(struct Node* head) head

null
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
newHead tmpNext
{
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 11

 Reversing a linked list

struct Node* reverse(struct Node* head) head

null
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
newHead tmpNext
{
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 12

 Reversing a linked list

struct Node* reverse(struct Node* head) head

null
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{ newHead
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 13

 Reversing a linked list

struct Node* reverse(struct Node* head) head

null
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{ newHead
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 14

 Reversing a linked list

struct Node* reverse(struct Node* head) head

null
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{ newHead
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 15

 Reversing a linked list

struct Node* reverse(struct Node* head) head

null
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{ newHead
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 16

 Reversing a linked list

struct Node* reverse(struct Node* head) head

null
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{ newHead
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 17

 Reversing a linked list

struct Node* reverse(struct Node* head) head

null
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{ newHead
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 18

 Reversing a linked list

struct Node* reverse(struct Node* head)

null head
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{ newHead
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 19

 Reversing a linked list

struct Node* reverse(struct Node* head)

null head
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{ newHead
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 20

 Reversing a linked list

struct Node* reverse(struct Node* head)

null head
{
Node* newHead = NULL;
null
Node* tmpNext;
while (head)
tmpNext
{ newHead
tmpNext = head->next;
head->next = newHead;
newHead = head;
head = tmpNext;
}
return newHead;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 21

 Assignment

Insert an item in the middle of the list

Diagram/Code?

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 22

 Assignment

Insert an item in the middle of the list

Diagram/Code?

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 23

 Todays lecture

Linked structures
Singly Linked Lists
Doubly Linked Lists

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 24

 Singly Linked List Problems

head 2 9 7 NULL

Problem:
Cannot get backwards or to the beginning since no
information related to previous node is available

Need a loop
while (nodePtr->next) // Find the last node in the list
nodePtr = nodePtr->next;

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 25

 Other list structures

Doubly-linked list
Each node has a pointer to its successor and its
predecessor
Faster insert/delete, but more space

Circular list
The last node points back to the head
Sorted list
Items stored in sorted order
Skip list
Skip certain nodes to avoid sequential processing
Self Organizing list
Dynamically organizes the list in a certain manner

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 26

Doubly Linked Lists

27
 Doubly Linked List

Contains two references to other nodes within each

node: one to the next node on the list, and one to the
previous node

I.e., every node (except the last node) contains the

address of the next node, and every node (except the
first node) contains the address of the previous node

Allows traversal in either direction

Implementations: ALT+TAB and ALT+SHIFT+TAB

(Window Browsing)

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 28

 Doubly Linked List

Add a prev pointer to Node class

Allows backward iteration

When adding or removing a node, we must fix the prev

and next pointers to have the correct value!

Can make it easier to implement some methods such

as remove

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 29

 Declaration Singly vs Doubly

Singly Linked List Doubly Linked List

class Node { class Node {

public: public:
Node() { Node() {
next = 0; next = prev = 0;
} }
Node(int i, Node *in = 0) { Node(int i, Node *in = 0 , Node *p = 0)
info = i; next = in; {
} info = i; next = in; prev = p;
int info; }
Node *next; int info;
}; Node *next, *prev;
};

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 30

 Add to tail operation

Singly Linked List Doubly Linked List

void AccessNode::addToTail(int el) { void AccessNode::addToTail(int el) {
if (tail != 0) { // if list not empty; if (tail != 0) { // if list not empty;
tail->next = new Node(el); tail = new Node(el,0,tail);
tail = tail->next; tail->prev->next = tail;
} }
else else
head = tail = new Node(el); head = tail = new Node(el);
} }

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 31

 Add to tail operation

Doubly Linked List

void AccessNode::addToTail(int el) {
if (tail != 0) { // if list not empty;
tail = new Node(el,0,tail);
tail->prev->next = tail;
}
else
head = tail = new Node(el);
}

Call from main() with el =10

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 32

 Add to tail operation

Doubly Linked List

void AccessNode::addToTail(int el) {
if (tail != 0) { // if list not empty;
tail = new Node(el,0,tail);
tail->prev->next = tail;
}
else
head = tail = new Node(el);
}

Call from main() with el =10

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 33

 Add to tail operation

Doubly Linked List

void AccessNode::addToTail(int el) {
if (tail != 0) { // if list not empty;
tail = new Node(el,0,tail);
tail->prev->next = tail;
}
else
head = tail = new Node(el);
}

Call from main() with el =10

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 34

 Add to tail operation

Doubly Linked List

void AccessNode::addToTail(int el) {
if (tail != 0) { // if list not empty;
tail = new Node(el,0,tail);
tail->prev->next = tail;
}
else
head = tail = new Node(el);
}

Call from main() with el =10

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 35

 Adding a node in middle

When adding a node to the list at a given index, the

following steps must be taken:
Advance through the list to the node just before the one
with the proper index
Create a new node, and attach it to the nodes that
should precede and follow it

How many 'arrows' (references) will need to be

changed?

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 36

 Deleting a node

int AccessNode::deleteFromTail(int el) {

int el = tail->info;
if (head == tail) { // if only one node in the list;
delete head;
head = tail = 0;
}
else { // if more than one node in the list;
tail = tail->prev;
delete tail->next;
tail->next = 0;
}
return el;
}

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 37

 Deleting a node in middle

When deleting a node from the list at a given index, the

following steps must be taken:
Advance through the list to the node with the proper
index
Detach it from the nodes that used to precede and follow
it

How many 'arrows' (references) will need to be

changed?

M. Shahzad: Data Structures & Algorithms Lecture 4: Doubly Linked List 38