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.
Learn data science courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs, or Masters Programs to fast-track your career.
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
What is Linear Data Structure: Definition and Characteristics
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.
Must read: Learn excel online free!
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
Our learners also read: Data structures and Algorithms free course!
upGrad’s Exclusive Data Science Webinar for you –
How to Build Digital & Data Mindset
Explore our Popular Data Science Courses
| Executive Post Graduate Programme in Data Science from IIITB | Professional Certificate Program in Data Science for Business Decision Making | Master of Science in Data Science from University of Arizona |
| Advanced Certificate Programme in Data Science from IIITB | Professional Certificate Program in Data Science and Business Analytics from University of Maryland | Data Science Courses |
You can use linear data structure in C, C++, Python, JavaScript, or any other programming language you are familiar with.
If you get baffled when given a list of linear structures and wonder which of the following is a linear data structure, here’s a rundown of the types.
Types of Linear Data Structures
Operations performed on linear data structure include insertion, deletion, searching, traversing, and sorting. All these operations serve as the foundation for linear data structures.
Discussed below are the linear data structure types and the corresponding operations on linear data structures that can be performed. You can also look for linear data structure examples to develop a robust idea.
1. Array
The array is that type of structure that stores hom*ogeneous 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.
Arrays incorporate the use of zero-based indexing techniques. This means users can access the first element with an index of 0, the second with an index of 1, and so on. Another remarkable feature of this linear data structure is that arrays provide a constant time of O(1) to access the elements, which means that it takes equal time to access any element in the series, disregarding the size of the array.
Types of array:
- One-dimensional array: This is a simple form of array that contains elements, all of which are the same type of data, in a single row.
- Two-dimensional array: This is also known as a matrix. This type of data structure has rows and columns and appears like a grid. The elements can be accessed using two indices- one for column and one for row.
- Multi-dimensional array: These arrays have more than two dimensions.
Operations Performed on Arrays:
The following operations can be performed on arrays:
- Accessing an element: Accessing an element by its index is an essential operation that can be performed on arrays. It is a constant time operation with a time complexity of O(1).
- Inserting or deleting elements: Inserting elements at the end of an array is a constant-time operation having complexity O(1). But inserting an element at the beginning takes O(n) time since all the elements have to be shifted.
The same goes for deletion of elements in an array.
- Searching for elements: For unsorted data, linear search takes O(n) time, and for sorted data, binary search takes O(logn) time.
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.
Our learners also read: Free Python Course with Certification
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.
Types of stack:
There are two types of stacks:
- Fixed-size stack: This kind of stack does not grow or shrink. Once full, any attempt to add an element will lead to an overflow error. Similarly, an attempt to remove an element will also display an underflow error.
- Dynamic size stack: This kind of stack can grow or shrink. When a stack is full or empty, it can automatically resize to accommodate a new element or shrink in size.
Other operations are:
- top(): This operation helps to return the element that has been inserted last and is at the top without removing it.
- size(): This operation indicates the total number of elements the stack contains.
- isEmpty(): This operation helps to identify if a stack is empty.
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.
Top Data Science Skills to Learn
| Top Data Science Skills to Learn | ||
| 1 | Data Analysis Course | Inferential Statistics Courses |
| 2 | Hypothesis Testing Programs | Logistic Regression Courses |
| 3 | Linear Regression Courses | Linear Algebra for Analysis |
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.
Following is a list of the different types of queues:
- Input restricted queue: In this kind of queue, one can only insert inputs from one end. Deletion, however, can be done from both ends.
- Output restricted queue: This is just the reverse of input restricted queues. Here, the input can be taken from both ends, but deletion can only be done from one end.
- Circular queue: In this kind of queue, the first and the last positions are connected to one another, resulting in a circular structure.
- Double-ended queue: This kind of operation supports insertion and deletion from both ends.
- Priority queue: In this kind of queue, elements can be accessed based on priority assigned to them.
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)
Other queue operations are:
- peek() or front(): This helps to acquire the data element available at the queue’s front node without actually eliminating it.
- rear(): This operation returns an element at the rear without it being removed.
- ifNull(): Finds out if a queue is empty.
- ifFull(): Finds out if a queue is full.
Have a look at this linear data structure example.
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.
Read our popular Data Science Articles
| Data Science Career Path: A Comprehensive Career Guide | Data Science Career Growth: The Future of Work is here | Why is Data Science Important? 8 Ways Data Science Brings Value to the Business |
| Relevance of Data Science for Managers | The Ultimate Data Science Cheat Sheet Every Data Scientists Should Have | Top 6 Reasons Why You Should Become a Data Scientist |
| A Day in the Life of Data Scientist: What do they do? | Myth Busted: Data Science doesn’t need Coding | Business Intelligence vs Data Science: What are the differences? |
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.
