What is Data Structure
- Data structure is a technique to store and organize data either in computer’s memory or on the disk storage so that it can be used efficiently.
- Data structure are the building blocks of any program. A program built on improper data structure may not work efficiently.
- The key idea behind any data structure is to organize, process, retrieve and to store any data in an efficient manner so that it can respond in appropriate ways.
- An abstract data type (ADT) is the way we look at a data structure, focusing on what it does and ignoring how it does its job.
Application areas of Data Structure
Data structure are used in almost every programs or software systems. Some common examples of data structure are: array, linked list, stack, queue, etc. Data structure are widely used in the following areas. They are:
- Compiler design
- Operating system
- Artificial Intelligence
Why data structure is needed ?
Data structure is much needed because of growing data around the world in every field now a days. Let us discuss some important needs for data structure. They are:
- To increase overall efficiency of the processor by implementing the best suitable technique while searching any specified data into huge amount of data.
- Data structures gives the ability to handle multiple request simultaneously on the web server while searching a particular data irrespective of a group of data.
- Organizing, processing, and retrieving data in a data structure is an easy task which can handle a huge complex data.
- Data structure once implemented can be reused again at other places.Implementation of data structures can be compiled into libraries which can be used by different clients.
Classification of Data Structure
Data structures are generally categorized into two classes:
- Primitive data structure
- Non-primitive data structure
1. Primitive data structure
Primitive data structures are the fundamental data types which are supported by a programming language. The term “data type” , “basic data type” and “primitive data type” are often used interchangeably. For example: integer, real, character and boolean.
2. Non-primitive data structure
Non-primitive data structure are those data structure which are created with the help of primitive data structure. For example: array, linked list, stack, queue,etc. Non-primitive data structure are further classified into two categories. They are:
- I. Linear Data Structure
- II. Non-linear Data Structure
2 (I). Linear Data Structure:
When the data elements are arranged or stored in a linear or sequential manner, then it is said to be a linear data structure. The following are the different types of linear data structure:
- Linked List
Linear data structure is further classified into tow categories based on the data representation. They are:
- a.) Static Linear Data Structure
- b.) Dynamic Linear Data Structure
2 (I) (a) Static Linear Data Structure
Static linear data structure is the way of representation of data elements by means of sequential memory locations. For example:
An array is a collection of similar types of data elements. All the elements stored in an array have the same data type. The elements in an array are stored in a sequential fashion or in consecutive memory locations and is referenced by an index (also known as subscript).
Note: Arrays are of fixed size and insertion and deletion of any element is a difficult task.
Arrays are declared with the following syntax: type name [size]
2 (I) (b) Dynamic Linear Data Structure
Dynamic linear data structure represents the other way of linear data structure where relations between the data elements is implemented by means of links. Size is not fixed here as case of an array, it means one can grow or shrink the size of data elements in dynamic linear data structure easily. The following are the different types of dynamic linear data structure:
- Linked Lists
Linked list is a type of dynamic linear data structure in which elements (also known as nodes) forms a sequential link and form a list. It is also known as self-referential data type.
- Linked list allows programmer to add n numbers of data into the list due its dynamic nature.
- In a linked list every node contains two types of data: data and the pointer or link.
- The last node or element contains a NULL pointer which indicates the end or tail of the list.
Note: Since, memory for a node is dynamically allocated, therefore total number of nodes in the list is limited only by the available memory.
Advantage: Easier to insert or delete data elements.
Disadvantage: Searching is slow and requires more memory space.
A stack is a linear data structure in which insertion and deletion of elements are done at only one end, which is known as the top of the stack.
- Stack is generally called as last-in, first-out (LIFO) structure because last element which is added to the stack becomes the first element which is deleted from the stack.
- In computer memory stack is implemented with the help of an array or a linked list.
- Stack uses two variables TOP and MAX for its operation.
- Variable TOP is used to store the address of the top most element of the stack.
- Variable MAX is used to store the maximum number of elements that the stack can store.
- A stack performs three basic operations: push, pop and peep.
- Push operation adds an element to the top of the stack.
- Pop operation removes the element from the stack.
- Peep operation returns the value of the topmost element of the stack without deleting it.
- if top=NULL, then it means that the stack is empty and if top=MAX-1
- When we try to insert any element into the stack that is already full, then it is said to be overflow condition.
- When we try to delete any element from the stack that is already empty, then it is said to be underflow condition.
A queue is an important dynamic linear non-primitive data structure which is extensively used in computer applications.
- A queue is a first-in, first-out (FIFO) data structure in which the elements that is inserted first becomes the first element that is to be taken out.
- Like stacks, queues can be implemented with the help of an array or linked lists.
- Queue used two variables for its operations: FRONT and REAR
- The elements in a queue are added at one end called the REAR and removed from the other end called the FRONT.
- When we want to insert a new element to the queue .ie. REAR=MAX-1, where MAX is the size of the queue where index starts with zero(0), then the queue is said to be full and this condition is known as overflow condition.
- If FRONT= NULL and REAR=NULL, then there is no element in the queue, it is said to be underflow condition.