UNIT II

Linked Lists : Introduction to Lists and Linked Lists, Basic Linked List Operations, Doubly
Linked List, Circular Linked List, Linked List versus Arrays.

LINKED LISTS
A linked list or one way list is a liner collection of data elements, called nodes where the linear
order is given by means of references. That is each node is divided into to parts the first part
contains the information of the element and the second part called the link field or next
reference field, contains the address of the next node in the list.

Node
The reference of the last node contains a special value called “NULL” reference
denoted by “ X ” in the diagram signals the end of the list. The linked list also contains a
pointer variable called “START” which refer to the first or head node in the list .
A special case is the list that has no nodes, such list is called the “NULL” list or empty
list and is denoted by null reference in the start variable.

Linked list can be classified as :

1. Singly liked list
2. Doubly linked list
3. Circularly singly linked list
4. Circularly doubly linked list

1. Singly linked list

Here in this type of list the node has only one reference variable apart from the
information part which always refers to the next node. In singly linked list we can
perform only forward traversing. This type of lists is also known as one way list.
 2. Doubly linked list
These types of lists are also known as two way list, which can be traversed in two
directions forward and backward directions. A two list is a collection of data elements
called nodes where each node is divided into three parts
• An information field INFO which contains the data
• A reference field “NEXT” which contains the location of the next node in the list.
• A reference field “PREV” which contains the location of the preceding node in
the list

3. Circularly Singly linked List:

In a singly linked list the last node refers to the first node of the same list, then its form
a cyclic or circle, then this type of list called as Circular Single Linked List.

4. Circularly doubly linked list:

In a double linked list, the end node refer back to the header node and the header
node refers tothe end node, it forms a circle then it is called as Circular Double linked
list.

Advantages of linked lists

1) The primary advantage of linked list over arrays is that linked list can increase and
decrease in size. That means their maximum size need not be mentioned in advance.
This is a very good advantage in practical applications.
2) The second advantage of linked list is the flexibility in allowing the items to the
rearranged efficiently. This flexibility is gained at the experience of quick access to any
item in this.
3) The insertion and deletion of an element takes one time. Unlike array implementation in
which they take n-times.

Limitations of linked lists

1) The space needed to store a list using more.
2) Another limitation is that it is not possible to travel a list in both directions. This can be
over come in double linked list.
 Differences between arrays & linked lists

Arrays Linked List

1. Array is fixed in size. 1. No.of nodes in the list is unlimited.

2. Static allocation of memory is done. 2. Dynamic Memory allocation is done.

3. Use initialized area. 3. Uses free store or heap memory area.

4. Only identical items can be placed. 4. Identical or different items may be

placed.
5. Optimum utilization of memory will 5. Optimum utilization of memory is
not be found. done.
6. Do not use pointers concept. 6. Uses pointers only.
7. Continuous blocks of memory is 7. Doesn’t need continuous memory.
required.

BASIC OPERATIONS ON SINGLE LINKED LISTS

Creating a Linked List

The creation of a list is the most basic operation among other operations.
Algorithm Creation( )
[ Initially head = null and last = null ]
Step-1: Read a value into item
Step-2: if(item = = -1) then
[ end the process ]
Else
Step-2.1 : create a new node called “temp”
Step-2.2 : Insert temp.data = item , temp.link = null.
Step-2.3 : if head = = null then
head = last = temp
else
last.link = temp
last = temp
[ Repeat the process until item = -1 ]
Step-3: Exit
Implementation:

1. Initially head = null and last = null

2. Item=10
3. Since, item != -1 create a new node called temp.

4. temp.data = 10 , temp.link = null

5. since head = null so head = last = temp.

6. item = 20
7. Since, item != -1 create a new node called temp.

8. temp.data = 20 , temp.link = null

9. since head != null so, last.link = temp and last = temp.

10. item=30
11. Since, item != -1 create a new node called temp.

12. temp.data = 30 , temp.link = null

