Data Structures - Linear Data Structures
Data structure is an organizational way of storing data in the computer and it reduce the time and cost of data access. And also it can reduce the storage space of data. In this post, I am going to consider about Linear Data Structures (LDS). Under LDS, there are few popular data structures that are commonly used.
1. Array2. Linked List3. Stack4. Queue
Array
Array is a data structure used to store data that are in same data type at contiguous spaces. The size of an array must be assigned before storing data. Each and every storage space can accessed separately. The index of array list starts from 0 and end with size -1.
Ex: int[] arr = new int[5]; or int[] arr; or int[] arr = {1,2,3,4,5};
arr[0] = 1; arr = new int[] {1,2,3,4,5};
When considering the size of array is equal to n.
| Accessing Time | O(1) | because data are stored at near by spaces |
| Search Time | O(n) O(log n) | Sequential Search - one by one Binary Search - using sorted array |
| Insertion Time | O(n) | Insertion starts from the beginning of the array - one by one insertion |
| Deletion Time | O(n) | Deletion starts from the beginning of the array - one by one deletion |
Limitation
1. Array has a fixed size
2. Insertion is not easy - When the size of the array is exceeded, we have to create new array and insert all the data to it.
3. Deletion is not easy - When delete a data from the array, the other data of the array have to move.
Linked List
A Linked List is a LDS, and the element of the data structure is an object (called as node). This node contains the data and a reference to the next node. There are not stored at a contiguous spaces.
Types of Linked List (LL):
1. Singly LL2. Doubly LL3. Circular LL
1. Singly LL : In this type of linked list, every node stores address of next node in list and the last node has next address as NULL.
// A simple Java Program for Singly LLclass LinkedList {Node head; // head of list (1st element of the list)
public LinkedList(){} // Constructor - Class LinkedList
//static inner class - main method can directly access static inner classes
static class Node {int data;Node next;Node(int d){data = d;next = null;} // Constructor - Class Node}//print methodpublic void printList(){Node n = head;while (n != null) {System.out.println(n.data);n = n.next;}}//main methodpublic static void main(String[] args){LinkedList ll= new LinkedList();ll.head = new Node(1);Node second = new Node(2);Node third = new Node(3);ll.head.next = second; // Link first node with the second nodesecond.next = third; // Link first node with the second nodell.printList();}}
Limitation
1. Cannot access data randomly - we have to start from the 0th node to find a data
2. Extra space required to store address of the next node
3. Can traverse only one single path
2. Doubly LL : In this type of Linked list, there are two address for each nodes, One address points to the next node and other address points to the previous node.
public class DoublyLL{Node head; // head of list/* Doubly Linked list Node*/class Node {int data;Node prev;Node next;// Constructor to create a new nodeNode(int d) {
data = d;
next = null;
prev = null; }
}}
Limitation
1. Need extra space to store addresses
3. Circular LL : In Circular linked list, all nodes are connected as a circle. There is no NULL at the end. Any node can consider as a starting node.
When consider the Linked List
| Accessing Time | O(n) | |
| Search Time | O(n) | |
| Insertion Time | O(1) | If we at the position of the node, we can easily add the node |
| Deletion Time | O(1) | If we at the position of the node, we can easily delete the node |
Stack
Stack follows a particular order to perform operations.
1. LIFO(Last In First Out)
2. FILO(First In Last Out)
Here we can only access the top of the stack for insertion and deletion. Normally we are using Array data structure or Linked List data structure to implement this stack. Linked List implementation can increase at the run time. However need extra space to store pointers in this method. Using Array for implementation is easy. But we cannot do dynamical changes. There are four methods that are used in Stack Class.
1. push(data) : add the data on the top of the stack.
2. pop() : remove and returns the top data of the stack.
3. peek() : return the data on the top of the stack.
4. isEmpty() : if nothing is on the top of the stack, returns true else false
Ex: Implementation using Array data structure
class Stack {static final int MAX = 1000;int top;int stackarr[] = new int[MAX]; // Maximum size of Stackboolean isEmpty(){if(top < 0){return true;}else{return false;}}Stack(){top = -1; //Starting from -1}void push(int val) //push operation{if (top >= (MAX - 1)) {System.out.println("Stack Overflow");}else {stackarr[++top] = val;System.out.println(val + " pushed into stack");}}void pop() //pop operation{if (isEmpty() == true) {System.out.println("Stack Underflow");}else {int val = stackarr[top--];System.out.println(val+" poped from the Stack");}}void peek() //peek operation{if (isEmpty() == true) {System.out.println("Stack Underflow");}else {int val = stackarr[top];System.out.println(val+" peek of the Stack");}}}public class Main {public static void main(String args[]){Stack s = new Stack();s.push(1);s.push(2);s.push(3);s.pop();s.peek();}}
When considering the stack,
| Insertion | O(1) | because we push to the top |
| Deletion | O(1) | because we pop from the top |
| Peek | O(1) | because the peek is the top |
| isEmpty | O(1) | because we check it from the top |
Queue
Queue also follows a particular order to perform operations. The order is First In First Out (FIFO).
There are four basic operations of Queue.
1. Enqueue: Adds an data to the queue. If the size of the queue exceeded, it is overflow
2. Dequeue: Removes an data from the queue. If there is no data in the queue, it is underflow
3. Front: Get the front data from queue.
4. Rear: Get the last data from queue.
Normally we are using Array and Linked List data structures to implement this queue. Using Array, Queue implementation is easy but it has fixed size.
Ex: Implementation using Array data structure
class Queue {int front, rear, size;int capacity;int array[];public Queue(int capacity){this.capacity = capacity;this.size = 0;front = 0;rear = capacity - 1;array = new int[this.capacity];}// Queue is full when size is equal to capacityboolean isFull(){if(size == capacity){return true;}else{return false;}}// Queue is empty when size is 0boolean isEmpty(){if(size == 0){return true;}else{return false;}}//enqueuevoid enqueue(int num){if (isFull()==true) {System.out.println("Overflow");}else{this.rear = (this.rear + 1) % this.capacity;this.array[this.rear] = num;this.size = this.size + 1;System.out.println(num + " enqueued to queue");}}//dequeuevoid dequeue(){if (isEmpty()==true){System.out.println("Underflow");}else{int num = this.array[this.front];this.front = (this.front + 1) % this.capacity;this.size = this.size - 1;System.out.println(num + " dequeued from queue");}}// get front of queuevoid front(){if (isEmpty()==true) {System.out.println("0");}else{System.out.println("Front " + this.array[this.front]);}}// get rear of queuevoid rear(){if (isEmpty()==true) {System.out.println("0");}else{System.out.println("Rear " + this.array[this.rear]);}}}public class Test {public static void main(String[] args){Queue queue = new Queue(5);queue.enqueue(1);queue.enqueue(2);queue.enqueue(3);queue.enqueue(4);queue.enqueue(5);queue.enqueue(6);queue.dequeue();queue.enqueue(6);queue.front();queue.rear();}}
When we are considering queue data structure,
| Insertion | O(1) | because we enqueue to the rear |
| Deletion | O(1) | because we dequeue from the front |
| Front | O(1) | |
| Rear | O(1) |
There are three extensions from the Queue.
1. Priority Queue - Consider the priority of the data and dequeue high priority data first.
2. Deque Queue - Give permission to insertion and deletion from the both ends.
3. Circular Queue - In here the last index of the array connect with the first index of the array and make a circle. Using this method can fill empty dequeued spaces.
Comments
Post a Comment