DATA STRUCTURES

Doubly and
Circular Lists
Problems with Linked Lists

-3 4 -1 NULL

header
A node in the list

NULL (An empty list)

header

Two problems – we can’t get back to the beginning of the list

from the end, and we can’t go backwards through the list. So,
circular linked lists and doubly linked lists were invented.
Other list flavors
 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.
DOUBLY LINKED LIST
Doubly-Linked Lists
 A common variation on linked lists is to
have two references to other nodes
within each node: one to the next node
on the list, and one to the previous node

 Doubly-linked lists make some

operations, such as deleting a tail node,
more efficient
Doubly Linked List
A doubly linked list is a linked list in which every node
•

has a next pointer and a back pointer

• 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.

A doubly linked list can be traversed in either direction

•
Doubly-Linked Lists
 Other operations, such as adding an
item to an ordered linked list, are easier
to program with doubly-linked lists
 Tradeoffs:
 The NodeType class is more complex: extra
instance variable, extra methods, revised
constructors
 Each node requires 4 additional bytes
Doubly-linked Lists - properties
 Allow sequential access to the list in both
directions
 Each element points to
 Next element
 Previous element
previous value next
Doubly-Linked List

head size tail

3

. .
Example - Doubly-linked Lists

• Non-empty doubly linked list

size head tail
3

null Bill Jill Karl null

p data n

• Empty doubly linked list

size head tail
0 null null
Advantages
 The doubly linked list eliminates the need
for the “pPrevious” pointer since each node
has pointers to both the previous and next
nodes in the list.

 You can go to the previous node easily

 Traversal is in both directions.

 Implementations: ALT+TAB and

ALT+SHIFT+TAB (Window Browsing)
 Picture Viewers, Power Point Presentations
Doubly-linked lists
 add a prev pointer to our Node class
 allows backward iteration
 some methods need to be modified
 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
Linked list add operation
 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?
Linked list remove
operation
 When removing 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?
addFirst Method
count head tail
Before:
3

null Bill Jill Karl null

Amma

New value

count head tail

After: 4
Bill Jill Karl null

null Amma
addLast method
Before:

New value
count head tail

3 Laura

null Bill Jill Karl null

After:

count head tail

Amma null
3

Bill Jill Karl

remove method
 Case 1: remove a middle element

Before:
size head tail

null Bill Jill Karl null


After: to be removed

size head tail

null Bill Karl null

Jill
remove method
 Case 2: remove head element
 Before:
count head tail
3

null Bill Jill Karl null

to be removed

count head tail

 After:
2

null Bill null Jill Karl null

remove method
 Case 3: remove the only element
 Before:
0
null Bill null

to be removed
 After
0 null null

null Bill null

To Remove Last Item From a Doubly-Linked List

Note: We no longer need

to traverse the list.
head size tail Save a reference to the
last data object so that it
4
can be returned later

. .
To Remove Last Item From a Doubly-Linked List

Reset tail so that it points

at the node prior to the
head size tail original tail node
4

. .
To Remove Last Item From a Doubly-Linked List

Get rid of the successor

node of the new tail node
head size tail
4

. .
To Remove Last Item From a Doubly-Linked List

Set the successor of the

new tail node to NULL,
head size tail decrement the size of the
list, and return the
3 reference to the deleted
data object

. . .
CIRCULAR LISTS
 DEFINITION 

A linked list in which the last node points to the first node
is called a circular linked list

In a circular linked list with more than one node, it is

convenient to make the pointer first point to the last node
of the list
A Circular Linked List

2 -3 4 -1

header

Have the last node link back to the first (or the header).
Circular Linked Lists
 Circular linked lists avoid the use of null
references in their nodes
 Can be useful for certain algorithms
 Can also make programming simpler:
fewer special cases to consider
 Successor of tail node is the head node;
in doubly-linked list
Circular linked lists
 Insertions and deletions into a circular
linked list follow the same logic patterns
used in a singly linked list except that
the last node points to the first node.

 Therefore, when inserting or deleting the

last node, in addition to updating the tail
pointer, we must also point the link field
of the new last node to the first node.
Circular linked list
 Advantage is that we can start searching
