0% found this document useful (0 votes)
6 views19 pages

DSA Notes Module 3

This document provides an overview of linked lists, detailing their advantages over arrays, types of linked lists, and their implementation in C. It discusses the structure of linked lists, including singly linked lists, doubly linked lists, circular linked lists, and operations such as insertion, deletion, traversal, and searching. Additionally, it covers the dynamic memory allocation for linked lists and their application in implementing queues.

Uploaded by

aryankrishna1025
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
6 views19 pages

DSA Notes Module 3

This document provides an overview of linked lists, detailing their advantages over arrays, types of linked lists, and their implementation in C. It discusses the structure of linked lists, including singly linked lists, doubly linked lists, circular linked lists, and operations such as insertion, deletion, traversal, and searching. Additionally, it covers the dynamic memory allocation for linked lists and their application in implementing queues.

Uploaded by

aryankrishna1025
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 1

Module 3
Linked Lists
Linked Lists: Singly Linked, Lists and Chains, Representing Chains in C, Linked Stacks and Queues,
Polynomials, Additional List Operations, Sparse Matrices, Doubly Linked List.

3.1 Introduction to Linked List


In this chapter, the list data structure is presented. This structure can be used as the basis for the
implementation of other data structures (stacks, queues etc.). The basic linked list can be used
without modification in many programs. However, some applications require enhancements to the
linked list design. These enhancements fall into three broad categories and yield variations on
linked lists that can be used. Linked lists are built to overcome the disadvantages of arrays
The disadvantages of arrays are:
• The size of the array is fixed. Most often this size is specified at compile time. This makes
the programmers to allocate arrays, which seems "large enough" than required.
• Inserting new elements at the front is potentially expensive because existing elements need
to be shifted over to make room.
• Deleting an element from an array is not possible. Linked lists have their own strengths and
weaknesses, but they happen to be strong where arrays are weak. Generally, arrays allocate
the memory for all its elements in one block whereas linked lists use an entirely different
strategy.
• Linked lists allocate memory for each element separately and only when necessary.

DEFINITION : A linked list, or one-way list, is a linear collection of data elements, called
nodes, where the linear order is given by means of pointers. That is, each node is divided into
two parts:
• The first part contains the information of the element, and
• The second part, called the link field or next pointer field, contains the address of the
next node in the list.

Disadvantages of Arrays

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 2

• The size of the array is fixed. Most often this size is specified at compile time. This
makes the programmers to allocate arrays, which seems "large enough" than required.
• Inserting new elements at the front is potentially expensive because existing elements
need to be shifted over to make room.
• Deleting an element from an array is requires a lot of data movement and is time
consuming.
• Linked lists have their own strengths and weaknesses, but they happen to be strong where
arrays are weak. Generally, arrays allocate the memory for all its elements in one block
whereas linked lists use an entirely different strategy (as and when required).
• Linked lists allocate memory for each element separately and only when necessary.

3.2 Advantages of linked lists

• Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution
of a program.
• Linked lists have efficient memory utilization. Here, memory is not pre-allocated.
Memory is allocated whenever it is required and it is de-allocated (removed) when it is no
longer needed.
• Insertion and Deletions are easier and efficient. Linked lists provide flexibility in
inserting a data item at a specified position and deletion of the data item from the given
position.
• Many complex applications can be easily carried out with linked lists.
Disadvantages
• It consumes extra space because every node requires a additional pointer to store address
of the next node.
• Searching a particular element in list is difficult and also time consuming.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 3

3.3 TYPES OF LINKED LISTS

Basically, linked lists are classified into four type:


i) A Single linked list is one in which all nodes are linked together in some sequential
manner. Hence, it is also called as linear linked list.

ii) A double linked list is one in which all nodes are linked together by multiple links which
helps in accessing both the successor node (next node) and predecessor node (previous
node) from any arbitrary node within the list. Therefore each node in a double linked list
has two link fields (pointers) to point to the left node (previous) and the right node (next).
This helps to traverse in forward direction and backward direction.

iii) A circular linked list is one, which has no beginning and no end. A single linked list can
be made a circular linked list by simply storing address of the very first node in the link
field of the last node.

iv) A circular double linked list is one, which has both the successor pointer and predecessor
pointer in the circular manner.

3.4 REPRESENTING SLL IN C LANGUAGE / MEMORY ALLOCATION

