Lists

Linked List

// List.h
#pragma once

template <typename T>
class List {
    public:
    //
    
    private:
        class ListNode {
            public:
                T data; // a place to store data
                ListNode *next; // a pointer pointing to next node
                ListNode(T &data) : data(data), next(NULL);
                // a constructor that inits data with ref
                // and default next to NULL
        }
        
        ListNode *head_;
}




// List.cpp

#include "List.h"

template <typename T>
void List::insertAtFront(const T &d){// d: data
    ListNode *new_node = new ListNode(d);
    new_node->next = head_;
    head_ = new_node;
}


// returning a reference of a pointer to a ListNode inside List<T>
// return the reference of a pointer, so we can update the pointer
// typename on line 40 tells List<T>::ListNode is a type
template <typename T>
typename List<T>::ListNode *&
List<T>::_index(unsigned index) {
    ListNode *&_index_helper(ListNode *n, unsigned i) {
        if(i==0) {
            return n;
        } else {
            return _index_helper(ListNode n->next, i-1); // recursion
        }
    }
    
    return _index_help(_head, index); 
}


template <typename T>
T & List<T>::operator[] (unsigned index) {
    ListNode * node = _index(index);
    return node->data; // returns the reference of data
}
// so we can do things like: myList[1] = 2;


template <typename T>
void List<T>::insert(const T &t, unsigned index) {
    ListNode * &node = _index(index); // get original index 2
    // this is a reference to the pointer to original index 2 node
    // it is the reference of node 1's 'next'
    ListNode *new_node = new ListNode(t); // create new node
    new_node->next = node; // put original index 2 as this node's next
    node = new_node; // update original pointer from original index 2
    // to new node
}


template <typename T>
void List<T>::delete(unsigned index) {
    ListNode * &node = _index(index);
    ListNode * temp = node;
    node = node->next;
    delete temp;
}

Other Notes

• O(1) insert/remove at front or back
• O(1) insert/remove after a given element
• O(n) lookup by index

Array List

#pragma once
template <typename T>
class List {
    public:
    private:
        T * data_; // an array T[]
        unsigned size_;
        unsigned capacity_;
}

When the array does not have enough empty space, it will need to expand (by creating a larger new array, copying existing items then delete the original array).

Resizing strategy

size n to size n+2: Amortized O(n) for inserting each item (copy cost)

size n to size 2n: Amortized O(1) for inserting each item but on average will have more space wasted.

std::vector

Standard implementation for array list in C++.

Other Notes

• O(1) amortized insert/remove at front or back
• O(n) insert/remove at any location (cost of shifting elements)
• O(1) lookup by index

Stack & Queue

Queue

Order: FIFO (first in first out)

Implementation: On top of list with enqueue() to add and dequeue to remove.

Runtime: O(1) for both enqueue and dequeue.

Stack

Order: LIFO (last in first out)

Implementation: On top of list with push() to add, and pop() to remove.

Runtime: O(1) for both push and pop.

ref: https://courses.engr.illinois.edu/cs225/fa2020/