What is a linear datastructure?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Linear datastructure is one in which the data items are placed in the memory contiguously i.e. one after the other.
Pros
If we search the first data item, then it is very easy to find the next data items Cons
Size of the array must be know prior to allocation Requires contiguous memory, however if a free memory space is disjoint then this free memory space is not utilized for memory allocation Example of linear datastructure is an array.
[Read More]What is a sorting algorithm?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A sorting algorithm is an algorithm that sorts the data into ascending or descending order.
Examples of such sorting algorithms are:
Introduction to Heap
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Definition of a heap
A heap is a data structure that contains objects which have comparable keys.
Uses of Heap
Some uses for a heap include: keeping track of employee records where the social security number is the key, network edges, events where there is a priority, etc.
Such a heap is called descending heap. In an ascending heap, on the other hand, the key value stored in a node is smaller than the keys of its children nodes.
[Read More]Selection Sort
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
The sorting problem
Input: Array of numbers , unsorted. Eg.
Output : Same numbers sorted in some order, say increasing order. Eg.
Selection Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of in-place comparison sort.
Pseudocode of selection sort
Get the smallest element and put it in the first position Get the next smallest element and put it in the 2nd position ….
[Read More]What is Bucket Sort?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Bucket Sort (alternatively know as bin sort) is an algorithm that sorts numbers and comes under the category of distribution sort.
This sorting algorithm doesn’t compare the numbers but distributes them, it works as follows:
Partition a given array into a number of buckets One-by-one the numbers in the array are placed in the designated bucket Now, only sort the bucket that bare numbers by recursively applying this Bucket Sorting algorithm Now, visiting the buckets in order, the numbers should be sorted Java code:
[Read More]What is a Graph data structure?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Graphs consist of 2 ingredients :
Vertices (V) , also called nodes and can be pictured as dots Edges (E) , the line connecting the nodes. Types of Graphs
Depending on the edges, there two types of graphs:
Undirected Graphs - A graph that entail edges with ordered pair of vertices, however it does not have direction define. Example of such a graph is the ‘Family tree of the Greek gods’ **Directed Graphs (**aka Arcs) - Directed Graph: A graph that entail edges with ordered pair of vertices and has direction indicated with an arrow.
[Read More]Graph Traversal Methods
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
There are two possible traversal methods for a graph:
i. Breadth-First Traversal
ii. Depth-First Traversal
i. Breadth-First Traversal: Traverse all the vertices starting from a given ‘start vertex’. Hence, such a traversal follows the ‘neighbour-first’ principle by considering the following:
- No vertex is visited more than once
- Only those vertices that can be reached are visited
Importantly here, we make use of the Queue data structure. In effect, we house the vertices in the queue that are to be visited soon in the order which they are added to this queue i.
[Read More]What is a Complete Binary Tree?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A strictly binary tree of depth ’d’ in which all the leaves are at level ’d’ i.e. there is non empty left or right subtrees and leaves are populated at the same level.
In a complete binary tree all the internal nodes have equal degree, which means that one node at the root level, two nodes at level 2, four nodes at level 3, eight nodes at level 4, etc, which the below figure represents:
[Read More]Data Structure Introduction
Posted on July 29, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
The basic building block of DATA STRUCTURE are “data” and “information”. So, before discussing data structure, we need to understand what is data and some ground facts about data structure.
many people use the terms “data” and “information” as synonyms but these two terms actually convey very distinct concepts. “data” is defined as a body of facts or figures, which have been gathered systematically for one or more specific purposes
[Read More]Link list ADT
Posted on December 29, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
What is linked list?
Linked List consists of a sequence of nodes. These nodes are made-up of the following:
A Data Field for housing the data item
One or Two Reference/s for pointing at other node/s i.e. pointing to the next/previous node/s.
In this data structure, the nodes are allowed to be inserted and removed at any point in the list in constant time, however random access in not possible.
[Read More]