UNIT II
LINEAR DATA STRUCTURES
Stack : Definition Operation, Uses, Implementation etc.,
Queue: Definition, Operations, Uses, Implementation, Types of Queue etc.,
Linked List: Definition, Operation, Uses, Implementation, Types (Singly, Doubly, Circular)
LINEAR DATA STRUCTURE
Linear data structure is a type of structure where data items are arranged in a linear fashion
(sequential elements).
Each data elements are attached to their members (previous and next elements).
Data storage is allowed in only single level as elements are attached in linear fashion.
Data traversal is only one run.
Such data structures are easy to implement as the computer memory is also sequential.
Linear data structures include,
Arrays,
Stack
Queue
Linked Lists
Arrays
Arrays are collection of elements stored in contiguous memory.
It is used to store homogenous elements at contiguous locations.
The size of an array need to be provided much before storing data.
Array uses index based data structure for identifying each of the elements.
Arrays can be categorized as single dimensional array and double dimensional array.
Practice Questions
1. Write a program in C to read n number of values in an array and display them in
reverse order.
2. Write a program in C to copy the elements of one array into another array.
3. Write a program in C to count the total number of duplicate elements in an array.
,Uses
Arrays can be used for sorting data elements.
It is used for storing contacts on a mobile device, storing data in table format, performing
matrix operations.
Operation
Analysis of Arrays
Let the size of an array be n,
Accessing Time : O(1) (Constant Time)
All elements are stored in contiguous memory locations.
Searching Time: O(n) (Linear Time)
Linear Time in case of sequential search.
O(log n) in case of binary search.
Inserting Time: O(n)
Deleting Time : O(n)
Advantages
1. Arrays take constant time to access its elements.
2. Memory allocation / location is contiguous.
3. The method of implementation is easy.
Stack
A Stack ( LIFO – Last in First Out) is an ADT (Abstract Data Type)
It is a collection of elements.
It has two principal operations : Push() and Pop().
Push() adds elements into the collection where as Pop() removes elements from the
collection.
Pop() always removes elements that are added last.
Both operations take place at the same end that is at the top of the stack.
Analysis
, Insertion time takes O(1)
The time taken to insert elements into a stack is constant represented by O(1).
Deletion time takes O(1)
The time taken to delete elements from a stack is constant represented by O(1).
Access time
Acesssing time of elements in a stack takes O(n) ( linear time) (Worst Case)
That is, in simple terms, as input grows time taken also grows linearly.
Where all Stack used ? (Application of Stack)
1) Stacks are used in function calls.
2) Stacks are used in reversing a word
3) Check for balanced parenthesis
4) In Editors, the last typed word is the first to be removed (Undo operation).
Operations
push() An element is inserted into stack
pop() An element is popped out of stack.
top() This will return the last inserted element.
size () This will return the size of the stack.
isEmpty() This indicates if the stack is empty or not
isFull() This indicates if the stack is full or not.
Implementation of (Sample Programs) stack functions.
(Pending)
#include <stdio.h>
// stack using array with choices.
#define MAX_SIZE 5
int ctr=0;
int stack[MAX_SIZE];
int top = -1;
int elements;
int push()
LINEAR DATA STRUCTURES
Stack : Definition Operation, Uses, Implementation etc.,
Queue: Definition, Operations, Uses, Implementation, Types of Queue etc.,
Linked List: Definition, Operation, Uses, Implementation, Types (Singly, Doubly, Circular)
LINEAR DATA STRUCTURE
Linear data structure is a type of structure where data items are arranged in a linear fashion
(sequential elements).
Each data elements are attached to their members (previous and next elements).
Data storage is allowed in only single level as elements are attached in linear fashion.
Data traversal is only one run.
Such data structures are easy to implement as the computer memory is also sequential.
Linear data structures include,
Arrays,
Stack
Queue
Linked Lists
Arrays
Arrays are collection of elements stored in contiguous memory.
It is used to store homogenous elements at contiguous locations.
The size of an array need to be provided much before storing data.
Array uses index based data structure for identifying each of the elements.
Arrays can be categorized as single dimensional array and double dimensional array.
Practice Questions
1. Write a program in C to read n number of values in an array and display them in
reverse order.
2. Write a program in C to copy the elements of one array into another array.
3. Write a program in C to count the total number of duplicate elements in an array.
,Uses
Arrays can be used for sorting data elements.
It is used for storing contacts on a mobile device, storing data in table format, performing
matrix operations.
Operation
Analysis of Arrays
Let the size of an array be n,
Accessing Time : O(1) (Constant Time)
All elements are stored in contiguous memory locations.
Searching Time: O(n) (Linear Time)
Linear Time in case of sequential search.
O(log n) in case of binary search.
Inserting Time: O(n)
Deleting Time : O(n)
Advantages
1. Arrays take constant time to access its elements.
2. Memory allocation / location is contiguous.
3. The method of implementation is easy.
Stack
A Stack ( LIFO – Last in First Out) is an ADT (Abstract Data Type)
It is a collection of elements.
It has two principal operations : Push() and Pop().
Push() adds elements into the collection where as Pop() removes elements from the
collection.
Pop() always removes elements that are added last.
Both operations take place at the same end that is at the top of the stack.
Analysis
, Insertion time takes O(1)
The time taken to insert elements into a stack is constant represented by O(1).
Deletion time takes O(1)
The time taken to delete elements from a stack is constant represented by O(1).
Access time
Acesssing time of elements in a stack takes O(n) ( linear time) (Worst Case)
That is, in simple terms, as input grows time taken also grows linearly.
Where all Stack used ? (Application of Stack)
1) Stacks are used in function calls.
2) Stacks are used in reversing a word
3) Check for balanced parenthesis
4) In Editors, the last typed word is the first to be removed (Undo operation).
Operations
push() An element is inserted into stack
pop() An element is popped out of stack.
top() This will return the last inserted element.
size () This will return the size of the stack.
isEmpty() This indicates if the stack is empty or not
isFull() This indicates if the stack is full or not.
Implementation of (Sample Programs) stack functions.
(Pending)
#include <stdio.h>
// stack using array with choices.
#define MAX_SIZE 5
int ctr=0;
int stack[MAX_SIZE];
int top = -1;
int elements;
int push()
