Array

  • Array is a data structure used to store homogeneous elements at contiguous locations.
  • The size of an array must be provided before storing data.

Arrays have following advantages:

  1. Random access is possible.
  2. Required fixed memory.

Arrays have following limitations:

  1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
  2. Deletion and Insertion are expensive. Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to shift.
    • e.g. For example, in a system if we maintain a sorted list of IDs in an array arrayExample[] = [100, 103, 105, 200, 204].
      • Insertion: if we want to insert a new value 102, then to maintain the sorted order, we have to move all the elements after 100.

      • Deletion: To delete 103 in arrayExample[], everything after 101 has to be moved.

Complexity of Array Data Structure

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

 Array

Θ(1) Θ(n) Θ(n) Θ(n) O(1) O(n)  O(n) O(n) O(n)

 

Explanation:

Let the size of the array be 'n'.
Accessing Time:

O(1)  - This is possible because elements are stored at contiguous locations

 
Search Time:  

O(n) for Sequential Search
O(log n) for Binary Search if Array is sorted


Insertion Time:

O(n) - The worst case occurs when insertion happens at the Beginning of an array and requires shifting all of the elements.


Deletion Time:

O(n) -  The worst case occurs when deletion happens at the Beginning of an array and requires shifting all of the elements

Arrays as an ADT:

  • String
    • Array of characters
  • Stack
    • Array of data type

Linked List

A linked list is a linear data structure (like arrays) where each element is a separate object. Each element (that is the node) of a list is comprising of two items – the data and a reference to the next node.

Why do we need Linked List:

  • Static arrays are structures whose size is fixed at compile time and therefore cannot be extended or reduced to fit the data set.
  • A dynamic array can be extended by doubling the size but there is overhead associated with the operation of copying old data and freeing the memory associated with the old data structure.
  • One potential problem of using arrays for storing data is that arrays require a contiguous block of memory which may not be available if the requested contiguous block is too large.
  • However, the advantages of using arrays are that each element in the array can be accessed very efficiently using an index.
  • However, for applications that can be better managed without using contiguous memory using Linked lists.

Types of Linked List:

  1. Singly Linked List:
    • In this type of linked list, every node stores address or reference of next node in the list and the last node has next address or reference as NULL.
  2. Doubly Linked List:
    • In this type of Linked list, there are two references associated with each node, One of the reference points to the next node and one to the previous node.
    • The advantage of this data structure is that we can traverse in both the directions and for deletion we don’t need to have explicit access to the previous node. 
  3. Circular Linked List:
    • Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end.
    • A circular linked list can be a single circular linked list or doubly circular linked list. The advantage of this data structure is that any node can be made as starting node.
    • This is useful in the implementation of the circular queue in linked list.
  4. Multi-Linked List: 
    • It is a more general linked list with multiple links from nodes. 
    • for example, in storing and organizing a musical song database that can be iterated/viewed/played in chronological (insertion) order, in alphabetical (sorted) order, and in random order (a.k.a. “shuffle” mode).

Advantages over arrays:

  • Dynamic size
  • Ease of insertion/deletion

Drawbacks over arrays:

  • Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists.
  • The array can be accessed very efficiently using an index, as it requires a contiguous block of memory.
  • Extra memory space for a pointer is required with each element of the list.

The complexity of Linked List:

 

Time Complexit

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Singly-Linked List

Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)

Doubly-Linked List

Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)

 

Explanation:

  • Accessing time of an element: O(n)
  • Search time of an element: O(n)
  • Insertion of an element: O(1) If we are at the position where we have to insert an element.
  • Deletion of an element: O(1) If we know the address of node previous the node to be deleted.

Linked List Representation:

 

FYI - 


Stack - Linear Data Structures

The complexity of Stack List:

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Stack

Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)

Queue

A queue or FIFO (first in, first out) is an abstract data type that serves as a collection of elements.

It has following principal operations:

  1. Enqueue - the process of adding an element to the collection.(The element is added from the rear side
  2. Dequeue - the process of removing the first element that was added. (The element is removed from the front side).
  3. Front - Get the front item from queue.
  4. Rear - Get the last item from queue.

A queue is a sequence of elements such that each new element is added (enqueued) to one end, called the back of the queue, and an element is removed (dequeued) from the other end, called the front. Also known as a FIFO (First In First Out) buffer.

There are two ways to implement a queue:

Queue will be useful in following scenarios-

  • When a resource is shared among multiple consumers
    • e.g. Include CPU scheduling, Disk Scheduling, etc.
  • When data is transferred asynchronously between two processes. 
    • e.g. Include IO Buffers, pipes, file IO, etc.

The complexity of Queue:

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Queue

Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)

 

Examples:

  • Applications:
    • CPU Scheduling
    • Disk Scheduling
  • Algorithm;
    • Breadth First Search