Summary of Even Semester, 2020

Summary of Data Structure Even Semester 2020

Introduction to Data Structure

Data structure ® a particular way of organizing data in a computer so that it can be used effectively. Purpose: to reduce the space and time complexities of different tasks.

Types of Data Structure:

·         Array

·         Linked Lists

·         Stack

·         Queue

·         Binary Tree

·         Binary Search Tree

·         Heap

·         Hashing Data Structure

·         Matrix

·         Trie

Linked List

Linked list ® data structure that consists of a sequence of data records such that each record there is a field that contains a reference to the next record in the sequence.

Advantages over arrays:

·         Dynamic size

·         Ease of insertion/deletion

Drawbacks:

·         Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists efficiently with its default implementation. 

·         Extra memory space for a pointer is required with each element of the list.

·         Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.

Types of linked list:

·         Single linked list

·         Double linked list

Single Linked List

Characteristic ® Having a single one way link from a list pointing to another list

First, define the node structure.

Insert function of single linked list:

Delete function of single linked list

Circular Single Linked List

In circular, last node contains a pointer to the first node.

We can have a circular singly linked list as well as a circular doubly linked list.

There is no storing of NULL values in the list

Double Linked List

Double/Doubly linked list (two-way linked list) ® a linked list data structure with two link, one that contain reference to the next data and one that contain reference to the previous data.

Define node

 Insert function

Delete function

Circular Double Linked List

Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two consecutive elements are linked or connected by previous and next pointer and the last node points to first node by next pointer and also the first node points to last node by previous pointer.

Stack & Queue

Stack

Stack ® a linear data structure which follows a particular order in which the operations are performed.

Characteristic ® LIFO (Last In First Out); all insertions and deletions are done at the node pointed by the TOP (The starter point).

Operation:

·         Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.

·         Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.

·         Peek or Top: Returns top element of stack.

·         isEmpty: Returns true if stack is empty, else false.

Applications:

·         Balancing of symbols

·         Infix to Postfix /Prefix conversion

·         Redo-undo features at many places like editors, photoshop.

·         Forward and backward feature in web browsers

·         Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.

·         Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver

·         In Graph Algorithms like Topological Sorting and Strongly Connected 

Components

Implementation:

There are two ways to implement a stack:

·         Using array

·         Using linked list

Infix, Postfix, and Prefix

Prefix   : operator is written before operands

Infix     : operator is written between operands

Postfix : operator is written after operands

Queue

Queue ® a linear structure which follows a particular order in which the operations are performed.

Characteristic ® First In First Out (FIFO).

The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Operations:

•    Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.

•    Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.

•    Front: Get the front item from queue.

•    Rear: Get the last item from queue.

Applications of Queue:

Queue is used when things don’t have to be processed immediately, but have to be processed in FIFO order like Breadth First Search. This property of Queue makes it also useful in following kind of scenarios.

1) When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.

2) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

Priority Queue

Priority Queue is an extension of queue with following properties.

1.     Every item has a priority associated with it.

2.    An element with high priority is dequeued before an element with low priority.

3.    If two elements have the same priority, they are served according to their order in the queue.

A typical priority queue supports following operations.

•      insert(item, priority): Inserts an item with given priority.

•      getHighestPriority(): Returns the highest priority item.

•      deleteHighestPriority(): Removes the highest priority item.

Applications of Priority Queue:

1)     CPU Scheduling

2)    Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc

3)    All queue applications where priority is involved.

Deque

Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both ends.

Operations on Deque:

Mainly the following four basic operations are performed on queue:

•      insertFront(): Adds an item at the front of Deque.

•      insertLast(): Adds an item at the rear of Deque.

•      deleteFront(): Deletes an item from front of Deque.

•      deleteLast(): Deletes an item from rear of Deque.

In addition to above operations, following operations are also supported

•      getFront(): Gets the front item from queue.

•      getRear(): Gets the last item from queue.