Singly linked lists are the basic type of linked lists where each node has exactly one pointer field.
A singly linked list is comprised of zero/ more number of nodes when the number of nodes is zero,
the list is empty otherwise if the linked list is non-empty, the list is pictorially represented as 1st
node links to 2nd node and 2nd node links to 3rd node and so on. The last node has zero link whose
value of address is set to NULL.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 4

The following features are used to represent SLL. Use the following 3 steps to create a SLL.
i) Define node’s structure
To define a node, self-referential structures are used

ii) Create a new node malloc( ) or MALLOC macro is used to allocate memory for the
defined structures nodes of the size needed for structure node considered.

iii) Removal of nodes


At any point if the allocated nodes are not in use, they are removed by free().
Example: To create a linked list of words following the above steps follow the steps given below.
1. Defining a node: Using self-referential structures nodes are created. for a list of words, in every
node the data field should store words, so define datatype accordingly. The following structure
declaration defines a linked list node:

struct node
{
long int phno; NULL
char name[20];
struct node *next;
} *first=NULL

typedef struct node NODE;

This definition will result into a node by name NODE containing char data field of size 4 and a
field by name NEXT, which is a pointer variable of type list pointer, where list pointer is a pointer
to whole structure.
2. Create a new empty list :
NODE *first=NULL;
Here, first is a variable of type pointer i.e. NODE pointer, initially making it as NULL and hence,
a new list is created by name first and it is empty, To create a new node in list, malloc()
function is used.
temp = (struct node *)malloc(sizeof(struct node));

3. To assign the value to the fields of the node. Here, the operator → is used, which is referred
as the structure member operator.
printf("\nName:"); gets(name);
printf("\nPhone Number:"); scanf("%ld",&ph);
strcpy(temp->name,name);
temp->phone=ph;
temp->next=NULL;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 5

void create()
{
long int ph;
char name[20];
temp=(struct node *)malloc(sizeof(struct node));

printf("\nName:"); gets(name);
printf("\nPhone Number:"); scanf("%ld",&ph);

strcpy(temp->name,name);
temp->phone=ph;
temp->next=NULL;
count++;
}

4. When the node is not required, it can be released using following statement
free(temp);
• When the memory is allocated to the linked lists, a special list is maintained which consists
of unused memory cells. This list, which has its own pointer, is called the list of available
space/ the free storage list or the free pool. Thus, the memory is allocated from free pool.
• When node is deleted from a list or a entire list is deleted from a program, the memory
space has to be inserted into free storage list, so that it will be reusable.
• The operating system of a computer may periodically collect all the deleted space onto the
free storage list. Any technique which does this collection is called garbage collection.
Garbage collection usually takes place in 2 steps:
i. The computer runs through all list, tagging those cells which are currently in use and then the
computer runs through the memory, collecting all untagged space onto the free – storage list.
ii. The garbage collection may take place when there is only some minimum amount of space or
no space at all left in the free-storage list or when the CPU is idle and has time to do the collection.
The garbage collection is invisible to the programmer.
The implementation of a linked list involves two tasks:
• Declaring the list node
• Implementing the linked list operations
a. Insert b. Delete c. Search d. Print/Traversal
a. INSERTION : Insertion operation is used to insert new node to the list created. This operation
is performed depending on many scenarios of linked lists like:
➢ If the linked list is empty, then new node after insertion becomes the first node.
➢ If the list already contains nodes the new node is attached either at front end of the list or
at the last end.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 6

➢ If the insertion is based on the data element/position, then search the list to find the
location and then insert the new node.
NOTE: Same conditions are checked for deleting a node from the list as well.
void insertFront() void insertRear()
{ {
create(); create();
if(first==NULL) if(first==NULL)
{ {
first=temp; first=temp;
last=first; last=first;
} }
else else
{ {
temp->next=first; last->next=temp;
first=temp; last=temp;
} }
count++; count++;
} }