13. since head != null last.link = temp and last = temp.

14. item = -1
15. since item = -1, we will stop the process.
Traversing a Linked List
Visiting each and every node in the list is called traversing.
Algorithm Traverse( )
Step-1 : set temp = head
Step-2 : while temp!=null
Step-2.1 : display temp.data
Step-2.2 : temp=temp.link
Step-3 : Exit

Implementation:
Let us consider the following linked list with four nodes.

1. set temp = head

2. since temp!=null, 10 is visited

3. temp=temp.link

4. since temp!=null, 20 is visited.

5. Now temp=temp.link

6. Since temp!=null, 30 is visited.

7. Now temp=temp.link

8. Since temp!=null, 40 is visited.

9. Now temp=temp.link

10. Since temp=null, the process stops here.

Counting Number of Nodes in a Linked List:
Step-1 : set temp = head , count=0
Step-2 : while temp!=null
Step-2.1 : count=count+1
Step-2.2 : temp=temp.link
Step-3 : Exit

Implementation:
Let us consider the following linked list with four nodes.

1. set temp = head

2. since temp!=null, count=1.

3. temp=temp.link

4. since temp!=null, count=2.

5. Now temp=temp.link

6. Since temp!=null, count=3.

7. Now temp=temp.link

8. Since temp!=null, count=4.

9. Now temp=temp.link
10. Since temp=null, the process stops here.

Inserting
Adding a new node to the existing list is called as inserting. We can insert a node in the
followingthree places.
1. Insertion at head
2. Insertion at last
3. Insertion in between any two nodes.
1. Insertion at head:
If the node is inserted before the head node that node becomes new head of the list.

Algorithm: Insert-At-Head( )
Step-1: Create a new node called temp.
Step-2: Read a value into item.
Step-3: Insert temp.data=item
temp.link=null
Step-4: temp.link=head
head=temp
Step-5: Exit

Implementation:
Let us consider the following the list with four nodes.

1. Create a new node called “temp”

2. Item=5, temp.data=item, temp.link=null.

3. temp.link=headhead=temp

2. Insertion at Last
Algorithm insertAtLast( )
Step-1: Create a new node called “nodex”
Step-2: Read a value into item.
Step-3: Insert nodex.data=item
nodex.link=null
Step-4: set temp=head
step-4.1: while(temp!=null)
temp1=temp
temp=temp.link
step-4.2: if(temp=null)
temp1.link=nodex
last=nodex
Step-5: Exit

Implementation
Let us consider the following the list with four nodes.
 1. create a new node called “nodex”.

2. item=50
3. nodex.data=item , nodex.link=null

4. temp=head

5. since temp!=null , temp1=temp and temp=temp.link

6. since temp!=null , temp1=temp and temp=temp.link

7. since temp!=null , temp1=temp and temp=temp.link

8. since temp!=null , temp1=temp and temp=temp.link

9. since temp=null , temp1.link=nodex , last = nodex.

3. Insertion between any two nodes

In order to insert a new node in between any two nodes we need to traverse until
that node, by keepingtrack of two successive nodes.

Algorithm insertAtMiddle( )
Step-1: Create a new node called “nodex”
Step-2: Read a value into item.
Step-3: Insert nodex.data=item
nodex.link=null
Step-4: Read place to insert into place.
Step-5: set temp=head , i=1
step-5.1: while(i<place)
temp1=temp
temp=temp.linki=i+1
step-5.2: temp1.link=nodex
nodex.link=temp.
Step-6: Exit
Implementation
Let us consider the following the list with four nodes.

1. create a new node called “nodex”.

2. item=25
3. nodex.data=item and nodex.link=null

4. place=3
5. set i=1 and temp=head

6. since 1<3 , temp1=temp , temp=temp.link and i=i+1

7. since 2<3, temp1=temp , temp=temp.link and i=i+1

8. since 3<3 is false , the process stopped here.

9. temp1.link = nodex.

10. nodex.link = temp