•      isEmpty(): Checks whether Deque is empty or not.

•      isFull(): Checks whether Deque is full or not.

Applications of Deque:

Since Deque supports both stack and queue operations, it can be used as both. The Deque data structure supports clockwise and anticlockwise rotations in O(1) time which can be useful in certain applications.

Also, the problems where elements need to be removed and or added both ends can be efficiently solved using Deque.

Implementation:

A Deque can be implemented either using a doubly linked list or circular array. In both implementation, we can implement all operations in O(1) time.

Circular Queue

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’.

Operations on Circular Queue:

•              Front: Get the front item from queue.

•              Rear: Get the last item from queue.

•              enQueue(value) This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at Rear position.

Steps:

1.     Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).

2.    If it is full then display Queue is full. If queue is not full then, check if (rear == SIZE – 1 && front != 0) if it is true then set rear=0 and insert element.

•              deQueue() This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from front position.

Steps:

1.     Check whether queue is Empty means check (front==-1).

2.    If it is empty then display Queue is empty. If queue is not empty then step

3.    Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if it is true then set front=0 and return the element.

Hashing and Hash Tables, Trees & Binary Tree

Hashing ® a technique used for storing and retrieving keys in a rapid manner.

Hashing can also be defined as a concept of distributing keys in an array called a hash table using a predetermined function called hash function.

Hash table ® a table (array) where we store the original string. Index of the table is the hashed key while the value is the original string.

Hash function ® ways to hash a string into a key.

Types of hash function:

·         Mid-square ® Square the string/identifier and then using an appropriate number of bits from the middle of the square to obtain the hash-key.

·         Division (most common) ® Divide the string/identifier by using the modulus operator.

·         Folding ® Partition the string/identifier into several parts, then add the parts together to obtain the hash key

·         Digit Extraction ® A predefined digit of the given number is considered as the hash address.

·         Rotating Hash ® Use any hash method (such as division or mid-square method). After getting the hash code/address from the hash method, do rotation

Collision Handling: Since a hash function gets us a small number for a big key, there is possibility that two keys result in same value. The situation where a newly inserted key maps to an already occupied slot in hash table is called collision and must be handled using some collision handling technique.

Ways to handle collisions:

•    Chaining: The idea is to make each cell of hash table point to a linked list of records that have same hash function value. Chaining is simple, but requires additional memory outside the table.

•    Open Addressing: In open addressing, all elements are stored in the hash table itself. Each table entry contains either a record or NIL. When searching for an element, we one by one examine table slots until the desired element is found or it is clear that the element is not in the table.

Tree ® a non-linear data structure that represents the hierarchical relationships among the data objects; a collection of one or more nodes.

Concept of Tree:

·      Node at the top is called as root.

·      A line connecting the parent to the child is edge.

·      Nodes that do not have children are called leaf.

·      Nodes that have the same parent are called sibling.

·      Degree of node is the total sub tree of the node.

·      Height/Depth is the maximum degree of nodes in a tree.

·      If there is a line that connects p to q, then p is called the ancestor of q, and q is a descendant of p.

Binary tree ® a rooted tree data structure in which each node has at most two children.

Types of binary tree:

·         Perfect binary tree ® a binary tree in which every level are at the same depth.

·         Complete binary tree ® a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A perfect binary tree is a complete binary tree.

·         Skewed binary tree ® a binary tree in which each node has at most one child.

·         Balanced binary tree ® a binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther”).

Binary Search Tree

Binary Search Tree ® a node-based binary tree data structure which has the following properties:

•      The left subtree of a node contains only nodes with keys lesser than the node’s key.

•      The right subtree of a node contains only nodes with keys greater than the node’s key.

•      The left and right subtree each must also be a binary search tree.

Basic operations:

·         find(x)       : find key x in the BST

·         insert(x)     : insert new key x into BST

·         remove(x) : remove key x from BST

For viewing PDF file, please click here