Page 47 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes printf( “Enter the data values to be placed in a node\n”);
scanf(“%d”,&x);
start = insert ( start, &end,x );
}
printf(“The created list is\n”);
printfor ( start );
printf(“enter the node number after which the new node is to be
inserted\n”);
scanf(“%d”,&n);
printf(“enter the data value to be placed in the new node\n”);
scanf(“%d”,&x);
start=newinsert(start,n,x);
printfor(start);
}

Explanation

1. To insert a new node in a doubly linked chain, it is required to obtain a pointer to the node
in the existing list after which a new node is to be inserted.

2. To obtain this pointer, the node number after which the new node is to be inserted is given
as input. The nodes are assumed to be numbered as 1,2,3,…, etc., starting from the fi rst
node.
3. The list is then traversed starting from the start node to obtain the pointer to the specifi ed
node. Let this pointer be x. A new node is then created with the required data value, and
the right link of this node is made to point to the node to the right of the node pointed to by
x. And the left link of the newly created node is made to point to the node pointed to by x.
The left link of the node which was to the right of the node pointed to by x is made to point
to the newly created node. The right link of the node pointed to by x is made to point to the
newly created node.

Question
Write a program to delete a specific node from the linked list.

2.8 Circular Linked List

Circular Linked List is another remedy for the drawbacks of the Single Linked List besides
Doubly Linked List. A slight change to the structure of a linear list is made to convert it to circular

linked list; link field in the last node contains a pointer back to the first node rather than a Null.
(See Figure 2.6).
Figure 2.6: Circular Linked List

From any point in such a list it is possible to reach any other point in the list. If we begin at a given
node and traverse the entire list, we ultimately end up at the starting point.

42 LOVELY PROFESSIONAL UNIVERSITY