Deleting a Node from Single Linked List
Removing a node from the existing node is called as deleting. The deletion operation can
beperformed in following three places.
1. Deleting head node
2. Deleting last node
3. Deleting a node between any two nodes.

1. Deleting head node

If the head node is deleted then the next node will be the head node of the list.
Algorithm deleteHead( )
Step-1: head = head.link
Step-2: Exit

Implementation
Let us consider the following list with four nodes.

1. head = head.link

2. Deleting Last Node

For deleting a last node, we need to traverse until finding last node.
Algorithm deleteLast( )
Step-1: set temp = head
Step-2: while ( temp.link != null )
temp1 = temp
temp = temp.link
Step-3: temp1.link = null
Last=temp1
Step-4: Exit

Implementation
Let us consider the following list with four nodes.

1. temp = head

2. since temp.link != null , temp1 = temp , temp = temp.link

3. since temp.link != null , temp1 = temp , temp = temp.link

 4. since temp.link != null , temp1 = temp , temp = temp.link

5. since temp.link = null , loop stopped here.

6. temp1.link = null , last = temp1

3. Deleting a node in between any two nodes

In order to delete a node, we need to traverse until the node by keep tracking two
successive nodes.

Algorithm deleteMiddle( )
Step-1: Read place to delete into “place”
Step-2: set i=1, temp = head
Step-3: while ( i<place)
temp1 = temp
temp = temp.linki = i + 1
Step-4: temp1.link = temp.link
Step-5: Exit

Implementation
Let us consider the following list with four nodes.

1. place = 3
2. i=1 and temp = head

3. since i < place , temp1 = temp , temp = temp.link , i=i+1 = 2

4. since i < place , temp1 = temp , temp = temp.link , i=i+1 = 3.

5. since 3 < 3 is false, loop stops here.

6. temp1.link = temp.link
Searching an element
Searching means to find the element whether it is exist in the list or not. Here we use two
types of searching mechanism. The linked list is suitable only for linear search mechanism
and it is not suitable for binary search mechanism.

Algorithm search( )
Step-1: set flag=0
Step-2: Read search value into “key”
Step-3: set temp=head
Step-4: while ( temp!=null )if( temp.data = key )
flag=1
break the looptemp = temp.link
Step-5: if ( flag = 1) then
Display “FOUND”
Else
Display “NOT FOUND”
Step-6: Exit

Implementation
Let us consider the following list with four nodes.

1. flag = 0
2. key = 30
3. temp = head

4. since temp ! = null and temp.data ! = key (30) so temp = temp.link

5. since temp != null and temp.data != key (30) so temp = temp.link

6. since temp != null and temp.data = 30 so flag = 1 and loop stops here.
7. Since flag = 1 we conclude that the element was found.
DOUBLE LINKED LIST:
In Double Linked List, each node contains two reference parts. One reference is used to
remember the previous node address and another reference is used to remember the next
node address. The node in double linked list is represented as follows.
Node
Plink Data Nlink
❖ Plink is used to refer the previous node.
❖ Data part contains value of the node.
❖ Nlink is used to refer the next node.

In Double linked list, we need to remember two nodes, one is the first node called “head
node”. The Plink of the head node points to NULL. Another one is last node. The Nlink of
the last node points to NULL. The following is doublelinked list with four nodes.

Hea Nod Nod Las

d e e t
NULL 10 20 30 40
NULL
The single linked list is used for only one way traversing whereas the double linked list is
capable of traversing in both directions, either forward or backward.
For example, if we were at node 55 in a list of 100 nodes and if we want to visit node 51.
If single linked list is used we need to start from the head node and requires 55 moves in
forward direction whereas if the double linked list is used, then we require just 4 moves
backward from the node 55.

OPERATIONS ON DOUBLE LINKED LIST:

Creating a double linked list

