Module-3 Part-1
Linked List(Continued)
Vandana U
Asst. Professor
Dept. of AI/DS
Additional List
Operations
1. Inverting a singly linked list:
listpointer invert(listpointer lead)
{/* invert the list pointed to by lead*/
listpointer middle,trail; CURRENT LIST :
lead
middle= null;
while(lead) 10 20 30 NULL
{
REVERSED LIST :
trail=middle
middle=lead; 10 NULL 20 30
lead=lead->link;
middle->link=trail;
} lead
return middle;
Main Idea:
}
1. The idea is to make last node as the first node.
2. Make the links point in the reverse order.
2. Concatenating singly linked lists:
listpointer concatenate(listpointer ptr1, listpointerptr2)
{ /*produce a new list that contains the list ptr1 followed by the list ptr2. The list pointed to by ptr1 is
changed permanently*/
/*check for empty list*/
if(!ptr1) return ptr2; ptr1
if(!ptr2) return ptr1; 10 20 30 NULL
for(temp=ptr1;temp->link;temp=temp->link);
/*link end of first to start of second*/ ptr2
temp->link=ptr2; 40 50 60 NULL
ptr1
10 20 30 40 50 60 NULL
3). Searching an element from the unsorted list
search(info,link,start,item,loc)
1. set ptr=start
2. repeat step-3 while ptr!=NULL
3. if item=ptr->info then
set loc:= ptr and EXIT
else
ptr=ptr->link
[end of if]
[end of step 2 loop]
4. search is unsuccessful set loc:=NULL
5. EXIT
4). Searching an element from an sorted list
searchsl(info,link,start,item,loc)
1. set ptr=start
2. repeat step-3 while ptr!=NULL
3. if item>ptr->info then
set ptr= ptr->link then
set loc:= ptr and EXIT
else if item=ptr->link then
set loc:= ptr and EXIT
else loc:=NULL and EXIT
[end of if]
[end of step 2 loop]
4. search is unsuccessful set loc:=NULL
5. EXIT
Operations on Circular Linked List:
temp
1. Inserting at the front of the list 50 NULL
NODE insertbeg(int item,NODE last) 500
last
{
NODE temp; Existing List
New Node
temp=(NODE)malloc(sizeof(NODE));
temp 10 200 20 100
500
temp->info=item;
50 NULL
100 100 200
if(last==NULL)
500
last=temp;
return last;
}
2). Finding the length of a Circular List
int length(listpointer last)
{
/*find the length of the circular list last*/
listpointer temp;
int count=0;
if(last)
{
temp=last;
do
{
count++;
temp=temp->link;
}
}
return count;
}
SPARSE MATRIX REPRESENTATON
A linked list representation for sparse matrices.
In data representation, each column of a sparse matrix isrepresented as a circularly linked list with a
header node. A similar representation is used for each row of a sparsematrix. Each node has a tag field,
which is used to distinguish between header nodes and entry nodes.
Header Node:
• Each header node has three fields: down, right, and next as shown in figure (a).
• The down field is used to link into a column list and the right field to link into a row list.
• The next field links the header nodes together.
• The header node for row i is also the header node for column i, and the total number of header
nodes is max {number of rows, number of columns}.
Element node:
• Each element node has five fields in addition in addition to the tag field: row, col, down, right, value
as shown in figure (b).
• The down field is used to link to the next nonzero term in the same column and the right field to link
to the next nonzero term in the same row. Thus, if aij ≠ 0, thereis a node with tag field = entry,
value = aij, row = i, and col = j as shown in figure (c).
• We link this node into the circular linked lists for row i and column j. Hence, it is simultaneously
linked into two different lists.
Consider the sparse matrix, as shown in below figure (2).
Figure (3) shows the linked representation of this matrix. Although we have not shown the value of the
tag fields, we can easily determine these values from the node structure. For each nonzero term of a,
have one entry node that is in exactly one row list and one column list. The header nodes are marked
HO-H3. As the figure shows, we use the right field of the header node list header.
To represent a numRows x numCols matrix with numTerms nonzero terms, then we need max
{numRows, numCols} + numTerms + 1 node. While each node may require several words of memory,
the total storage will be less than numRows x numCols when numTerms is sufficiently small. There are
two different types of nodes in representation, so unions are used to create the appropriate data
structure. The C declarations are as follows:
Module – 3 PART-1
Next part is Doubly Linked List which is already covered in the 2nd module.
THANK YOU
