Author : Abhay Kumar Singh

DATA STRUCTURE USING IN C

UNIT – 1
Data structure  Way of analyzing an algorithm --
1.Best case 2. Average case 3. Worst case
 Data Structure is a branch of Computer Science.  Complexity of an algorithm --
 A data structure is a storage that is used to store and organize  Complexity in algorithms refers to the amount of
all the data items. resources required to solve a problem or perform a task.
 used for processing, retrieving, and storing data.  Resources may be me and space.
 Types of Complexi es of an algorithm --
Why do we use data structure
 Time complexity of an algorithm is the amount of me
 Necessary for designing efficient algorithms. it needs to run to comple on.
 It helps to organization of all data items within the memory.  Space complexity of an algorithm is the amount of
 It requires less time. space it needs to run to comple on.
 Easy access to the large database.
 order of Complexity of an algorithm --
Classification/ Types of Data structure
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(3^n) < O(n!)
 Linear data structure --allows data elements to be arranged
Asymptotic Notation
in a sequen al or linear fashion.
Example: arrays, linked lists, stack, and queue etc. It is used to write possible running me for an algorithm.It also
 Non-Linear data structure -- It is a form of data structure referred to as 'best case' and 'worst case' scenarios respec vely.
where the data elements do not stay arranged linearly or
sequen ally.  Big-oh nota on:
Example: Tree, graph etc.  It is the method of expressing the upper bound of an
algorithm's running me.
Terminologies in Data structure  It is the measure of the longest amount of me. The
func on f (n) = O (g (n))
 Data -- Data are values or set of values.  f(n) <= c.g(n) where n>n0
 Data Item -- Data item refers to single unit of values.  Example: 3n+2=O(n) as 3n+2≤4n for all n≥2
 En ty -- An en ty is that which contains certain a ributes or
proper es, which may be assigned values.
 En ty Set -- En es of similar a ributes form an en ty set.
 Field -- Field is a single elementary unit of informa on
represen ng an a ribute of an en ty.
 Record -- Record is a collec on of field values of a given
en ty.
 File -- File is a collec on of records of the en es in a given
en ty set.  Big-Omega nota on:
Datatypes in C programming  It is the method of expressing the lower bound of an
algorithm's running me.
 Primi ve Data Types – It is the most basic data types that  It is the measure of the smallest amount of me. The
are used for represen ng simple values such as: func on f (n) = Ω(g (n))
 Integers – 23, 33432 ,342342 etc.  f(n) >= c.g(n) where n>n0
 Float – 23.2342, 232.00,2342.0000,323.323 etc.  Example: 3n-3= Ω (n) as 3n-3 >=2n for all n≥3
 Characters - ‘2’, ‘a, ‘$’, ‘@,’g’ etc.
 Void – used to specify the type of func ons which
returns nothing.
 Non-Primi ve Data Types – It is derived from primi ve data
types.
 Arrays
 Linked-list  Theta(Θ) nota on:
 Queue  It is the method of expressing the both lower and upper
 Stack etc. bound of an algorithm's running me.
 It is the measure of the average amount of me. The
Algorithm func on f (n) = Θ(g (n))
 c1.g(n) <= f(n) <= c2.g(n) where n>n0
 An algorithm is a step-by-step procedure of any problem.
 Example: 3n-3=O(n) as 2n<= 3n-3 <= 4n for all n≥3
 Criteria of an algorithm --
1. Input 2. Output 3. Definiteness 4. Finiteness 5.
Effec veness
  It is used to implement vectors, and lists in C++ STL.
 Arrays are used as the base of all sor ng algorithms.
 It is used to implement other DS like stack, queue, etc.
 Used for implemen ng matrices.
 Graphs are also implemented as arrays in the form of an
adjacency matrix etc.

Sparse Matrix
Time-Space Trade-Off in Algorithms
 It is matrix in which most of the elements of the matrix have
 It is a problem solving technique in which we solve the zero value .
problem:  Only we stored non-zero elements with triples- (Row,
 Either in less me and using more space, or Column, value).
 In very li le space by spending more me.  Array representa on of Sparse Matrix –
 The best algorithm is that which helps to solve a problem
that requires less space in memory as well as takes less me
to generate the output.
 it is not always possible to achieve both of these condi ons
at the same me.

Abstract Data type (ADT)  Linked list representa on of sparse matrix –

 It is a type (or class) for objects whose behaviour is defined