The creation of a list is the most basic operation among other operations.
Algorithm create( )
[ initially head=NULL, last=NULL ]
Step1: Read a value into “item”
Step2: if [ item = -1 ] then
[ break the loop ]
else
Step2.1: Create a node called “temp”
Step2.2: Insert temp.data=item
temp.plink=NULL
temp.nlink=NULL
Step2.3: if head = = NULL, then
head = last = temp
else
last.nlink = temp
temp.plink = lastlast=temp
[ Repeat the process until item = -1 ]
Step3: Exit
Implementation
1. Initially head=NULL, last=NULL
2. Item=10
3. Since item!= -1, so
4. Create a new node called temp

5. temp.data=10, temp.nlink=NULL, temp.plink=NULL

6. since head = last = NULL, then head = last = temp

7. item=20
8. since item!= -1, so
9. create a new node called temp

10. temp.data=20, temp.plink = NULL, temp.nlink = NULL

11. since head!= NULL ; so, last.nlink = temp ; temp.plink = last ; last = temp

12. item=30
13. since item != -1, so
14. create a new node called temp

15. temp.data=30 ; temp.plink = NULL ; temp.nlink = NULL

16. since head != NULL. So, last.nlink = temp ; temp.plink = last ; temp = last

17. item = -1
18. since item = -1, so the process stops.
TRAVERSING A DOUBLE LINKED LIST
Traversing means visiting each and every node. A double linked list can be traversed in two
ways. They are
1. forward direction – from head to last
2. backward direction – from last to head

1. Traverse in Forward Direction:

Algorithm: Traverse Forward( )
Step1: set temp = head
Step2: while temp != NULL
Step2.1: display temp.data
Step2.2: temp = temp.nlink
Step3: exit

Implementation:
1. let us consider the following list with four nodes.

2. set temp = head

3. since, temp != NULL so 10 is visited.

4. Set temp = temp.nlink

5. Since temp != NULL. So 20 is visited

6. Set temp = temp.nlink

7. Since temp != NULL. So 30 is visited

8. Set temp = temp.nlink

9. Since temp != NULL. So 40 is visited.

10. Set temp = temp.nlink
11. Since temp = NULL, The process is stopped.

2. Traverse in Backward Direction

Algorithm Traverse Backward( )
Step1: set temp=last
Step2: while temp != NULL
Step2.1: display temp.data
Step2.2: temp = temp.plink
Step3: exit
 Implementation
1. Let us consider the following list with 4 nodes.

2. Set temp = last

3. Since temp != NULL. So, 40 is visited.

4. Set temp = temp.plink

5. Since temp != NULL. So, 30 is visited

6. Set temp = temp.plink

7. Since, temp != NULL. So, 20 is visited

8. Set temp = temp.plink

9. Since temp != NULL. So, 10 is visited

10. Set temp = temp.plink
11. Since temp = NULL. The process is stopped.

INSERTING A NODE IN DOUBLE LINKED LIST

The insertions can be done in the following three situations.
1. Inserting at head
2. Inserting at last
3. Inserting between nodes

1. Inserting at head
If a node is inserted before a head node that node becomes the new head of the list.
Algorithm insertAtHead( )
Step1: Create a new node called “temp”
Step2: Read a value into “item”
Step3: Insert,
temp.data = item
temp.nlink = NULL
temp.plink = NULL
Step4: temp.nlink = head
head.plink = temp
head = temp
Step5: Exit
 Implementation:
1. Let us consider the list with following 4 nodes.

2. Create a new node called temp.

3. Item = 5

4. temp.data= item ; temp.nlink = NULL ; temp.plink = NULL

5. temp.nlink = head ; head.plink = temp ; head = temp

2. Inserting at Last:

Algorithm insertAtLast( )
Step1: Create a new node called “temp”.
Step2: Read a value into “item”
Step3: Insert, temp.data = item
temp.plink = NULL
temp.nlink = NULL
Step4: last.nlink = temp
temp.plink = last
last = temp
Step5: Exit

Implementation
1. Let us consider the list with following 4 nodes.

