Data structures are the data structured in a way for efficient use by the users. As the computer program relies hugely on the data and also requires a large volume of data for its performance, therefore it is highly important to arrange the data. This arrangement of data in organized structures is known as a data structure.
Storing of the data in data structures allows the access, modifications, and other operations that can be carried over the data elements. The arrangement of the data is mainly done in a computer and therefore proper algorithms are required to carry on operations with the data structures. Reducing space and decreasing the time complexity of different tasks is the main aim of data structures.
The most important points in a data structure are:
- A large amount of data is organized through every type of data structure.
- A particular principle is followed by every data structure.
- The basic principle of the data structure should be followed even if any operations are carried out over the data structure.
Arrangement of the data within a data structure can follow different orders. A data structure is therefore classified according to the way of arrangement of the data. Basically, there are two types of data structure.
- Primitive data structure
- Non-primitive data structure
The primitive type of data structure includes the predefined data structures such as char, float, int, and double.
The non-primitive data structures are used to store the collection of elements. This data structure can be further categorized into
- Linear data structure
- Non-Linear data structure.
Read: Learn the differences between linear and non linear data structure
In this article, we will be mainly discussing the data structure storing data linearly.
Table of Contents
Linear Data Structure
It is a type of data structure where the arrangement of the data follows a linear trend. The data elements are arranged linearly such that the element is directly linked to its previous and the next elements. As the elements are stored linearly, the structure supports single-level storage of data. And hence, traversal of the data is achieved through a single run only.
Characteristics
- It is a type of data structure where data is stored and managed in a linear sequence.
- Data elements in the sequence are linked to one after the other.
- Implementation of the linear structure of data in a computer’s memory is easy as the data is organized sequentially.
- Array, queue. Stack, linked list, etc. are examples of this type of structure.
- The data elements stored in the data structure have only one relationship.
- Traversal of the data elements can be carried out in a single run as the data elements are stored in a single level.
- There is poor utilization of the computer memory if a structure storing data linearly is implemented.
- With the increase in the size of the data structure, the time complexity of the structure increases.
These structures can therefore be summarized as a type of data structure where the elements are stored sequentially and follow the order where:
- Only one first element is present which has one next element.
- Only one last element is present which has one previous element.
- All the other elements in the data structure have a previous and a next element
List of data structure in a linear type of data structure
1. Array
The array is that type of structure that stores homogeneous elements at memory locations which are contiguous. The same types of objects are stored sequentially in an array. The main idea of an array is that multiple data of the same type can be stored together. Before storing the data in an array, the size of the array has to be defined. Any element in the array can be accessed or modified and the elements stored are indexed to identify their locations.
An array can be explained with the help of a simple example of storing the marks for all the students in a class. Suppose there are 20 students, then the size of the array has to be mentioned as 20. Marks of all the students can then be stored in the created array without the need for creating separate variables for marks for every student. Simple traversal of the array can lead to the access of the elements.
2. Linked list
The linked list is that type of data structure where separate objects are stored sequentially. Every object stored in the data structure will have the data and a reference to the next object. The last node of the linked list has a reference to null. The first element of the linked list is known as the head of the list. There are many differences between a linked list to the other types of data structures. These are in terms of memory allocation, the internal structure of the data structure, and the operations carried on the linked list.
Getting to an element in a linked list is a slower process compared to the arrays as the indexing in an array helps in locating the element. However, in the case of a linked list, the process has to start from the head and traverse through the whole structure until the desired element is reached. In contrast to this, the advantage of using linked lists is that the addition or deletion of elements at the beginning can be done very quickly.
There are three types of linked lists:
- Single Linked List: This type of structure has the address or the reference of the next node stored in the current node. Therefore, a node which at the last has the address and reference as a NULL. Example: A->B->C->D->E->NULL.
- A Double Linked List: As the name suggests, each node has two references associated with it. One reference directs to the previous node while the second reference points to the next node. Traversal is possible in both directions as reference is available for the previous nodes. Also, explicit access is not required for deletion. Example: NULL<-A<->B<->C<->D<->E->NULL.
- Linked List which is circular: The nodes in a circular linked list are connected in a way that a circle is formed. As the linked list is circular there is no end and hence no NULL. This type of linked list can follow the structure of both singly or doubly. There is no specific starting node and any node from the data can be the starting node. The reference of the last node points towards the first node. Example: A->B->C->D->E.
Properties of a linked list are:
-
- Access time: O(n)
- Searching time: O(n)
- Adding element: O(1)
- Deleting an Element : O(1)
3. Stack
The stack is another type of structure where the elements stored in the data structure follow the rule of LIFO (last in, first out) or FILO (First In Last Out). Two types of operations are associated with a stack i.e. push and pop. Push is used when an element has to be added to the collection and pop is used when the last element has to be removed from the collection. Extraction can be carried out for only the last added element.
Properties of a stack are:
- Adding element: O(1)
- deleting element: O(1)
- Accessing Time: O(n) [Worst Case]
- Only one end allows inserting and deleting an element.
Examples of the stack include the removal of recursion. In scenarios where a word has to be reversed, or while using editors when the word that was last typed will be removed first (using an undo operation), stacks are used. If you want to try interesting data structure projects, click to read this article.
4. Queue
Queue is the type of data structure where the elements to be stored follow the rule of First In First Out (FIFO). The particular order is followed for performing the required operations over the elements. The difference of a queue from that of a stack lies in the removal of an element, where the most recently added object is removed first in a stack. Whereas, in the case of a queue, the element that was added first is removed first.
Both the end of the data structure is used for the insertion and the removal of data. The two main operations governing the structure of the queue are enqueue, and dequeue. Enqueue refers to the process where inserting an element is allowed to the collection of data and dequeue refers to the process where removal of elements is allowed, which is the first element in the queue in this case.
Properties of a queue are:
- Inserting an element: O(1)
- Deleting an element: O(1)
- Accessing Time: O(n)
Example of the queue: Similar to those queues made while waiting for the bus or anywhere, the data structure too follows the same pattern. We can imagine a person waiting for the bus and standing at the first position as the person that came to the queue first. This person will be the first one who will get onto a bus, i.e. exit the queue. Queues are applied when multiple users are sharing the same resources and they have to be served on the basis of who has come first on the server.
Conclusion
An increase in the size of the data has necessitated the efficient use of data structures in computer programs. Data if not organized in a structured manner, the performance of tasks over the elements becomes difficult.
For a hassle-free operation, it is always important to organize it so that easy and effective operations can be carried out by computer programs. If the data elements are organized in sequential order then it is known as a linear data structure whereas if the data elements are arranged in a non-linear way, it is termed a non-linear structure.
Wide application of data structure has been observed in machine learning languages, real-life problems, etc. People, who are dreaming to work in this field, should be able to master these concepts.
If you are want to learn more, then check out the upGrad Executive PG Programme in Data Science which provides a platform to transform you into successful data scientists. Designed for any mid-level professionals, the data science course will expose you to all the theoretical and practical knowledge required for your success. So why wait for other options, when success is just a click away. If any assistance is required, we will be happy to help you.
