ASSIGNMENT 1 FOR DSPS LAB

NAME OF STUDENT:                                         CLASS:

SEMESTER/YEAR:                                              ROLL NO:

DATE OF PERFORMANCE:                              DATE OF SUBMISSION:

EXAMINED BY:                                                    EXPERIMENT NO:

TITLE : implementation of DOUBLY circular  Linked List

 

AIM: Write a program using object oriented programming features to implement Doubly circular linked list with different manipulation facilities in C++..

OBJECTIVES:

1.     To understand structure of DCLL..

2.     To understand How Create, Insert , Delete , Display.

PRE-REQUISITES:

1.      0Knowledge of C++ programming

2.     Knowledge of array and  Link list

APPARATUS:

THEORY:

What is Doubly Circular Linked List?

Doubly Circular linked list is a linear data structure consists of a group of nodes so as each node is connected or linked to its predecessor node as well as to its successor node.                

A typical node structure of a DLL consists of prev, Data and next.

prev:- It is a pointer variable which points to the predecessor of the current node.

Data:- Actual information to be stored.

next:-It is a pointer variable that points to the successor of the current node.

In the last node of a list, the link next field  contains a HEAD and in first node of a list , the link prev contains a last node reference. A less common convention is to make it point to the first node of the list; in that case the list is said to be circular or circularly linked; otherwise it is said to be open or linear.

                           Doubly Circular Linked List

ALGORITHM:

Create:

1)     Dynamically allocate the memory which returns a pointer first.

2)     If head = null write memory not available.

3)     Else initialize data field , next and prev  field of a node.

4)     Return a pointer of this new node i.e. return (head).

5)     End of Create ( ).

Insert:

Insertion at the front:

1)     Dynamically allocate a node that returns a pointer next.

2)     Initialize the data field , next and prev  field of newly created node.

3)     If head = null (i.e. if list is empty) then return next.

4)     Else attach the next pointer and point the link of next to first.

Link (next) ßfirst node.

Link(prev)<-last node

5)     return (head)

Insertion at the end:

1)     Traverse the list till end.

2)     Create a new node

3)     Attach that node to the end of the list

4)     Give next link of new node to head

Insertion at Between:

1)     Ask for location where you want to enter the new node

2)     Create a new node

3)     Traverse to find the location and add the new node 

4)     Update all links

Delete:

Deletion at the front:

1)     Check for empty list , if head = NULL  then write list is empty.

2)     Check if data(first) = x i.e. if the node to be deleted is the first node

3)     Save the next node as head node

4)     Update the doubly circular link

Deletion at the end:

1)     Traverse the list till end.

2)     Delete last node.

3)     Update the circular link

Deletion at Between:

1)     Ask for data that you want to delete

2)     Traverse to find the entered data

3)     Delete data(Free the location)

4)     Update all links

Count

1)     Initialize any variable with 0 example A=0

2)     Traverse the list till end

3)     Every traversal increment A

4)     Return A

Search

1)     Ask for data that you want to search

2)     Traverse to find the entered data

3)     Return the position

4)     Update all links

Concan

1)     Create second list with head1

2)     Traverse the first list till end

3)     Link-> Next=head1

4)     Head1->prev=last node of first linked list

5)     Return the head

6)     Update all links

CONCLUSION: The DCLL is implemented successfully.

QUESTIONS: 

1. What is difference between CLL & DCLL?

2. How to search the element in DCLL?

3. Write application for  DCLL?