2. Create a new node called temp.

3. Item = 50
4. temp.data= item ; temp.nlink = NULL ; temp.plink = NULL

5. temp.plink = last ; temp.nlink=NULL ; last = temp

3. Inserting between any two nodes:
Algorithm insertAtMiddle( )
Step1: Create a new node called “nodex”
Step2: Read a value into item
Step3: Insert nodex.data=item
nodex.plink=NULL
nodex.nlink=NULL
Step 4: Read place to insert into place
Step 5: set i=1, temp=head
Step 6: while (i<place)
Step 6.1: temp 1 = temp
Step 6.2: temp = temp.nlink
Step 6.3: i=i+1
Step 7: temp1.nlink = nodex, nodex.plink = temp1.
Step 8: nodex.nlink=temp, temp.plink = nodex
Step 9: Exit

Implementation
1. Let us consider the following lists with four nodes.

2. Create a new node called “nodex”

3. item=25
4. nodex.data = item , nodex.nlink = NULL , nodex.plink = NULL

5. place = 3
6. set i=1, temp = head

7. a. since 1<3, so temp1 = temp, temp = temp.nlink i = i + 1

b. since 2<3 , so temp1 = temp , temp = temp.nlink i = i + 1

c. since 3<3 is false , so the process stopped.

 8. temp1.nlink = nodex , nodex.plink = temp1

9. nodex.nlink = temp , temp.plink = nodex

Deleting a Node in a Double Linked List

The deletion of a node can be done in the following 3 situations.
1. Deleting a head node
2. Deleting a last node
3. Deleting a node in between two nodes.

1. Deleting a Head Node:

If a head node is deleted, then the next node becomes the new node of the list and its
previous linkshould points to NULL.
Algorithm deleteHead( )
Step 1: Set head = head.nlink
Step 2: set head.plink = NULL.
Step 3: Exit

Implementation

1. Let us consider the following list with four nodes.

2. head = head.nlink

3. head = head.plink = NULL

2. Deleting a last Node:
If the last node is deleted, the previous node of the last node will become the new last
node of the list and thenlink of that node should point to NULL.
Algorithm deleteLast( )
Step 1: set last = last.plink
Step 2: last.nlink = NULL
Step 3: Exit

Implementation
1. let us consider the following list of 4 nodes.

2. last = last.plink

3. last.nlink = NULL

3. Deleting a node between any two nodes

In order to delete a node, we need to traverse until the node by tracking two successive
nodes.
Algorithm deleteMiddle( )
Step 1: Read place to delete into “place”.
Step 2: set i=1, temp = head
Step 3: while (I < = place-1)
Step 3.1: temp1 = temp
Step 3.2: temp = temp.nlink
Step 3.3: i = i + 1
Step 4: temp = temp.nlink
Step 5: temp1.nlink = temp
Step 6: temp.plink = temp1
Step 7: Exit

Implementation
1. Let us consider the following list with 4 nodes.

2. Place = 3
3. i = 1 , temp = head
 4. a. since, 1<=2. So, temp1 = temp , temp = temp.nlink , i = i + 1

b. since 2<=2, so, temp1 = temp , temp = temp.nlink , i=i+1

c. since 3<=2 is false, the loops stops here.

5. temp = temp.nlink

6. temp1.nlink = temp , temp.plink = temp1.

CIRCULAR LINKED LIST:

In a circular linked list, there is no beginning and there is no ending. In a circular linked list,
the reference part of the last node which means the last node points back to the first node.
There is no NULLreference in the circular linked list.
If there is a single node in the circular linked list, it points back to itself.

The following is the circular linked list with four nodes.

If it is a double linked list, the nlink of the last node refers to the head node and the plink
of the head node refers to the last node. The following is circular double linked with five
nodes.

Header Linked List:

