Saturday, May 7, 2011

An introduction to Data Structures

Data Structure is one of the very popular buzz words we will be listening in the field of Computer Science. It is used every where, every program and almost every software system. Literally we can say, without a Data Structure we can't write a perfect and an efficient program.

What is a Data Structure?

There are so many definitions available, but i like this one "A data structure is a specialized format for organizing and storing data, so that it can be used efficiently". There are different types of data structures available.

Data Structures can be classified in to two types

  1. Primitive Data Structures
  2. Non Primitive Data Structures

The Data Structures that can be operated directly are called as Primitive Data Structures. Also called as simple data types. Integer, Float, Character are some examples of Primitive Data Structures. These data structures supports very basic operations like creation, deletion, selection and updation.

The data structures which are not primitive are called Non-Primitive Data Structures which means these are data structures that cannot be directly manipulated . For example, Complex number. It can't be expressed as a simple type. Because it will have both imaginary part and real part. Stacks, Queues, Linked lists, Trees are few more examples of non-primitive data structures.

Again this non primitive data types can be divided in to two types

  1. Linear Data Structures
  2. Non-Linear Data Structures

Linear Data Structures are those, in which sequential addition and updation is possible. In another way, Elements in the data structure will form a sequence or adjacent to each other or can be arranged in a straight line. In terms of memory allocation, Contiguous blocks of memory will be allocated. Stacks, Queues, Arrays, Lists are few examples of linear data structures.

Non-Linear Data Structures are those, if one element can be connected to more than two adjacent elements then it is known as non-linear data structure. It's exactly opposite to linear data structures. Trees and Graphs are the examples of Non-Linear data structures.

See here for a full list of data structures and it's types.

The major advantages of data structures are :

  • It gives different level of organizing data.
  • It tells how data can be stored and accessed in its elementary level

We have so many data structures giving different types of data organization. It's good. But how we can select a data structure that can fit into our requirements. Which factors affect the selection of a data structure? To answer these questions, first we should know when a program is said to be good? A program is said to be good,if it meets all our requirements, good speed and efficiency. How you will you achieve the speed and efficiency? To answer this question, first we should know, what is an algorithm? what is the relationship between a program, an algorithm and a Data Structure.

In simple terms,

Algorithm : Steps to solve a problem

Program : Used to implement the algorithm

Data Structure : Organization of data, so that the data can used efficiently by the program.

If we want our program to be good and efficient, the underlying Algorithm and Data Structure should be efficient.

The efficiency of an Algorithm and Data structure will be calculated in terms of Space(Memory) and time.This Time factor is also called as Time Complexity where as Space measure is called as Space Complexity. There are different types notations available to specify the efficiency of a Data Structure and an Algorithm. Those are Big-Oh notation, Small-Oh notation, Big-Omega notation, Small-Omega notation and Theta Notation.

Why we need to know, all these details? Because, Each operation on a data structure will have these efficiency measures(Time Complexity and Space Complexity) which will decide the efficiency of the data structure. in turn it will help us in choosing the data structure for our program.

No comments:

Post a Comment