by a set of values and a set of opera ons.
 The defini on of ADT only men ons what opera ons are to
be performed but not how these opera ons will be
implemented.
Linked List
 Example : if we talk about LIST then here we can store
mul ple value and it has many built in func on so that we  A linked list is a collec on of “nodes” connected together via
will work on that data . links.
Func on such as insert(), delete(), pop(), remove() etc.  These nodes consist of the data to be stored and a pointer to
the address of the next element .
Array
 Linked list has mul ple types:
 An array is a collec on of items stored at con guous 1. singly linked list 2. Doubly linked list 3. Circular linked list
memory loca ons.
Singly Linked List (SLL)
 Array is linear data structure. It is one of the simplest DS.
 The idea is to store mul ple items of the same type  It is a linear data structure in which the elements are not
together. stored in contiguous memory locations .
 Syntax -- type variable_name [size];  Each element is connected only to its next element using
 Example – int arr[10]; this is a array declara on of the array address.
now here we can only store 10 integer values in this array
 Array has two type:

1. One dimensional 2. Mul dimensional  Representa on Node of SLL :

 One dimensional Array :
struct node{
 Array represented as one-one dimension such as row or
int data; //data item for storing value of the node
column and that holds finite number of same type of
struct node *next; //address of the next node
data items is called 1D array .
};
 Example -- int arr[10];
 create Node of SLL:
 Mul -dimensional Array :
 Array represented as more than one dimension . there struct Node* Node(int data){
are no restric on to number of dimensions that we can struct Node* newNode=(struct Node*)malloc(sizeof(struct
Node ));
have.
newNode->data=data;
 Example -- int arr[2][4][5]; newNode->next=NULL;
 Applica on of Array : return newNode;
 Arrays can be storing data in tabular format }
Operations on SLL  Traverse Linked List:

 Insert At beginning : void traverse(struct Node* head){

while (head->next!=NULL){
struct Node * addAtBeg(int data, struct Node* head){ printf("%d ", head->data);
struct Node* newNode=Node(data); head=head->next;
if(head==NULL){ }
return newNode; }
} Advantage & disadvantage of singly linked list
newNode->next=head;
return newNode;  Advantages:
}  very easier for the accessibility of a node in the forward
 Insert At End : direc on.
struct Node * addAtEnd(int data, struct Node* head){  the inser on and dele on of a node are very easy.
struct Node* newNode=Node(data);  require less memory when compared to doubly, circular
if(head==NULL){ linked list.
return newNode;  very easy data structure
}  Inser on and dele on of elements don’t need the
struct Node* temp=head; movement of all the elements when compared to an
while ( temp->next !=NULL)
array.
{
temp=temp->next;
 Disadvantages :
}  Accessing the preceding node of a current node is not
temp->next=newNode; possible as there is no backward traversal.
return head;  Accessing of a node is very me-consuming.
}
 Insert At specific Posi on : Doubly Linked List(DLL)

struct Node* addAtPos(int data , int pos , struct Node* head)  A DLL is a complex version of a SLL .
{  A DLL has each node pointed to next node as well as previous node.
if(pos==1){
return addAtBeg(data,head); }
struct Node* temp=head;
for (int i = 1; i <=pos; i++)
{ if(i!=pos && temp==NULL ){
return head; //invalid position
}
if(i==pos-1){  Representa on Node of DLL :
struct Node * newNode=Node(data);
newNode->next=temp->next; struct node
temp->next=newNode; {
return head; int data; //data item for storing value of the node
} struct node *next; //address of the next node
temp=temp->next; struct node *prev; //address of the previous node
}
};
return head;
}  create Node of DLL:
 Delete at beginning : struct Node* Node(int data){
struct Node* newNode=(struct Node*)malloc(sizeof(struct
struct Node * deleteAtBeg( struct Node* head){
Node ));
if(head==NULL){
newNode->prev= NULL;
return NULL;
newNode->data=data;
}
newNode->next=NULL;
return head->next;
return newNode;
}
}
 Delete at End :
Operations on DLL
struct Node * deleteAtEnd( struct Node* head){
if( head==NULL || head->next == NULL){  Insert At beginning :
return NULL;
} struct Node * addAtBeg(int data, struct Node* head){
struct Node* temp=head; struct Node* newNode=Node(data);
while (temp->next->next !=NULL){ if(head==NULL){
temp=temp->next; return newNode;
} }
temp->next=NULL; newNode->next=head;
return head; head->prev=newNode;
} return newNode;
}
 Insert At End : Circular Linked List (CLL)