from any node of the linked list and get to
any other node.
 No logical head and tail pointers. We
follow the conventions as first element
inserted into the list is given status of head
and last element entered is called as a tail.
Circular Linked Lists

 Last node references the first node

 Every node has a successor
 No node in a circular linked list contains
NULL
 Circular Linked List
Linked list that hasn’t null (nil) value
in its
head
connection field. tail

2 4 5 9

Circular Single Linked

head list tail

2 4 5 9

Circular Double Linked

 Operation
 Creation Same with linear single
or double linked list
 Insertion
 Delete
 Traversal
 Searching
 Sorting
 Destroy
 


INSERTION
 Front Insertion
• If list is empty (head = nil).

head tail alloc(new)

new->info= 1
new 1 new->next =new
head=new
tail=new
Front Insertion (cont’d)
• If list isn’t empty (head ≠ nil). For
example, there is list that has two
nodes:
head tail

2 3

alloc(new)
new 1 new->info= 1
Front Insertion (cont’d)

head tail

2 3

1
new->next=head
new
 Front Insertion (cont’d)

head tail

2 3
head=new

new 1
Front Insertion (cont’d)

new head tail

1 2 3

tail->next= head
Front Insertion (cont’d)
The last result for front insertion if
linked list wasn’t empty:

new head tail

1 2 3
 Back Insertion
• If list is empty (head = nil) 
the

process is same as front

insertion if linked
list is empty.
 Back Insertion (cont’d)
• If list isn’t empty (head ≠ nil). For
example, there is list that has two
nodes:

head tail

2 3
 Back Insertion (cont’d)
New node will be inserted after the node
that was refered by tail.

alloc(new)
new 1 new->info=1
Back Insertion (cont’d)

head tail

2 3 tail->next= new

new 1
 Back Insertion (cont’d)

head tail

3 2 tail= new

new 1

tail->next=head
 Back Insertion (cont’d)
The last result for back insertion if
linked list wasn’t empty:

head tail new

3 2 1
 Middle Insertion

Circular linked list doesn’t give effect

for middle insertion. The algorithm is
same as middle insertion in linear
single or double linked list (depend
on implementation of circular linked
list).
 


DELETION
 Front Deletion
• Delete one node in begining of linked
list if linked list has only one node
(head = tail). tail
head head

loc tail
1 THEN
head  nil
element
tail  nil
loc=head element= loc->info
dealloc(loc)
 Front Deletion (cont’d)
• If linked list has more than one
node (head ≠ tail). For example,
linked list has two nodes.

head tail

2 3
 Front Deletion (cont’d)

head tail
loc 2 3

element
tail->next=head
dealloc(loc)
loc=head
element= loc->info
head =head->next
 Front Deletion (cont’d)
The last result for front deletion if linked
list has more than one node:

head tail
loc 2 3

element
 Back Deletion
• Delete one node in back of linked list if
linked list has only one node (head =
tail).

This process is same as front

deletion if linked list
has only one node.
 Back Deletion (cont’d)
• If linked list has more than one
node (head ≠ tail). For example,
linked list has four nodes.

head tail

2 1 4 3
 Back Deletion (cont’d)

hea loc tail loc

d
2 1 4 3

loc  head element

elemen=tail->info tail =loc
while (loc->next ≠ tail) loc = loc->next
do tail->next=head
loc=loc->next dealloc(loc)
endwhile
 Back Deletion (cont’d)
The last result for back deletion if linked
list has more than one node:

head loc tail loc

2 1 4 3

element
 Other Operation

Other operations of circular linked list are

same

as linear single or double linked list but be

careful of overlooping (endless

looping)because there aren’t null value in

its connection fields.

 Applications of Circular
Linked List
• Circular lists are used in applications where the entire list is
accessed one-by-one in a loop.
• It is also used by the Operating system to share time for
different users, generally uses a Round-Robin time-
sharing mechanism.
• Multiplayer games use a circular list to swap between
players in a loop.
• Implementation of Advanced data structures like
Fibonacci Heap
• The browser cache which allows you to hit the BACK button
• Undo functionality in Photoshop or Word
\