Introduction to Data Structures

A Data Structure is a way of storing and organizing data in a computer so that it can be used efficiently. It refers to the scheme for organizing related piece of information.

Definition: "The organized collection of data in a mathematical or logical way is called data structure."

Liner Data Structure
This is a type of data structure in which elements are organize in a linear fashion. In simple words we can say that data elements in a linear data structure are stored one after another and can be traversed in similar fashion. Due to memory organization is in linear fashion, so this type of data structure can be easily accessed. Example of linear data structure is array, stack, queue and link list.

Non Linear Data Structures

This is a type of data structure in which data is not organized in sequential or linear fashion. A data item in a nonlinear data structure could be attached to several other data elements to reflect a special relationship among them and all the data items cannot be traversed in a single run. Examples of non linear data structure is trees and graphs

Some common examples of data structure are arrays, linked list, queues, stacks, binary trees, graphs and hash tables. 

Array

An array is a group of related data items that share a common name.

An array elements are accessed by using index which is mentioned inside the subscript operator ( [ ] ).

means here 10 elements are sharing a common name a.

Arrays are declared using the following syntax:

        type name[size]; 

Types of arrays:

• One Dimensional Array
• Two Dimensional Array
• Multi-Dimensional Array

Linked List

A linked list is a very flexible dynamic data structure in which elements can be added to or deleted from anywhere.

In linked list, each element called a node is allocated space as it is added to the list. In linked list each node is divided into 2 parts:

➢ Data part
➢ A pointer or link to the next node

Types of linked list:

1. Singly Linked Lists
2. Circular Linked Lists
3. Doubly Linked List
4. Circular Doubly Linked List

Stack

A stack is LIFO (Last-In, First-Out) data structure in which insertion/deletion are done only at one end, known as TOP of the stack.

TOP/TOS is used to store address of top most element of stack.

If TOP=NULL, then stack is empty.

If TOP=MAX-1,then stack is full.

Operations performed on stack are:

1. PUSH operation
2. POP operation
3. PEEP operation

Queue

A queue is a FIFO (First-In, First-Out) data structure in which the elements that is inserted first is the first one to be taken out. 

The elements in a queue are inserted at one end (called the REAR) and deleted from other end (called FRONT).

When REAR=MAX-1, then queue is full.

If FRONT=NULL and REAR=NULL, then queue is empty and there is no element in the queue.

Types of Queues:

1. Circular Queue
2. Deque
3. Priority Queue
4. Multiple Queue

Tree

 A tree is a non-linear data structure mainly represent data containing hierarchical relationship between elements. Topmost node is called root node.

A binary tree is the simplest form of tree which consists of a root node and left & right sub-trees. The root element is pointed by 'root' pointer.

If root=NULL, then the tree is empty.

Graph

A graph is a non linear data structure which is a collection of vertices(nodes) and edges that connect these vertices.

A graph is often viewed as a generalization of the tree structure. Every node in the graph can be connected with any other node. There is a cyclic relationship.

When two nodes are connected via an edge, the two nodes are known as neighbors.

Operations on Data Structures

➢Merging: Combining two lists into a single list.

➢Searching: Finding the location of the element with a given value.

➢Insertion: Adding a new element.

➢Deletion: Removing an element.

➢Traversal: Accessing and Processing each element at least once. It is also called visiting operation. 

➢Sorting: Arranging the elements in some type of order.

➢Splitting: Records in a large file are split into smaller files for processing.

➢Copying: To copy contents of one object to another object.

➢Concatenation: Selecting the records of two similar data structure and combining them.

Applications of Data Structure

1. It is very useful in simulation.
2. It helps in statistical analysis.
3. Helps lot in graphic applications.
4. Compiler Design
5. Database Management System
6. Managing the operating system
7. Numerical Analysis
8. AI

Time and Space Complexity of Algorithm

• To analyze an algorithm means determining the amount of resources (such as time and storage) needed to execute it.

• Efficiency or complexity of an algorithm is stated in terms of time complexity and space complexity.

• Time complexity of an algorithm is basically the running time of the program as a function of the input size.

• Similarly, space complexity of an algorithm is the amount of computer memory required during the program execution, as a function of the input size.

• Time complexity of an algorithm depends on the number of instructions executed. This number is primarily dependent on the size of the program's input and the algorithm used.

• The space needed by a program depends on:

➤  Fixed part includes space needed for storing instructions, constants, variables, and structured variables.

➤  Variable part includes space needed for recursion stack, and for structured variables that are allocated space dynamically during the run-time of the program.

 Abstract Data Type

• An Abstract Data Type (ADT) is the way at which we look at a data structure, focusing on what it does and ignoring how it does its job.
• For example, stacks and queues are perfect examples of an abstract data type. We can implement both these ADTs using an array or a linked list. This demonstrates the "abstract" nature of stacks and queues.
• In C, an Abstract Data Type can be a structure considered without regard to its implementation. It can be thought of as a "description" of the data in the structure with a list of operations that can be performed on the data within that structure.
• The end user is not concerned about the details of how the methods carry out their tasks. They are only aware of the methods that are available to them and are concerned only about calling those methods and getting back the results but not HOW they work.

Algorithm

• An “algorithm" is a formally defined procedure for performing some calculation.  It provides a blueprint to write a program to solve a particular problem.
• It is considered to be an effective procedure for solving a problem in finite number of steps. That is, a well-defined algorithm always provides an answer and is guaranteed to terminate.
• Algorithms are mainly used to achieve software re-use. Once we have an idea or a blueprint of a solution, we can implement it in any high level language like C, C++, Java, so on and so forth.