Introduction to Data Structure
Data Structure is a way of collecting and organizing data in such a way that we can perform operations on these data in an effective way. A data structure is about to organizing data in terms of relationships and storage. Data Structures are the most important part of some Computer Science Algorithms, as they enable the programmers to handle data in an efficient way.
Basic Terminology for Data Structure
Data Structures are the building blocks of any program. Following terminology is used as far as Data Structures are concerned:
1) Data: Data is a collection of facts and figures. Data are values or set of values. For example, Employee Name and its Id is data about an employee.
2) Data Item: Data item is referred to as a single unit of value. Data items are divided into sub-items are group items.
3) Record: Record is a collection of field value of a given entity. The elements of records are mainly called field or members. Records are different from the array by the fact that their number that their field is typically fixed, each field have a name and that each field has a different type.
4) File: File is a collection of various records of one type of entity.
For example, a file containing records of employees in a particular department.
5) Attribute and Entity: An entity represents the class of certain objects. It contains various attributes. Each attribute represents the property of that entity.
6) Field: Field is the elementary unit of information representing the attribute of an entity.
Need for Data Structure
As applications are getting complex and the amount of data getting increased data by day, there may arise the following problems:
1) Processor Speed: To handle a very large amount of data, high-speed processing is required, but as the data is growing day by day to the millions of files, the processor may fail to lead that much of data.
2) Data Search: Consider an inventory search 200 items, if our applications need to search for a particular item, it needs to go through 200 items every time, result in it slowing down the search process.
3) Multiple Requests: The fast server fails while searching the data if numbers of users searching data simultaneously.
Data Structure Classification
Primitive Data Structures: Primitive data structures are those which are the predefined way of storing data by a system. Primitive data structures are classified into char, int, float and double.
Non Primitive Data Structures: The data structures that are derived from primary data types are known as non-primitive. These data structure stores a group of values. Non-primitive data structures are classified into stack, queues, linked list, etc.
Types of Non-Primitive Data Structures:
Linear: A data structure is known as a linear data structure if all the data are arranged into a linear order.
Non-Linear: This data structure does not form a sequence, i.e each element is connected with two or other elements into a non-linear arrangement.
Types of Linear Data Structures:
Array: An array is a collection of similar type of data items. Each data item is called the element of an array. This makes it easier to calculate the position of each element.
Linked List: the Linked list is used to maintain a list in memory. It is a collection of nodes stored at a non-contiguous memory location. Each node of a list contains a pointer to its adjacent node.
Stack: Stack is a basic data structure that represents by a real physical stack and pile, a structure where insertion and deletion of an item take place is called a top stack. The basic implementation of the stack is called LIFO(Last In First Out), to demonstrate the way of accesses data. There are basically two operations that can be performed on stack (1)PUSH: inserting an item into a stack, (2) POP: deleting an item from a stack.
Queue: A queue is a basic data structure that is used throughout the programming. A queue is like the first one in the line is the first one to be served. A queue is FIFO(First One First Out) to demonstrate the way of access data.
Types of Non-Linear Data Structures:
Trees: Tree data structures are based on the parent-child relationship. Each node of a tree may have more than one child except the leaf node whereas each node has almost one parent except the root node.
Graph: A graph consists of nodes and edges. Nodes are defined as vertices and the edges are defined as a line.
Operations in Data Structures:
The operations used in Data Structures are as follows:
1) Insertion: Adding a new data element in a data structure.
2) Deletion: Removal of a data element from a data structure.
3) Searching: Searching a particular data element in a data structure.
4) Sorting: Arranging all the data elements in a specified manner.
5) Merging: Combining two or more than a similar type of data structures in a new data structure of the same type.
6) Traversal: Processing all the elements present in a data structure.
Algorithms of Data Structure
Algorithms are a set of instructions to be executed to get the desired output. An algorithm is a step-by-step process.
There are some categories of algorithms in a data structure that are as followed:
1) Searching: Searching means searching for the desired data element in a data structure. In an algorithm the searching consists of two types :
A)Linear Search: Linear search is much complex than a binary search because the time it takes to a search is correlated with the items to be searched.
(B)Binary Search: Binary search is faster than a linear search, but it works in an ordered sequence.
2)Sorting: Sorting means ordering, or arranging a data element in a specified manner. Sorting is divided into two ways:
A) Merge Sort: Merge sort is a sorting technique. It divides the list into comparable sizes lists, i.e it divides the list into left and right, sorting each other and then merge two stored lists back together.
B) Quick Sort: Quick-sort is used more as compare to merge sort. The algorithms start by picking an item which is known as the pivot, and moving a smaller item before it, while all greater element in the later portion of a list.by