b. LIST NODE DELETION : While deleting a node from the linked list, three conditions
needs to be checked:
* When first == NULL indicates empty linked list
* When first->next == NULL indicates Linked List contains only a single node,
otherwise linked list contains more elemens.
void deletefront() void deleteRear()
{ {
temp=first; temp=first;
if(first==NULL) { if(first==NULL){
printf("\n list is empty"); printf("\n list is empty");
return; return;
} }
if(temp->next==NULL) { if(temp->next==NULL){
printf("The deleted node is \n"); printf("The deleted node is \n");
printf("%s\t%ld",temp->name, printf("%s\t %ld",temp->name,
temp->phone); temp->phone);
free(temp); free(temp);
first=NULL; first=NULL;
} }
else else
{ {
first=temp->next; while(temp->next!=last)
printf("The deleted node is \n"); temp=temp->next;
printf("%s\t %ld",temp->name, printf("The deleted node is \n");
temp->phone); printf("%s\t %ld",last->name,
free(temp); last->phone);
} free(last);
count--; last=temp;
} // end of function last->next=NULL;
}
count--;
}

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 7

c. TRAVESING/PRINTING THE LIST : To print the data fields of the nodes in a list. First print
the contents of first‘s data field. Then, replace first with the address in its link field. So, continue
printing out the data field and moving to the next node until end of the list is reached.
void display()
{
if(first==NULL)
{ printf("\n list is empty"); return;}
else {
temp=first;
printf("The node is \n");
while(temp!=NULL)
{
printf("%s:%ld---> ",temp->name, temp->phone);
temp=temp->next;
}
printf("NULL\n"); }
}
d. SEARCHING
• Searching operation performs the process of finding the node containing the desired value
in linked list.
• Searching starts from the first node of the linked list, so that the complete linked list can
be searched to find the element. if found search is successful, else unsuccessful.
void search(NODE snode)
{
if(first==NULL)
{
printf("\n list is empty");
return;
}
else {
temp=first;
printf("The node is \n");
while(temp!=NULL)
{
if(strcmp(temp->name, snode->name)==0){
printf("%s %ld found ",temp->name, temp->phone);return;
}
temp=temp->next;
}
printf("Not found\n"); }
}
➢ C function to count number of nodes in SLL
int countNode(NODE *first)
{ int c=0;
NODE * temp=first;
if(first==NULL)
{printf("\nlist is empty"); return 0;}
while(temp!=NULL)

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 8

{
c=c+1;
temp=temp->NEXT;
}
printf("Node Count =%d",c);
return c;
}
➢ Function to concatenate two Lists
void concatenate(NODE *a, NODE *b)
{
NODE * temp=a;
if( a != NULL && b!= NULL )
if (a->NEXT == NULL)
a->NEXT = b;
else {
while(temp->NEXT!=NULL)
temp=temp->NEXT;
temp->NEXT = b;
}
else
printf("Either a or b is NULL\n");
}

➢ Function to concatenate two Lists using recursion


void concatenate(NODE *a, NODE *b)
{
if( a != NULL && b!= NULL )
if (a->next == NULL)
a->next = b;
else
concatenate(a->next,b);
else
printf("Either a or b is NULL\n");
}

Reverse a linked list


void reverse(NODE *first)
{
NODE *temp = first, *prev = NULL, *next = NULL;
while (temp != NULL) {
next = temp->NEXT; // Store next
temp->NEXT = prev; // Reverse

// Move pointers one position ahead.


prev = temp;
temp = next;
}
first = prev;
}

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 9

3.5 Linked List Implementation of Queues


• The linked implementation of queues involves dynamically allocating memory space at run
time while performing queue operations.
• Since, the allocation of memory space is dynamic, the queue consumes only that much amount
of space as is required for holding its data elements.
• This is contrary to array implemented queues which continue to occupy a fixed memory space
even if there are no elements present. Thus, linked implementation of queues based on
dynamic memory allocation technique prevents wastage of memory space.

3.6 Insert Operation


The insert operation under linked implementation of queues involves the following tasks:
1. Reserving memory space of the size of a queue element in memory
2. Storing the added (inserted) value at the new location
3. Linking the new element with existing queue at the rear end
4. Updating the rear pointer

3.7 Delete operation

The delete operation under linked implementation of queues involves the following tasks:
1. Checking whether the queue is empty. If so display underflow message.
2. Retrieving the front most element of the queue.
3. Updating the front pointer.
4. Returning the retrieved (removed) value.

3.8 Linked List Implementation of Queue

• Linked List implementation of Queue includes following :


– Declaration
– Create()
– InsertRear()
– DeleteFront()
– Display()

3.9 APPLICATIONS OF LINKED LISTS


• Sparse Matrix representation
• Polynomial representation and addition

Linked List Representation of the polynomial


