Table of contents
1.
Introduction
2.
Linear Data Structures
3.
Time Complexity
4.
Space Complexity
5.
Array
5.1.
Time Complexity in arrays of size ‘N’:
5.2.
Space Complexity in Arrays:
6.
String
6.1.
Time Complexity of String containing ‘N’ characters:
6.2.
Space Complexity in Strings:
7.
Queue
7.1.
Time Complexity of the queue containing ‘N’ elements:
7.2.
Space Complexity of the queue:
8.
Stack
8.1.
Time Complexity of a Stack storing ‘N’ elements
8.2.
Space Complexity of Stack
9.
Linked List
9.1.
Time Complexity of linked list storing ‘N’ elements
9.2.
Space Complexity of Linked List
10.
Summary
11.
FAQs
12.
Key Takeaways
Last Updated: Mar 27, 2024

Time and Space Complexity of Linear Data Structures

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

The most important thing for interviews in product-based companies is data structures. Data structure is way of storing and organizing the available data for further use. Data structures are of two types, Linear and Non-linear. Let us discuss linear data structures and their complexity.

Also see, Longest Common Substring and Rabin Karp Algorithm

Linear Data Structures

Linear Data structure are those data structures in which data is stored sequentially, and each element is connected to the previous or next element so that they can be accessed in a single run. Some examples of linear data structures are arrays, stacks, queues, etc.

Let us discuss their time and space complexity.

Time Complexity

Time complexity can be understood as a concept that constitutes the quantification of time taken by an algorithm or code snippet to execute. The time complexity is also a measure of the efficiency, such that the lesser the time is taken by the algorithm, the more its efficiency will be. 

We will be discussing only the worst-case time complexity in this article.

Space Complexity

Space Complexity can be understood as the amount of memory space occupied by a code snippet or algorithm. It is one of the two measures of the efficiency of an algorithm. The lesser the space it takes, the more efficient it is.

Now let’s discuss some linear data structures.

Array

A Data Structure in which a similar type of data is stored at contiguous memory locations is called an array. Array is the most frequently used linear data structure in computer science and due to its connectivity with the previous and next element, it became the inspiration for data structures like linked lists, queues, etc.  

Time Complexity in arrays of size ‘N’:

  • In an array, ‘ARR’ where the address of the first element is ‘A’ and the size of each element is ‘S’, ‘i’th element can be defined as 
    ARR[i] = A + (i - 1) * S
    Thus accessing an element at a specific memory address takes O(1) time, as its relative address can be calculated in constant time.
  • Similarly editing any element of the array takes O(1) time.
  • Inserting a new element at a particular index in arrays is only possible when we skip all the elements before that index, which takes O(N) time.
  • Similarly, deletion operation also takes O(N) time.
  • Searching operation in arrays takes O(N) time without any specific algorithm as we need to iterate and check every element in the array.

Space Complexity in Arrays:

As we do not need any extra space to perform all the operations mentioned above, the space complexity of fetching, over-writing, inserting, or deleting is constant i.e., O(1). Only the space taken to create the array is the auxiliary space.

Also read: Recursion

String

string is a data structure in computer science used to store the sequence of characters. Each character in the string consists of a specific index. Below is its time and space complexity.

Time Complexity of String containing ‘N’ characters:

  • Reading or editing any character stored at a particular index takes O(1) time, as similar to arrays, its relative index can also be calculated in constant time.
  • Inserting and deleting any character at a particular index in strings takes O(N) time, as we need to skip all the characters at previous indices.
  • Searching any character in strings takes O(N) time, as we check for every character present in the string.

Space Complexity in Strings:

As we do not need any extra space to perform all the operations mentioned above, the space complexity of reading, editing, inserting, or deleting is constant i.e., O(1). Only the space taken to create the string is the auxiliary space.

Also see, Array in Javascript

Queue

queue can be defined as a linear data structure, which is simply a collection of entries that are tracked in order, such that the addition of entries happens at one end of the queue, while the removal of entries takes place from the other end. Its order is also known as First In First Out (FIFO). 

