Doubly Linked List
This lab teaches you the following topics:
- Creation of doubly linked list
- Insertion in doubly linked list
- Deletion from doubly linked list
- Traversal of all nodes
For a complete detail about doubly linklist
Introduction
A doubly-linked list is a (dynamically allocated) list where the nodes feature two relationships: successor and predecessor. A model of such a list is given in figure 4.1. The type of a node in a doubly-linked list may be defined as follows:
typedef struct node_type
{
KeyT key; /* optional */
ValueT value ;
/* pointer to next node */
struct node_type *next ;
/* pointer to previous node */
struct node_type *prev;
} NodeT;
As we have seen when discussing singly-linked lists, the main operations for a doubly- linked list are:
- creating a cell;
- accessing a cell;
- inserting a new cell;
- deleting a cell;
- deleting the whole
Lab Activities:
Activity 1:
Creation of doubly linked list
Solution:
In what follows we shall assume that the list is given by a pointer to its header cell, i.e.
/* header cell */
struct list_header
{
NodeT * first ;
NodeT * last ;
};
/* list is defined as a pointer to its header */
struct list_header *L;
Creating a Doubly Linked List
We shall take the list to be initially empty, i.e.
L−>first = L−>last = NULL;
After allocating space for a new node and filling in the data (the value field), insertion of this node, pointed by p, is done as follows:
i f ( L−>f i r st == NULL )
{
/* empty list */
L−>f i r st = L−>last = p;
p−>next = p−>prev = NULL;
}
else
{ /* nonempty list*/
L−>last−>next = p;
p−>prev= L−>last ;
L−>last= p;
}
Activity 2:
Accessing nodes of doubly linked list
Solution:
Stating at a certain position (i.e. at a certain node) we can access a list:
- In sequential forward direction
for ( p = L−>f i r s t ; p != NULL; p = p−>next )
{
/* some operation on current cell */
}
- In sequential backward direction
for ( p = L−>last ; p != NULL; p−>p−>prev )
{
/* some operation on current cell */
}
Activity 3:
Inserting node in doubly linked list
Solution:
We can insert a node before the first node in a list, after the last one, or at a position specified by a given key:
- before the first node:
i f ( L−>f i r st == NULL )
{
/* empty l i s t */
L−>f i r st = L−>last = p;
p->next = p−>prev = NULL;
}
else
{
/* nonemp ty l i s t*/
p−>next= L−>f i r st ;
p−>prev= NULL;
L−>f irst−>prev= p;
L−>f i r s t = p;
}
- after the last node:
i f ( L−>f i r st == NULL )
{ /* empty l i s t */
L−>f i r st = L−>last = p;
p_>next = p−>prev = NULL;
}
else
{ /* nonempty list*/
p−>next= NULL;
p−>prev= L−>last ;
L−>last−>next = p;
L−>last = p;
}
- After a node given by its key:
p−>prev = q;
p−>next = q−>next ;
i f ( q−>next != NULL )
q−>next−>prev = p;
q−>next = p;
i f ( L−>last == q )
L−>last = p;
Here we assumed that the node with the given key is present on list L and it we found it and placed a pointer to it in variable q.
Activity 4:
Deletion from doubly linked list
Solution:
When deleting a node we meet the following cases:
- Deleting the first node:
p = L−>first ;
L−>first = L−>first −>next ; /* nonempty l i s t assumed */
free ( p ) ; /* release memory taken by node */
i f ( L−>first == NULL )
L−>last == NULL; /* list became empty */
else
L−>f irst −>prev = NULL;
- Deleting the last node:
p = L−>last ;
L−>last = L−>last−>prev; /* nonempty list assumed */
i f ( L−>last == NULL )
L−>first = NULL; /* list became empty */
else
L−>last−>next = NULL;
free ( p ) ; /* release memory taken by node */
- Deleting a node given by its We will assume that the node of key givenKey exists and it is pointed to by p (as a result of searching for it)
i f ( L−>f i r st == p && L−>last == p )
{
/* list has a single node */
L−>first = NULL;
L−>last = NULL; /* list became empty */
free ( p ) ;
}
else
i f ( p == L−>first )
{ /* deletion of first node */
L−>first = L−>first −>next ;
L−>first −>prev =NULL;
free ( p ) ;
}
else
{ /* deletion of an inner node */
p−>next−>prev = p−>prev;
p−>prev−>next = p−>next ;
free ( p ) ;
}
Activity 5:
Deleting complete doubly linked list
Solution:
Deleting a list completely means deleting each of its nodes, one by one.
NodeT *p;
while ( L−>first != NULL )
{
p = L−>first ;
L−>first = L−>first −>next ;
free ( p ) ;
}
L−>last = NULL;
Home Activities:
- Write a function which reverses the order of a doubly linked list.
- Write a function which rearranges the linked list by group nodes having even numbered and odd numbered value in their data part.
- Write a function which takes two values as input from the user and searches them in the If both the values are found, your task is to swap both the nodes in which these values are found. Note, that you are not supposed to swap values.
Related links
Single link list Stack AVL Trees Binary search Counting Sort
Doubly link list Queue Graphs Bubble Sort Radix sort
Circular link list Binary search tree Hashing Insertion Sort Bucket Sort
Josephus Problem Tree Traversal Heaps Quick Sort Merge Sort
At Cui tutorial, courses, past papers and final year projects
#tutorial #cui #pastpaper #courses