In a circular linked list, there is no beginning and there is no ending. So, while traversing a
list we face aproblem because there is no NULL reference termination.
In order to solve this problem, we include the dummy reference is called “header”. The
following is the header linked list with four nodes.
Array VS. LinkedList
ARRAY LINKED LIST
1. An array is a collection of elements having 1. Linked List is an ordered collection of
same data type with common name. elements which are connected by
links or pointers.
2. In Array, elements can be accessed using 2. In Linked List, elements can be
index or subscript value i.e., elements can accessed accesses sequentially and
be accessed randomly. So array provides accessing element takes order of n
fasterrandom access. O(n) times.

3. In Array, elements are stored in consecutive 3. In Linked List, elements can be

memory locations. stored at any available place as
address of node is stored in previous
4. Insertion & Deletion takes more time in array node.
as elements are stored in consecutive 4. Insertion & Deletions are fast and
memory locations. easy in linked list as only value of
pointer is needed to change.
5. In Array memory is allocated at compile time 5. In Linked List memory is allocated at
i.e., static memory allocation. runtime i.e., Dynamic Memory
Allocation.
6. Array can be single dimensional, two 6. Linked List can be single, double or
dimensional or multi dimensional. circular linked list.
7. In Array each element is independent, no 7. In Linked List location or address is
connection with previous element or with its stored in the link part of previous
location. element or node.
8. In Array no pointers are used like linked list. 8. In Linked List, adjacency between
So, no need of extra space in memory for the elements are maintained using
pointer. pointers or links. So pointers are
used for that extra memory space is
needed.

Advantages using linked lists over arrays

1. Linked lists provide flexibility in allowing items to be rearranged efficiently.
2. It is easier to insert or delete items by rearranging the links.
3. It provides polynomial manipulations.
4. It allows dynamic memory allocation.
5. It allows performing additions and subtractions multiplications on large sizenumbers.
6. It provides implementations for the symbol table in compiler construction.
SPARSE MATRIX MATRIX
In computer programming, a matrix can be defined with a 2-dimensional array. Any array with
'm' columns and 'n' rows represents a mXn matrix. There may be a situation in which a matrix
contains more number of ZERO values than NON-ZERO values. Such matrix is known as
sparse matrix, i.e Sparse matrix is a matrix which contains very few non-zero elements. When
a sparse matrix is represented with 2-dimensional array, we waste lot of space to represent
that matrix. For example, consider a matrix of size 100 X 100 containing only 10 non-zero
elements. In this matrix, only 10 spaces are filled with non-zero values and remaining spaces
of matrix are filled with zero. That means, totally we allocate 100 X 100 X 4 = 40000 bytes of
space to store this integer matrix. And to access these 10 non- zero elements we have to
make scanning for 10000 times.

Sparse Matrix Representations A sparse matrix can be represented by using TWO

representations,
They are
1. Triplet Representation
2. Linked Representation

1. Triplet Representation
In this representation, we consider only non-zero values along with their row and
column index values. In this representation, the 0th row stores total rows, total
columns and total non- zero values in the matrix. For example, consider a matrix of size
5 X 6 containing 6 number of non- zero values. This matrix can be represented as

shown in the fig:

In above example matrix, there are only 6 non-zero elements ( those are 9, 8, 4, 2, 5 &
2) and matrix size is 5 X 6. We represent this matrix as shown in the above image.
Here the first row in the right side table is filled with values 5, 6 & 6 which indicates that
it is a sparse matrix with 5 rows, 6 columns & 6 non-zero values. Second row is filled
with 0, 4, & 9 which indicates the value in the matrix at 0th row, 4th column is 9. In the
same way the remaining non-zero values also follows the similar pattern.

2. Linked Representation
In linked representation, we use linked list data structure to represent a sparse matrix.
In this linked list, we use two different nodes namely header node and element node.
Header node consists of three fields and element node consists of five fields as shown
in the image...
 Consider the above same sparse matrix used in the Triplet representation. This sparse
matrix can be represented using linked representation as shown in the below image...