Time Complexity of the queue containing ‘N’ elements:

  • To access or edit any element stored in a queue, the time taken is O(N) as to reach any specific element, all the elements after it has to be removed. 
  • The searching operation also takes a total time of O(N), as reaching any specific element isn’t possible without popping the elements stored after it.
  • Operations like insertion or deletion in a queue take constant time i.e., O(1). Only the front element can be removed at a time and insertion can only take place at the back.

Space Complexity of the queue:

Space complexity for each operation in a queue is O(1), as no extra space is required for any operation.

 

Also see, Morris Traversal for Inorder, Application of Linked List , hash function in data structure

Read about Application of Queue in Data Structure here.

Stack

stack is a linear data structure, following a particular order in which operations can be performed. Its order is also known as LIFO(Last In First Out). Stacks are implemented using arrays and linked lists. Let us discuss its efficiency in terms of time and space complexity.

Time Complexity of a Stack storing ‘N’ elements

  • To access or edit any element stored in a stack, the time taken is O(N) as to reach any specific element, all the elements before it has to be removed. 
  • The searching operation also takes a total time of O(N), as reaching any specific element isn’t possible without popping the elements stored before it.
  • Operations like insertion or deletion in a stack take constant time i.e. O(1).

Space Complexity of Stack

Space complexity for each operation in a stack is O(1), as no extra space is required for any operation.

Must Read Python List Operations And Application of Graph in Data Structure

Linked List

A linked list can be understood as a data structure that consists of nodes to store data. Each node consists of a data field and a pointer to the next node. The various elements in a linked list are linked together using pointers. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations.

Its efficiency can be understood with the below complexity analysis.

Time Complexity of linked list storing ‘N’ elements

For insertion in the linked list, the time complexity is O(1) if done on the head, O(N) if done at any other location, as we need to reach that location by traversing the linked list.

For deletion, the time complexity is O(1), if done on the head, O(N), if done at any other location, as we need to reach that location by traversing the linked list.

For searching and accessing any elements, the involved time complexity is O(N).

Space Complexity of Linked List

Space complexity for each operation in a linked list is O(1), as no extra space is required for any operation.

 

You can also read Difference Between Array List and Linked List here.

Must Read Algorithm Types

Summary

Data Structure Insert Delete Access Search
Array O(N) O(N) O(1) O(N)
String O(N) O(N) O(1) O(N)
Queue O(1) O(1) O(N) O(N)
Stack O(1) O(1) O(N) O(N)
Linked List

O(1), if inserted on head 

O(N), elsewhere

O(1), if deleted on head

O(N), elsewhere

O(N) O(N)

Where ‘N’ is the size of the respective data structure.

Read More - Time Complexity of Sorting Algorithms

FAQs

  1. What are non-linear data structures?
    Non-linear data structures are those kinds of data structures that do not contain data in a linear or sequential manner but in a hierarchical manner, therefore its data elements can’t be traversed in a single run only. Examples of non-linear data structures are trees and graphs.
     
  2. Is the complexity for insertion and deletion for a linked list is different for different positions?
    Yes, in a linked list, the time complexity for insertion/deletion at the head is O(1) which is different from insertion/ deletion at other positions which is O(N).
     
  3. Is it possible to decrease the time complexity for searching any element in an array?
    Yes, it is possible to decrease the time complexity for searching in an array with the help of algorithm like Binary Search, etc, for which the elements of the array needs to be in sorted order. The time complexity for searching in an array using a Binary search algorithm is O(log(N)).
     
  4. Which linear data structure is considered to be the best in terms of efficiency?
    All the data structures are proved to be efficient according to the requirements. Every data structure has its own significance, due to which any specific data structure can not be considered as the best in terms of efficiency.  
    If we talk about the most used data structure, then the array can be the specific answer.
     
  5. What is a Data structure?
    A data structure is a way of storing data and organizing it, so that it is easier to use the information stored efficiently, change, add more of it or delete any. In different programs, we use different data structures based on the requirements of the operations further.

Key Takeaways

In the above article, we learned about the time and space complexity of Linear Data Structures, which is a very important concept required in the preparation for all the DSA based interviews. 

To learn more about Data Structures and Algorithms, you can enroll in our course on DSA in Java. Head over to our library section for many such interesting blogs, and if you want to practice problems to enhance your problem-solving skills, you can go to our practice platform Coding Ninjas Studio. Keep practicing and growing.

Live masterclass