DSA(DataStructures and Algo)

The Hot Cake Course of every institute

Algorithmic complexity / Big-O / Asymptotic analysis

Data Structures

  • Arrays

    • Implement an automatically resizing vector.

    • Description:

    • Implement a vector (mutable array with automatic resizing):

      • Practice coding using arrays and pointers, and pointer math to jump to an index instead of using indexing.

      • New raw data array with allocated memory

        • can allocate int array under the hood, just not use its features

        • start with 16, or if starting number is greater, use power of 2 - 16, 32, 64, 128

      • size() - number of items

      • capacity() - number of items it can hold

      • is_empty()

      • at(index) - returns item at given index, blows up if index out of bounds

      • push(item)

      • insert(index, item) - inserts item at index, shifts that index's value and trailing elements to the right

      • prepend(item) - can use insert above at index 0

      • pop() - remove from end, return value

      • delete(index) - delete item at index, shifting all trailing elements left

      • remove(item) - looks for value and removes index holding it (even if in multiple places)

      • find(item) - looks for value and returns first index with that value, -1 if not found

      • resize(new_capacity) // private function

        • when you reach capacity, resize to double the size

        • when popping an item, if size is 1/4 of capacity, resize to half

    • Time

      • O(1) to add/remove at end (amortized for allocations for more space), index, or update

      • O(n) to insert/remove elsewhere

    • Space

      • contiguous in memory, so proximity helps performance

      • space needed = (array capacity, which is >= n) * size of item, but even if 2n, still O(n)

  • Linked Lists

    • Description:

    • C Code (video) - not the whole video, just portions about Node struct and memory allocation

    • Linked List vs Arrays:

    • why you should avoid linked lists (video)

    • Gotcha: you need pointer to pointer knowledge: (for when you pass a pointer to a function that may change the address where that pointer points) This page is just to get a grasp on ptr to ptr. I don't recommend this list traversal style. Readability and maintainability suffer due to cleverness.

    • Implement (I did with tail pointer & without):

      • size() - returns number of data elements in list

      • empty() - bool returns true if empty

      • value_at(index) - returns the value of the nth item (starting at 0 for first)

      • push_front(value) - adds an item to the front of the list

      • pop_front() - remove front item and return its value

      • push_back(value) - adds an item at the end

      • pop_back() - removes end item and returns its value

      • front() - get value of front item

      • back() - get value of end item

      • insert(index, value) - insert value at index, so current item at that index is pointed to by new item at index

      • erase(index) - removes node at given index

      • value_n_from_end(n) - returns the value of the node at nth position from the end of the list

      • reverse() - reverses the list

      • remove_value(value) - removes the first item in the list with this value

    • Doubly-linked List

  • Stack

    • Stacks (video)

    • Will not implement. Implementing with array is trivial

  • Queue

    • Queue (video)

    • Circular buffer/FIFO

    • Implement using linked-list, with tail pointer:

      • enqueue(value) - adds value at position at tail

      • dequeue() - returns value and removes least recently added element (front)

      • empty()

    • Implement using fixed-sized array:

      • enqueue(value) - adds item at end of available storage

      • dequeue() - returns value and removes least recently added element

      • empty()

      • full()

    • Cost:

      • a bad implementation using linked list where you enqueue at head and dequeue at tail would be O(n) because you'd need the next to last element, causing a full traversal each dequeue

      • enqueue: O(1) (amortized, linked list and array [probing])

      • dequeue: O(1) (linked list and array)

      • empty: O(1) (linked list and array)

  • Hash table

More Knowledge

Trees

Sorting

As a summary, here is a visual representation of 15 sorting algorithms. If you need more detail on this subject, see "Sorting" section in Additional Detail on Some Subjects

Graphs

Graphs can be used to represent many problems in computer science, so this section is long, like trees and sorting were.

Even More Knowledge

DSA practice problems:

PreviousThe Daily PlanNextRegular Warmup

Last updated

Was this helpful?