Kerala Plus Two Computer Science Notes Chapter 3 Data Structures and Operations
It is a particular way of organizing similar or dissimilar logically related data items into a single unit.
Classification of data structures
Classified as simple and compound. Compound (mixture) data structure is further classified as linear and non linear. A data structure is said to be linear if its elements form a sequence(it needs contiguous memory location) otherwise it is called a non-linear data structure needs random memory)
The examples of Linear data structures are stack, queue and linked list.
We know that memory is classified into two primary and secondary. Just like that data structures are classified as static and dynamic. Static data structure is associated with primary memory. The needed memory is allocated before the execution of the program and it is fixed through out the execution. Array is an example for this. In Dynamic data structure, memory is allocated during execution. Linked list is an example for this.
Operations on data structures
- Traversing: Accessing or visiting or reading all elements of a data structure is called Traversal.
- Searching: Searching is the process of finding elements in a data structure
- Inserting : It is the process of adding new data at particular location is called insertion.
- Deleting : It is the process of removing a particular element from the data structure
- Sorting : Arranging elements in a particular order(ascending ordescending) is called sorting. Examples are bubble sort and selection sort.
- Merging: This is the process of combining two sorted data structure and form a new one.
Stack
A stack is a linear structure in which items can be added or removed only at one end called top. Add an item into the stack is called push and deleting an item from the stack is called pop.
The data structure that follows LIFO principle is known as stack. Example. CD pack, idly utensils, etc. Implementation of stack In a stack the values can be added or removed by at the top end only.Stack can be implemented using array. Initially the value of‘top’is set to-1 to denote the stack is empty. Whenever a value is added to a stack top’ is incremented by 1. The index of first element is 0 and the last Is N-1.
Operations on stack
a) Push operation: It is the process of inserting (adding) a new data item into the stack. If the stack is full and we try to add a new item into the stack makes the stack over flow.
b) Pop operation: It is the process of deleting (removing) a data item from the stack. If the stack is empty and we try to delete an item from the stack makes the stack underflow.
Queue
The working principle of a Queue is First In First Out(FIFO) manner. A new data item is added at the rear and removed from the front of a Queue. Examples Queue in a Cinema theater, poling station etc. Implementation of Queue A new data item is added at the rear and removed from the front of a Queue.Queue can be implemented using array. Initially the value of front and rearisset to -1 to denote the queue is empty. Whenever a value is added to a queue the rear is incremented by 1. Similarly on each deletion the value of front will be incremented by, until it crosses the value of rear.
Operation on Queue
a) Insertion operation: It is the process of adding a new item into a queue at the rear end. If the queue is full and we try to add a new item into thequeue makes the queue overflow.
b) Deletion operation: It is the process of deleting (removing) a data item from the queue from the front. If the queu is empty and we try to delete an item from the queue makes the queue underflow.
Circular queue
As the name implies logically the shape of the circular queue is a shape of a circle. The linear queue has some limitations such as some occasions the capacity of the linear queue cannot be used fully. The limitation of linear queue can overcome by circular queue. Circular queue is a queue in which the two end points are connected
Linked List
Stack and queue are implemented by array and has the fixed storage capacity. That is these implementation are static. But linked list follows the dynamic data structure method. It grows and shrinks as and when the new items are added and removed respectively. Not only that an array requires contiguous memory but linked list not require contiguous memory rather it uses scattered memory and they linked by pointers. So an element in a linked list consists of data and an address it is called node. Here address is the link.
Linked list is a collection of nodes. The first node contains the data and address of next node. The second node contains the data and the address of next node and so on. The last node contains the last data and a null pointer.
Implementation of linked list
A node consists of data and address of the next node. The address is a pointer. To implement this self referential structure is used since structure consist s of different types of data.
Example
struct node
{
int data;
node *link;
};The special pointer start that points to the first node is created by as follows node ‘start;
Operations on linked list
a) Creation of linked list: Linked list can be implemented by self referential structure.
Step 1 : Create a node and obtain its address.
Step 2 : Store data and NULL in the node.
Step 3 : If it is the first node, store its address in Start.
Step 4 : If it is not the first node, store its address in the link part of the node.
Step 5 :’ Repeat the steps 1 to 4.
b) Traversing a linked list: Traversing is the process of reading all elements in a data structure.
Step 1 : Get the address of the first node and store it in the variable Temp.
Step 2 : Using the address jn Temp, get and store the data in Val.
Step 3 : The address of the next node store it in Temp.
Step 4: If the address of Temp is not null go to step 2, otherwise stop.
c) Insertion in a linked list Insertion is the process of adding new node to a data structure.
Step 1: Create a node and store its address in Temp.
Step 2 : Store the data and link part of this new node using Temp.
Step 3 : Get the address of the previous node (POS-1) and next node(POS+1) inthe pointers PreNode and PostNode respectively.
Step 4 : Copy the contents of Temp into the link part of node at position (POS-1). .
Step5 : Copy the contents of PostNode into the link part of new node that is pointed to by Temp.
d) Deletion from a linked list
It is the removal of a node from the data structure.
Step 1 : Get the address of the previous node (POS-1) and next node(POS+1) in the pointers PreNode and PostNode respectively.
Step 2 : Copy the contents of PostNode into the link part of node at position (POS-1).
Step 3: Free the node at position POS.