DSA goes brrr...

What is a Data Structure?

A data structure (DS) is a way of organizing data so that it can be used effectively. It's a way of organizing data in some fashion so that later on it can be accessed queried or even updated quickly and easily.

Why Data Structures?

• They are essential ingredients in creating fast and powerful algorithms.
• They help to manage and organize data.
• They make code cleaner and easier to understand.

Abstract Data Types vs. Data Structures

An abstract data type (ADT) is an abstraction of a data structure which provides only the interface to which a data structure must adhere to.

The interface doesn't give any spedific details about how something should be implemented or in what programming language.

Examples:

Abstraction (ADT)	Implementation (DS)
List	Dynamic Array, Linked List
Queue	LL based Queue, Stack based Queue, Array based Queue
Map	Tree Map, Hash Map / Hash Table
Vehicle	Golf Cart, Bicycle, Car

Computational Complexity Analysis

• How much time does an algorithm need to finish?
• How much space does an algorithm need for its computation?

Big-O Notation:

Gives an upper bound of the complexity in the worst case, helping to quantify performance as the input size becomes arbitrarily large.

Example of worst case - finding an element in an unordered list and the element is not even present in the list.

Below are the complexities ordered in from smallest to largest: n - size of the input

1. Constant time : O(1)
2. Logarithmic time : O(log(n))
3. Linear time : O(n)
4. Linearithmic time: O(nlog(n))
5. Quadratic time : O(n^2)
6. Cubic time : O(n^3)
7. Exponential time : O(b^n), b > 1
8. Factorial time : O(n!)

Big-O Properties:

O(n + c)  =  O(n)
   O(nc)  =  O(n), c > 0

We can ignore constants as when n is an arbitrarily large number then adding or multiplying it with a constant doesn't change many things. But of course this is all theoritical, in real world if your constant is of size let's say a billion then that's probably gonna have a substantial impact on the running time of the algorithm.

Let f be a function that describes the runnning time of a particular algorithm for an input size of n:

   f(n)  =  7log(n)^3 + 10n^2 + 2n^3 + 8
O(f(n))  =  O(n^3)

Big-O Examples:

The following run in constant time: O(1)

a := 1
b := 2
c := a + 5 * b

i = 0
While i < 10 Do
    i = i + 1

In both of the examples above the time complexity is O(1) because they don't depend on n (input size) at all.

The following run in linear time: O(n)

i := 0
While i < n Do
    i = i + 1

   f(n)  =  n
O(f(n))  =  O(n)

i := 0
While i < n Do
    i = i + 5

   f(n)  =  n / 5
O(f(n))  =  O(n / 5)  ~=  O(n)

In both of the examples above the time complexity remains O(n) as the loop depends upon the input size n, note that the complexity of the second loop is 5 times faster than the first one for the same input n but as we ignore constants it's generalized to O(n).

Both of the following run in quadratic time. The first may be obvious since n work is done n times - n * n = o(n^2), but what about the second one?

For (i := 0 ; i < n ; i = i + 1)
    For (j := 0 ; j < n ; j = j + 1)

   f(n)  =  n * n  =  n^2
O(f(n))  =  O(n^2)

For (i := 0 ; i < n ; i = i + 1)
    For (j := i ; j < n ; j = j + 1)
              ^ replaced 0 with i

   f(n)  =  n * n  =  n^2
O(f(n))  =  O(n^2)

Let's understand the 2nd one, for a moment just focus on the second/inner loop. Since i goes from [0, n) the amount of looping done is directly propotional by what i is. Remark that if i = 0, we do n work, if i = 1 we do n - 1 work, if i = 2 we do n - 2 work, and so on...

So the question becomes what is: n + (n - 1) + (n - 2) + ... + 3 + 2 + 1? Remarkably this truns out to be n(n + 1) / 2, so the time complexity becomes O(n * (n + 1) / 2) = O(n^2 / 2 + n / 2) = O(n^2).

Suppose we have a sorted array and we want to find the index of a particular value in the array, it it exists. What is the time complexity of the following algorithm?

low := 0
high := n - 1
While low <= high Do
    mid := (low + high) / 2

    If array[mid] == value: return mid
    Else If array[mid] < value: low = mid + 1
    Else high = mid - 1
return -1 // Value not found

Binary Search yeilds the time complexity of O(log_2(n)) => O(log(n))

Can you calculate the time complexity of the following example:

i := 0
While i < n Do
    j = 0
    While j < 3 * n Do
        j = j + 1

    j = 0
    While j < 2 * n Do
        j = j + 1

Let's calculate:

• outer loop takes O(n) time.
• first inner loop takes O(3 * n) time.
• second inner loop takes O(2 * n) time.
• total time complexity - O(n * (3n + 2n)) = O(n * 5n) = O(5n^2).

Hence, the final time complexity of this algorithm is O(n^2).

Try to calcualte this one too:

i := 0
While i < 3 * n Do
    j := 10
    While j <= 50:
        j += 10

    j = 0
    While j < n * n * n Do
        j = j + 2
    i = i + 1