In above representation, H0, H1,...,H5 indicates the header nodes which are used to
represent indexes. Remaining nodes are used to represent non-zero elements in the matrix,
except the very first node which is used to represent abstract information of the sparse matrix
(i.e., It is a matrix of 5 X 6 with 6 non-zero elements).

In this representation, in each row and column, the last node right field points to it's
respective header node.
LAB PROGRAMS

1. Program on Singly Linked List

#include<stdio.h>
#include<stdlib.h>
struct Node;
typedef struct Node * PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node
{
int e;
Position next;
};
void Insert(int x, List l, Position p)
{
Position TmpCell;
TmpCell = (struct Node*) malloc(sizeof(struct Node));
if(TmpCell == NULL)
printf("Memory out of space\n");
else
{
TmpCell->e = x;
TmpCell->next = p->next;
p->next = TmpCell;
}
}
int isLast(Position p)
{
return (p->next == NULL);
}

Position FindPrevious(int x, List l)

{
Position p = l;
while(p->next != NULL && p->next->e != x)
p = p->next;
return p;
}
void Delete(int x, List l)
{
Position p, TmpCell;
p = FindPrevious(x, l);

if(!isLast(p))
{
TmpCell = p->next;
p->next = TmpCell->next;
free(TmpCell);
}
else
printf("Element does not exist!!!\n");
}
void Display(List l)
{
printf("The list element are :: ");
Position p = l->next;
while(p != NULL)
{
printf("%d -> ", p->e);
p = p->next;
}
}

void Merge(List l, List l1)

{
int i, n, x, j;
Position p;
printf("Enter the number of elements to be merged :: ");
scanf("%d",&n);

for(i = 1; i <= n; i++)

{
p = l1;
scanf("%d", &x);
for(j = 1; j < i; j++)
p = p->next;
Insert(x, l1, p);
}
printf("The new List :: ");
Display(l1);
printf("The merged List ::");
p = l;
while(p->next != NULL)
{
p = p->next;
}
p->next = l1->next;
Display(l);
}

int main()
{
int x, pos, ch, i;
List l, l1;
l = (struct Node *) malloc(sizeof(struct Node));
l->next = NULL;
List p = l;
printf("LINKED LIST IMPLEMENTATION OF LIST ADT\n\n");
do
{
printf("\n\n1. INSERT\t 2. DELETE\t 3. MERGE\t 4. PRINT\t 5. QUIT\n\nEnter the choice :: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
 p = l;
printf("Enter the element to be inserted :: ");
scanf("%d",&x);
printf("Enter the position of the element :: ");
scanf("%d",&pos);
for(i = 1; i < pos; i++)
{
p = p->next;
}
Insert(x,l,p);
break;
case 2:
p = l;
printf("Enter the element to be deleted :: ");
scanf("%d",&x);
Delete(x,p);
break;
case 3:
l1 = (struct Node *) malloc(sizeof(struct Node));
l1->next = NULL;
Merge(l, l1);
break;
case 4:
Display(l);
break;
}
}
while(ch<5);
return 0;
}
OUTPUT

LINKED LIST IMPLEMENTATION OF LIST ADT

1. INSERT 2. DELETE 3. MERGE 4. PRINT 5.
QUIT Enter the choice :: 1
Enter the element to be inserted
:: 10 Enter the position of the
element :: 1

1. INSERT 2. DELETE 3. MERGE 4. PRINT 5.

QUIT Enter the choice :: 1
Enter the element to be inserted
:: 20 Enter the position of the
element :: 2

1. INSERT 2. DELETE 3. MERGE 4. PRINT 5.

QUIT Enter the choice :: 1
Enter the element to be inserted
:: 30 Enter the position of the
element :: 3

1. INSERT 2. DELETE 3. MERGE 4. PRINT 5.

QUIT Enter the choice :: 4
The list element are :: 10 -> 20 -> 30 ->

1. INSERT 2. DELETE 3. MERGE 4. PRINT 5.

