Rusty Craft

Data Structures & Complexities

Array

A collection which is ordered and changeable. Allows duplicate members.

Time Complexities

  • Get item at index - O(1)
  • Set item at index - O(1)
  • Insert at last - O(1)
  • Insert intermediate - O(n)
  • Pop last - O(1)
  • Pop intermediate - O(n)
  • Delete last - O(1)
  • Delete intermediate - O(n)
  • Length - O(1)
  • Iteration - O(n)
  • Sort - O(n log n)
  • Search - O(n)
  • Presence - O(n)
  • Min, Max - O(n)
  • Get Slice - O(K)
  • Set Slice - O(k+n)
  • Del Slice - O(n)
  • Extend - O(k)
  • Copy - O(n)
  • Multiply - O(nk)

When to use?

  • If you need to access an element by index often, an array might be a better choice than a linked list or a set.

How to use?

  • Questions to ask
    • Does it require sorting?
      • Increases complexity by O(N logN) time complexity.
    • Does it require more than 1 pointer?
      • https://leetcode.com/articles/two-pointer-technique/
      • https://medium.com/algorithms-and-leetcode/two-pointer-algorithm-explained-with-leetcode-problems-2ed289925acf
      • Does a combination of slow and fast pointer (To reach end faster) help?
      • Does both pointers at 0 index help?
      • Does one pointer at 0 index and another at last index help?
      • Does pointers at mid-point help?
      • Does more than 2 pointers help?
    • Does it require a sliding window?
      • Does it require a window of constant size?
      • Does it require a window of increasing / decreasing size?
    • Can translating to a hash_set make processing feasible?
      • Makes the array unique. And searches in O(1) time complexity.
    • Can translating to a hash_map make processing feasible?
      • Decide the key for the hashmap.
        • Is it an array index, or the value or some other logic?
      • Decide the value for the hashmap.
      • Insert / Delete / lookup in hashmap are O(1) time complexity.
    • Can maintaining a stack help?
      • Maintain a stack of values and pop as per LIFO.
    • Can maintaining a queue help?
      • Maintain a queue of values and pop as per FIFO.
    • Can translating to a tree make processing feasible?
      • Decide between binary tree vs binary search tree?
      • Do we need to maintain a visited set of nodes visited while traversal?
      • Does tree node values have to be a single character / digit or the entire string / number?
      • Does BFS help?
        • Maintain a queue of nodes and pop as per LIFO.
      • Does DFS help?
        • Maintain a stack of nodes and pop as per FIFO.
    • Does divide and conquer help?
      • Divide array into k sub-problems and solve each sub-problem
    • Does back-tracking help?
      • Traverse to an end. Backtrack and traverse in another direction.

Set or Hash Set

A collection which is unordered and unindexed. No duplicate members.

Time Complexities

  • Presence - O(1)
  • Add - O(1)
  • Union s|t - O(len(s) + len(t))
  • Intersection s&t - O(min(len(s), len(t))

When to use?

  • If you need to search for an element often, a set might be a better choice than an array.

Hash Map

A collection which is ordered and changeable. No duplicate members.

Time Complexities

  • Presence - O(1)
  • Copy - O(n)
  • Get Item - O(1)
  • Set item - O(1)
  • Delete item - O(1)
  • Iteration - O(n)

When to use?

  • If you need to store key-value pairs.
  • If you need to often search for a value by key, a hash map might be a better choice than a hash set.

Single Linked List

A sequence of nodes containing a value and a pointer to the next node in the sequence

Time Complexities

  • Access by Index - O(n)
  • Add at beginning - O(1)
  • Add after the given node - O(1)
  • Add at last - O(N)
  • Delete at beginning - O(1)
  • Delete a given node - O(n)
    • Need to traverse till the nth node.
  • Delete last node - O(n)
  • Changing head value - O(1)
  • Changing given node value - O(1)
  • Search a given node - O(n)

When to use?

  • If you need to add or delete a node frequently, a linked list could be a better choice than an array.

Double Linked List

A sequence of nodes containing a value, a pointer to the next node in the sequence and another pointer to the previous node in the sequence.

Time Complexities

  • Access by Index - O(n)
  • Add at beginning - O(1)
  • Add after the given node - O(1)
  • Add at last - O(1)
  • Delete at beginning - O(1)
  • Delete a given node - O(1)
  • Delete last node - O(1)
  • Changing head value - O(1)
  • Changing given node value - O(1)
  • Search a given node - O(n)

When to use?

  • If you need to add or delete a node frequently, a linked list could be a better choice than an array.
  • If you need to add or delete intermediate nodes frequently, a double linked list is better than a single linked list.

Binary Tree

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Time Complexities

  • Search Node - O(n)
  • Insert Node - O(n)
  • Delete Node - O(n)

When to use?

Binary Search Tree

A binary search tree (BST), a special form of a binary tree, satisfies the binary search property:

  • The value in each node must be greater than (or equal to) any values stored in its left subtree.
  • The value in each node must be less than (or equal to) any values stored in its right subtree.

Time Complexities

  • Search Node - O(h)
  • Insert Node - O(h)
  • Delete Node - O(h)

where h is the height of BST.

When to use?

  • To store data in order and need several operations, such as search, insertion or deletion, at the same time, a BST might be a good choice.

Height Balanced Binary Search Tree

A height-balanced (or self-balancing) binary search tree is a binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions. That is, the height of a balanced BST with N nodes is always logN. Also, the height of the two subtrees of every node never differs by more than 1.

Time Complexities

  • Search Node - O(log N)
  • Insert Node - O(log N)
  • Delete Node - O(log N)

where N is no. of nodes of BST.

When to use?

  • To improve performance of BST use-cases. Can provide search, insertion and deletion operations all in O(logN) time complexity.
  • The hash set, HashSet in Java or unordered_set in C++, is implemented by hash, but the height-balanced BST also plays an important role in the hash set. When there are too many elements with the same hash key, it will take O(N) time complexity to look up for a specific element, where N is the number of elements with the same hash key. Typically, the height-balanced BST will be used here to improve the performance from O(N) to O(logN).

N-ary Tree

Time Complexities

  • Search Node - O(n)
  • Insert Node - O(n)
  • Delete Node - O(n)

where n is no. of nodes

Trie

A Trie is a special form of a Nary tree. Typically, a trie is used to store strings. Each Trie node represents a string (a prefix). Each node might have several children nodes while the paths to different children nodes represent different characters. And the strings the child nodes represent will be the origin string represented by the node itself plus the character on the path. The root node is associated with the empty string.

Time Complexities

  • Search word - O(n)
  • Insert word - O(n)
  • Starts with prefix - O(n)

where n is the longest length of all the words in the trie.

When to use?

Stack

Stack is a LIFO data structure; the newest element added will be processed first. Typically, the insert operation is called push in a stack. A new element is always added at the end of the stack.The delete operation, pop, will always remove the last element.

Time Complexities

  • Push - O(1)
  • Pop - O(1)
  • Top - O(1)
  • Size - O(1)
  • Search - O(n)

When to use?

  • For depth first search of tree data structure.

Queue

Queue is a FIFO data structure. The first element added to the queue will be processed first. The insert operation is also called enqueue and the new element is always added at the end of the queue. The delete operation is called dequeue. Dequeue removes the first element.

Time Complexities

  • Enqueue - O(1)
  • Dequeue - O(1)
  • Front - O(1)
  • Rear - O(1)
  • Size - O(1)

When to use?

  • For breadth first search of tree data structure.
  • To process the elements in order, using a queue might be a good choice.

Heap

A detailed explanation is available in this video

Important Links

← Back to home