Looks complex? let's break it down:

• outer loop takes O(3n) time.
• first inner loop takes O(4) time.
• second inner loop takes O(n^3 / 2) time as we increment by 2 each time.
• total time complexity - O( 3n * ( 4 + (n^3 / 2) ) ) = O( 12n + (3n^4 / 2) ).

Hence, the final time complexity of this algorithm is O(n^4).

Other examples:

• Finding all the subsets of a set - O(2^n).
• Finding all permutations of a string - O(n!).
• Sorting using mergesort - O(nlog(n)).
• Iterating over all the cells in a matrix of size n by m - O(nm).

---

Static & Dynamic Arrays

A static array is a fixed length container containing n elements indexable form the range [0, n - 1].

Q. What is meant by being 'indexable'? A. This means that each index in the array can be referenced with a number.

Static arrays are given a contiguous memory, all the addresses are adjacent in these arrays.

When and where is a Static Array used?

They are used everywhere, it's hard to make a program that doesn't use them.

1. Storing and accessing sequential data.
2. Temporarily storing objects.
3. Used by IO routines (functions) as buffers.
4. Lookup tables and inverse lookup tables.
5. Can be used to return multiple values from a function.
6. Used in dynamic programming to cache solutions to subproblems.

Complexity

	Static Arrays	Dynamic Arrays
Access	O(1)	O(1)
Search	O(n)	O(n)
Insertion	NA	O(n)
Appending	NA	O(1)
Deletion	NA	O(n)

Static arrays are fixed sized containers so we can't insert, append or delete from them. Whereas dynamic arrays can grow and shrink in size (allowing for insertion, appending, and deletion.)

Q. How can we implement a dynamic array?

A: One way is to use a static array!

1. Create a static array with an initial capacity.
2. Add elements to the underlying static array, keep track of the number of elements.
3. If adding another element would exceed the capacity then create another array with twice the capacity and copy the original elements into it.

Ex: suppose we create a dynamic array of initial capacity as 2

[null, null]

insert 7
[7, null]

insert 10
[7, 10]

insert -3: capacity exceeded > new array of capacity twice before
[7, 10, -3, null]

insert 13
[7, 10, -3, 13]

insert -6: capacity exceeded > new array of capacity twice before
[7, 10, -3, 13, -6, null, null, null]

and so on...

NOTE: The reverse is not true when you delete elements such that the capacity can be halved, this is to prevent a performance issue called thrashing, if you repeatedly add and remove an element right at the capacity threshold, the program would waste valuable processing time constantly allocating and deallocating memory.

But if you explicitly want to reduce the capacity you can use shrink_to_fit() method on a std:vector in c++, trimToSize() method on an ArrayList in Java, in Python you can't expose capacity controls manually but creating a new list would do the job my_list = list(my_list).

You can view the implementation of Dynamic Arrays in the dynamic_array folder.

Linked List

A linked list is a sequential list of nodes that hold data and also points to other nodes also containing data.

+------+------+------+------+------+
| Data | Data | Data | Data | NULL |
+------+------+------+------+------+

(the first node points to the second node and the second points to the third and so on, note that the last node points to NULL.)

Where are Linked List used?

• Used in many List, Queue, and Stack implementations.
• Great for creating circular lists.
• Used in separate chaining, which is used to deal with hashing collisions in certain Hashtable implementations.
• Often used in the implementation of adjacency lists for graphs.
• Can be used to implement features like undo and redo, or going back to previous or next links a browser tab.

NOTE: I am thinking of creating a mini-project which implements the feature of undo and redo using linked lists.

Terminology

1. Head: the first node in the linked list.
2. Tail: the last node in the linked list.
3. Pointer: reference to another node.
4. Node: an object containing data and pointer(s).

Singly & Doubly Linked Lists

Singly Linked List: only hold a reference to the next node. In the implementation you always maintain a reference to the head to the linked list and a reference to the tail node for quick additions/removals.

• Pros: Uses less memory and is simpler to implement.
• Cons: Can't traverse backwards.

Double Linked List: each node holds a reference to the previous and next node. In the implementation you always maintain a reference to head and the tail to do quick additions/removals from botht the ends of the list.

• Pros: Can traverse backwards
• Cons: Uses 2x memory to for storing references.

Complexity Analysis

              Singly   Doulbly
               List     List
+-----------+--------+--------+
| Search    |  O(n)  |  O(n)  |
+-----------+--------+--------+
| Insert/   |        |        |
| Delete    |  O(1)  |  O(1)  |
| at head   |        |        |
+-----------+--------+--------+
|  Insert   |        |        |
|    at     |  O(1)  |  O(1)  |
|   tail    |        |        |
+-----------+--------+--------+
|  Delete   |        |        |
|    at     |  O(n)  |  O(1)  |
|   tail    |        |        |
+-----------+--------+--------+
| Insert/   |        |        |
| Delete    |  O(n)  |  O(n)  |
| in middle |        |        |
+-----------+--------+--------+

The implementation code for Singly, Doubly and Circular Linked List is in the linked_list folder.