QUIT Enter the choice :: 5
2. Program on Doubly Linked List

#include<stdio.h>
#include<stdlib.h>
struct Node;
typedef struct Node * PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

struct Node
{
int e;
Position previous;
Position next;
};

void Insert(int x, List l, Position p)

{
Position TmpCell;
TmpCell = (struct Node*) malloc(sizeof(struct Node));
if(TmpCell == NULL)
printf("Memory out of space\n");
else
{
TmpCell->e = x;
TmpCell->previous = p;
TmpCell->next = p->next;
p->next = TmpCell;
}
}

int isLast(Position p)
{
return (p->next == NULL);
}

Position Find(int x, List l)

{
Position p = l->next;
while(p != NULL && p->e != x)
p = p->next;
return p;
}

void Delete(int x, List l)

{
Position p, p1, p2;
p = Find(x, l);
if(p != NULL)
{
p1 = p -> previous;
p2 = p -> next;
p1 -> next = p -> next;
if(p2 != NULL) // if the node is not the last node
p2 -> previous = p -> previous;
 }
else
printf("Element does not exist!!!\n");
}

void Display(List l)
{
printf("The list element are :: ");
Position p = l->next;
while(p != NULL)
{
printf("%d -> ", p->e);
p = p->next;
}
}

void main()
{
int x, pos, ch, i;
List l, l1;
l = (struct Node *) malloc(sizeof(struct Node));
l->previous = NULL;
l->next = NULL;
List p = l;
printf("DOUBLY LINKED LIST IMPLEMENTATION OF LIST ADT\n\n");
do
{
printf("\n\n1. INSERT\t 2. DELETE\t 3. FIND\t 4. PRINT\t 5. QUIT\n\nEnter the choice :: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
p = l;
printf("Enter the element to be inserted :: ");
scanf("%d",&x);
printf("Enter the position of the element :: ");
scanf("%d",&pos);
for(i = 1; i < pos; i++)
{
p = p->next;
}
Insert(x,l,p);
break;

case 2:
p = l;
printf("Enter the element to be deleted :: ");
scanf("%d",&x);
Delete(x,p);
break;

case 3:
p = l;
printf("Enter the element to be searched :: ");
scanf("%d",&x);
 p = Find(x,p);
if(p == NULL)
printf("Element does not exist!!!\n");
else
printf("Element exist!!!\n");
break;

case 4:
Display(l);
break;
}
}
while(ch<5);
}

OUTPUT

DOUBLY LINKED LIST IMPLEMENTATION OF LIST ADT

1. INSERT 2. DELETE 3. FIND 4. PRINT 5.

QUIT Enter the choice :: 1
Enter the element to be inserted
:: 10 Enter the position of the
element :: 1

1. INSERT 2. DELETE 3. FIND 4. PRINT 5.

QUIT Enter the choice :: 1
Enter the element to be inserted
:: 20 Enter the position of the
element :: 2

1. INSERT 2. DELETE 3. FIND 4. PRINT 5.

QUIT Enter the choice :: 1
Enter the element to be inserted
:: 30 Enter the position of the
element :: 3
1. INSERT 2. DELETE 3. FIND 4. PRINT 5. QUIT

Enter the choice :: 4

The list element are :: 10 -> 20 -> 30 ->

1. INSERT 2. DELETE 3. FIND 4. PRINT 5.

QUIT Enter the choice :: 3
Enter the element to be searched
:: 20 Element exist!!!

1. INSERT 2. DELETE 3. FIND 4. PRINT 5. QUIT

Enter the choice ::5

Unit II
IMPORTANT QUESTIONS
1.What is linked list ? Explain about arrays and linked lists ?
2.Write about the types of linked lists ?
3.Explain the operations on Single Linked Lists ?
4.Explain the operations on Doubly Linked Lists ?
5.Explain the differences between Arrays and Linked Lists ?
6.Write a program on single linked list ?
7.Write a program on Doubly Linked list ?