struct Node * addAtEnd(int data, struct Node* head){  All nodes are connected to form a circle.
struct Node* newNode=Node(data);
 the first node and the last node are connected to each other
if(head==NULL){
return newNode; which forms a circle.
}  There is no NULL at the end.
struct Node* temp=head;
while ( temp->next !=NULL)
{
temp=temp->next;
}
temp->next=newNode;
newNode->prev=temp;
return head;
Operations on CLL
}
 Delete At beginning:  Insert at beginning
struct Node * deleteAtBeg( struct Node* head){  Insert at specific Posi on
if(head==NULL || head->next==NULL){  Insert at end
return NULL;  delete at beginning
}  delete at specific posi on
head ->next->prev = NULL;  delete at end
return head->next;
} Advantage & disadvantage of CLL
 delete At End :
 Advantages:
struct Node * deleteAtEnd( struct Node* head){  No need for a NULL pointer
if( head==NULL || head->next == NULL){  Efficient inser on and dele on
return NULL;
 Flexibility
}
struct Node* temp=head;  Disadvantages :
while (temp->next->next !=NULL){  Traversal can be more complex
temp=temp->next;  Reversing of circular list is a complex as SLL.
}
temp->next=NULL; Row major order & Column major order
return head;
} int arr[2][3]=
 Traverse DLL : { {1,2,3},
{4,5,6} } //2D array
void traverse(struct Node* head){
while (head!=NULL){ //row major order
printf("%d ", head->data); {1,2,3,4,5,6}
head=head->next; } } //column major order
 ReverseTraverse DLL: {1,4,2,5,3,6}
Address of any element in 1D array
void traverseRev(struct Node* head){
if(head==NULL) Address of A[I] = B + W * (I – LB)
return;
while (head->next!=NULL) I =element, B = Base address, LB = Lower Bound
head=head->next;
W = size of element in any array(in byte),
while (head!=NULL){
printf("%d ", head->data); Example: Given the base address of an array A[1300 ………… 1900] as
head=head->prev; 1020 and the size of each element is 2 bytes in the memory, find the
} address of A[1700].
}
Advantage & disadvantage of DLL Solution :

Address of A[I] = B + W * (I – LB)

 Advantages:
 It is bi-direc onal traversal Address of A[1700] = 1020 + 2 * (1700 – 1300)
 It is efficient dele on = 1020 + 2 * (400) = 1020 + 800=1820
 Inser on and dele on at both ends in constant me
 Disadvantages : Address of any element in 2D array
 Increased memory usage
Row major order : A[I][J] = B + W * ((I – LR) * N + (J – LC))
 More complex implementa on
 It is slower traversal I = Row element , j=column element , LR=lower limit of row

N = No. of column given in the matrix , LC=lower limit of column

Example: Given an array, arr[1………10][1………15] with base value
100 and the size of each element is 1 Byte in memory. Find the
address of arr[8][6] with the help of row-major order.
Formula:

Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))

Solution:

N = Upper Bound column – Lower Bound column + 1

A[8][6] = 100 + 1 * ((8 – 1) * 15 + (6 – 1)) = 100 + 1 * ((7) * 15 + (5))

= 100 + 1 * (110)=210

column major order :

A[I][J] = B + W * ((J– LC) * M + (I – LR))

N = No. of rows given in the matrix

Example: Given an array, arr[1………10][1………15] with base

value 100 and the size of each element is 1 Byte in memory. Find
the address of arr[8][6] with the help of row-major order.
Formula:

A[I][J] = B + W * ((J– LC) * M + (I – LR))

Solution:

M = Upper Bound row – Lower Bound row + 1

A[I][J] = B + W * ((J – LC) * M + (I – LR))

A[8][6] = 100 + 1 * ((6 – 1) * 10 + (8 – 1))

= 100 + 1 * ((5) * 10 + (7))= 100 + 1 * (57)= 157

Difference between Array and Linked List

Array Linked List

It is stored in a contiguous It can be stored randomly in
memory location. the memory .
elements are independent of elements are dependent on
each other. each other
memory is allocated at memory is allocated at run
compile-time. time
Accessing any element in an Accessing an element in a
array is faster linked list is slower
Array takes more time while Linked list takes less time while
performing any operation like performing any operation like
insertion, deletion, etc. insertion, deletion, etc.