Show Menu
Cheatography

Linked List and Hash Table Cheat Sheet by

InsertHead LL

template <class T>
void List<T>::insertHead(T n)
{
ListNode<T> *aNewNode = new ListNode<T>(n);
aNewNode->_next = _head;
_head = aNewNode;
_size++;
};

Remove Head LL

template <class T>
void List<T>::removeHead()
{
   if (_size > 0) {
      ListNode<T> *temp = _head;
      _head = _head->_next;
      delete temp;
      _size--;
    }
}

Iterative Print LL

template <class T>
void List<T>::print(bool withNL) {
ListNode<T> *temp = _head;
   while (temp) {
        cout << temp->_item;
        if (withNL)
          cout << endl;
        else
          cout << " ";
        temp = temp->_next;
     }
     cout << endl;
}

Exist LL

 
template <class T>
bool List<T­>::­exist(T n)
{
for (ListN­ode­<T>* ptr = _head; ptr; ptr = ptr->_­next) {
if (ptr->­_item == n)
{return true;}
}
return false;
}

ReverseOP LL

template <class T>
void List<T>::reverseOp() {
ListNode<T> *previous = NULL; //start from NULL
ListNode<T> *current = _head;
ListNode<T> *next;
while (current != NULL) {
next = current->_next;
current->_next = previous;
previous = current;
current = next;
}
_head = previous;
}
 

Extract Max LL

template <class T>
T List<T>::extractMax()
{
if (_head != NULL) {
ListNode<T>* largest = _head;
ListNode<T>* location = _head;
T max = largest->_item; //
//allocating the node before the largest.
for (ListNode<T>* ptr = _head; ptr; ptr = ptr->_next) {
if (ptr->_next != NULL) {
if (ptr->_next->_item > largest->_item) {
largest = ptr->_next;
location = ptr;
max = largest->_item;
}
}
}
// removing and joining
if (largest == _head) {
_head = largest->_next;
delete largest;
_size--;
}
else {
location->_next = largest->_next;
delete largest;
_size--;
}
return max;
}
return T();
}

Operator Overlo­ading

#include <iostream>
    using namespace std;
    class Cal {
        public:
    static int add(int a,int b){
            return a + b;
        }
    static int add(int a, int b, int c)
        {
            return a + b + c;
        }
    };
    int main(void) {
        Cal C; // class object declaration.
        cout<<C.add(10, 20)<<endl;
        cout<<C.add(12, 20, 23);
       return 0;
    }

Hash Insert

 
hash-i­nse­rt(key, data)
int i = 1; // num of collisions
while (i <= m) { // Try every bucket
int bucket = h(key, i);
if (T[bucket] == null){ // Found an empty bucket
T[bucket] = {key, data}; // Insert key/data
return success; // Return
}
i++;
}
HandeE­rror(); // Table full!
 

Hash Search

 
hash-s­ear­ch(key)
int i = 1;
while (i <= m) {
int bucket = h(key, i);
if (T[bucket] == null) // Empty bucket!
return key-no­t-f­ound;
if (T[buc­ket­].key == key) // Full bucket.
return T[buck­et].data;
i++;
}
return key-no­t-f­ound; // Exhausted entire table

Quick Sort

int partition (int arr[], int low, int high)
{
    int pivot = arr[high]; // pivot
    int i = (low - 1); // Index of smaller element
  
    for (int j = low; j <= high - 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++; // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
  
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
        at right place */
        int pi = partition(arr, low, high);
  
        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Help Us Go Positive!

We offset our carbon usage with Ecologi. Click the link below to help us!

We offset our carbon footprint via Ecologi
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          Numeric Formats Cheat Sheet
          C# & Unity MonoBehaviour Cheat Sheet

          More Cheat Sheets by BearTeddy

          Binary Search Tree C++ Cheat Sheet