A(x) = am-1 x cm-1 + ... +a0xc0 where, ai are non-zero co-efficient and the ci are non-negative integer
exponents such that cm-1 > cm-2 >...>c1>c0>=0.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 10

Declaration
struct polyNode
{
int coef;
int expon;
struct polyNode *link;
};
struct polyNode *a, *b;

Representation of Polynomials

a= 3x14+2x8+1 NULL

b = 8x14-3x10+10x6 NULL

Polynomial Addition (single variable):


For adding 2 polynomials, the following terms
are compared and checked starting at the nodes
pointed to by a & b. Below figure illustrates
this process for the polynomials addition.
o If the exponents are equal – add 2
coefficients and create new term for
the result. Move a & b to point to
next nodes.
If the exponent of the term in ‘a’ is less than the exponent of current item in ‘b’, then,
▪ Create a duplicate term ‘b’.
▪ Attach this term to the result called ‘c’.
▪ Advance the pointer to the next term only in ‘b’.
If the exponent of the term in ‘a’ is greater then the
exponent of current item in ‘b’, then,
• Create a duplicate term ‘a’.
• Attach this term to the result, called ‘c’.
• Advance the pointer to next term only in ‘a’.

Pseudocode to implement addition of two single


variable polynomial.
Step 1: Store two polynomials in two linked lists, say a and b. Let Result be the empty LL
Step 2: while (a != NULL or b != NULL) loop step 3 and 4
Step 3: if a->expo == b->expo then
Add a->coef and b->coef, Create new node and insert into Result LL
a = a->next ; b= b->next;
Step 4: if a->expo > b->expo then
Insert current node of ‘a’ into Result LL
a = a->next ;
else
Insert current node of ‘b’ into Result LL
b = b->next ;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 11

Step 5: copy rest all nodes to Result LL


Step 6: Print Result LL

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 12

3.10 Double Linked List


The difficulties with single linked lists is that, it is possible to traversal only in one direction, ie.,
direction of the links. The only way to find the node that precedes p is to start at the beginning of
the list. The same problem arises when one wishes to delete an arbitrary node from a singly linked
list. Hence the solution is to use doubly linked list. Doubly linked list is a linear collection of data
elements, called nodes, where each node is divided into three parts:
i. An information field INFO which contains the data of Node.
ii. A pointer field PREV which contains the location of the next node in the list
iii. A pointer field NEXT which contains the location of the preceding node in the list.
iv. The PREV of FIRST node and NEXT of LAST node are pointing to NULL.

3.10.1 The declaration of Double Linked List(DLL)


typedef struct node
{
struct node *prev;
int data;
struct node *next;
} NODE;

3.10.2 Create a node in DLL


void create()
{
int data;
temp=(struct node *)malloc(sizeof(struct node));
printf("\nEnter the data:"); scanf("%d",&data);
temp->data=data;
temp->prev=NULL;
temp->next=NULL;
count++;
}

3.10.3 Insert Operation:

• Insert at Front The new node is always added before the head of the given Linked List.
And newly added node becomes the new head of DLL.
• The new node is always added after the last node of the given Linked List.
void insertatfirst() void insertatlast()
{ {
create(); create();
if(first==NULL) { if(first==NULL) {
first=temp; first=temp;
last=first; last=first;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 13

} }
else { else {
first->prev=temp; last->next=temp;
temp->next=first;
first=temp; temp->prev=last;
} last=temp;
} }
}

3.10.4 Deleting a node

• Deleting a node at the end of the DLL is to move the LAST pointer to the previous node
and remove the LAST node.
• Deleting a node at the beginning of the DLL is to move the TEMP pointer to the beginning
of the DLL and move the FIRST pointer to the next node and remove the TEMP pointer
node.
void deleteatfirst() void deleteatlast()
{ temp=first; { temp=first;
if(first==NULL){ if(first==NULL) {
printf("\n DLL is empty"); printf("\n DLL is empty");
return; } return; }
if(temp->next==NULL){ if(temp->next==NULL) {
printf("\nDeleted node is: printf("\nDeleted node
%d",temp->data); is:%d", temp->data);
free(temp); first=NULL; } free(temp); first=NULL; }
else { else {
first=temp->next; temp=last->prev;
printf("\nDeleted node is: printf("\nThe deleted node
%d",temp->data); is:%d", temp->data);
free(temp); free(last); last=temp;
first->prev=NULL; } last->next=NULL; }
count--; count--;
} }

3.10.5 Traversing / Displaying nodes in DLL

Displaying of data in nodes start with the first node and ends at the last node.

void display()
{
if(first==NULL) {
printf("\nDLL is empty.");
return; }
else { temp=first;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 14

printf("\n DLL is\n");


while(temp!=NULL) {
printf("%d ",temp->data);
temp=temp->next;
}
printf("\nThe number of node(s) in DLL = %d.",count);
}
}

3.11 Header Linked List


A header linked list is a linked list which always contains a special node called the header node at
the beginning of the list. It is an extra node kept at the front of a list. Such a node does not
represent an item in the list. The information portion might be unused.

This header node allows us to perform operations more easily. The header node may contain some
useful information about linked list such as number of nodes in the list, address of last node/some
specific distinguishing information like the address of starting node is refereed by header pointer
The following are two kinds of widely used header lists:
1. A grounded header list is a header list where the last node contains the null pointer.
2. A circular header list is a header list where the last node points back to the header node.

3.12 Linked Stacks and Queues


Instead of using array, we can also use linked list to implement stack. Linked list allocates the
memory dynamically. However, time complexity in both the scenario is same for all the operations
i.e. push, pop and peek.
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory.
Each node contains a pointer to its immediate successor node in the stack. Stack is said to be
overflown if the space left in the memory heap is not enough to create a node.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 15

struct node
{
int data;
struct node *next;
} *top=NULL;

3.12.1 Adding a node to the stack (Push operation)

Adding a node to the stack is referred to as push operation. Pushing an element to a stack in linked
list implementation is different from that of an array implementation. In order to push an element
onto the stack, the following steps are involved.

The push operation under linked implementation ofstacks involves


l. Reserving memory space of the size of a stack element in memory
2. Storing the pushed (inserted) value at the new location
3. Linking the new element with existing stack
4. Updating the stack pointer
void push () // similar to insertFront()
{
int val;
struct node *temp =(struct node*)malloc(sizeof(struct node));
printf("Enter the value");
scanf("%d",&val);
if(head==NULL) {
temp->data = val;
temp->next = NULL;
head=temp;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 16

}
else {
temp->data = val;
temp->next = head;
head=temp;
}
printf("Item pushed");
}
}

3.12.2 Deleting a node from the stack (POP operation)

Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the
linked list implementation of stack is different from that in the array implementation. In order to
pop an element from the stack, we need to follow the following steps:
The pop operation under linked implementation of stacks involves the following tasks:
1. Checking whether the stack is empty
2. Retrieving the top element of the stack
3. Updating the stack pointer
4. Returning the retrieved (popped) value
int pop()
{
if (top==NULL)
{
printf("\n Stack is empty (underflow) \n");
return NULL;
}
else
{
int temp = top->data;
top=top->next;
return(temp);
}
}

3.13 Linked List Implementation of Queues


• The linked implementation of queues involves dynamically allocating memory space at run
time while performing queue operations.
• Since, the allocation of memory space is dynamic, the queue consumes only that much amount
of space as is required for holding its data elements.
• This is contrary to array implemented queues which continue to occupy a fixed memory space
even if there are no elements present. Thus, linked implementation of queues based on
dynamic memory allocation technique prevents wastage of memory space.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 17

3.13.1 Insert Operation


The insert operation under linked implementation of queues involves the following tasks:
1. Reserving memory space of the size of a queue element in memory
2. Storing the added (inserted) value at the new location
3. Linking the new element with existing queue at the rear end
4. Updating the rear pointer

3.13.2 Delete operation


The delete operation under linked implementation of queues involves the following tasks:
1. Checking whether the queue is empty. If so display underflow message.
2. Retrieving the front most element of the queue.
3. Updating the front pointer.
4. Returning the retrieved (removed) value.

3.13.3 Linked List Implementation of Queue


• Linked List implementation of Queue includes following :
– Declaration
– Create()
– InsertRear()
– DeleteFront()
– Display()

3.14 APPLICATIONS OF LINKED LISTS


• Sparse Matrix representation
• Polynomial representation and addition

3.14.1 A linked list representation for sparse matrices.

In data representation, each column of a sparse matrix is represented as a circularly linked list
with a header node. A similar representation is used for each row of a sparse matrix.
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.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 18

• 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, there is 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 link into the list of header nodes.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 3: BCS304 DATA STRUCTURES AND APPLICATIONS 19

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]

You might also like