Data Structures

Arrays

The most fundamental idea of an Array is that it is a contiguous memory space.

This space must be informed in it's allocation, and you cannot grow it, only reallocate it to a new bigger or smaller Array.

Getting at specific index

Takes the width of the type (Bytes) and you multiply by the offset of the position you want.

This take $O(1)$ , since you know the type width and the offset, you just multiply them.

Inserting at specific index (Not really inserting)

The content of the index is overwritten, since you cannot just grow the array size.

Also $O(1)$ , since accessing at specific position is constant.

Deleting at specific index (Not really deleting)

Overwrite the content of the index to some specific null value. (Not necessarily null)

Also $O(1)$ , since it is basically the same as inserting.

Linked List

A linked list is objects that are linked. This means that each object in this list, only knows who is their next object.

The weakness of a Linked List in terms of costs, is the traverse cost to get to an element.

There are also Doubled Linked Lists, where each object knows the previous and next object.

Node Interface

interface LinkedListNode<T> {
    value: T;
    next?: LinkedListNode<T>;
}

interface DoubledLinkedListNode<T> {
    value: T;
    next?: DoubledLinkedListNode<T>;
    previous?: DoubledLinkedListNode<T>;
}

Getting specific value or at specific position

You will have to run through the linked list, since there are no indexes, until you find the desired value.

Takes $O(1)$ , for head and tail of the list. (constant time for tail only IF you have it's reference saved)

Otherwise takes $O(N)$ , for middle elements.

Inserting at specific position

Desconsidering the asymptotic time to find and get to the position. Inserting a new element is just updating the next property of the existent object, and updating the next from the new object. (In Doubled Linked List, there is also the previous property, and it must update the previous element and the next element, of the inserted position)

Takes $O(1)$ , for the head of the list.

It would also take $O(1)$ , for the list tail IF you have it's reference saved.

Otherwise for middle elements it will take $O(N)$ , since you will have to go through the list until you reach the desired position.

Deleting at specific position

Deleting is the same as inserting, you only update next property from the previous object. (In Doubled Linked List, you also update the previous property from the next object)

Takes $O(1)$ , for the head of the list.

It would also take $O(1)$ , for the list tail IF you have it's reference saved.

Otherwise for middle elements it will take $O(N)$ , since you will have to go through the list until you reach the desired position.

Implementation

type Node<T> = {
    value: T;
    prev?: Node<T>;
    next?: Node<T>;
}

class DoubledLinkedList<T> {
    public length: number = 0;
    private head?: Node<T>;
    private tail?: Node<T>;
    
    prepend(item: T): void {
        let newNode: Node<T> = {
            value: item,
            prev: undefined,
            next: this.head
        }
        if (!this.head) this.tail = newNode;
        else this.head.prev = newNode;
        this.head = newNode;
        this.length++;
    }
    
    insertAt(item: T, idx: number): void {
        if (idx <= 0) this.prepend(item);
        else if (idx >= this.length) this.append(item);
        
        let elRight: Node<T> | undefined = this.getNodeAt(idx);
        let elLeft: Node<T> | undefined = elRight?.prev;
        
        let newNode: Node<T> = {
            value: item,
            prev: elLeft,
            next: elRight
        }
        
        elLeft.next = newNode;
        elRight.prev = newNode;
        this.length++;
    }
    
    append(item: T): void {
        let newNode: Node<T> = {
            value: item,
            prev: this.tail,
            next: undefined
        }
        if (!this.tail) this.head = newNode;
        else this.tail.next = newNode;
        this.tail = newNode;
        this.length++;
    }
    
    remove(item: T): T | undefined {
        let removedNode = this.head;
        for (; removedNode && removedNode.value !== item;)
            removedNode = removedNode.next;
        if (!removedNode) return removedNode;
        
        let elRight: Node<T> | undefined = removedNode?.next;
        let elLeft: Node<T> | undefined = removedNode?.prev;
        
        if (!elRight && !elLeft) {
            this.head = undefined;
            this.tail = undefined;
        }
        else {
            if (elRight) elRight.prev = elLeft;
            if (elLeft) elLeft.next = elRight;
            if (!elRight.prev) this.head = elRight;
            if (!elLeft.next) this.tail = elLeft;
        }
        this.length--;
        return removedNode.value;
    }
    
    removeAt(idx: number): T | undefined {
        let removedNode = this.getNodeAt(idx);
        if (!removedNode) return removedNode;
        
        let elRight: Node<T> | undefined = removedNode?.next;
        let elLeft: Node<T> | undefined = removedNode?.prev;
        
        if (!elRight && !elLeft) {
            this.head = undefined;
            this.tail = undefined;
        }
        else {
            if (elRight) elRight.prev = elLeft;
            if (elLeft) elLeft.next = elRight;
            if (!elRight.prev) this.head = elRight;
            if (!elLeft.next) this.tail = elLeft;
        }
        this.length--;
        return removedNode.value;
    }
    
    private getNodeAt(idx: number): Node<T> | undefined {
        let curr = this.head;
        for (let i = 0; i < idx && curr; i++)
            curr = curr.next;
        return curr;
    }
    
    get(idx: number): T | undefined {
        let curr = this.head;
        for (let i = 0; i < idx && curr; i++)
            curr = curr.next;
        return curr?.value;
    }
}

Ring Buffer

Can be seen as Arrays that have a defined head and tail property.

You work inserting data in the middle of this Array which we will call Buffer. And you may insert in the head or in the tail, meaning these properties will end up creating an abstract Array inside this Buffer.

Once the tail reach N size you then tail % N, and make it ring around to the begining.

When tail = head then the buffer is full and must grow.

They are good if you need a DS that maintains order, but have data being flushed periodicaly, and want your memory allocation to be stable and not spiking from time to time.

Like a data structure to maintin logs.

HashMap

Terminology

load factor

The amount of data points vs the amount of storage. (data.len / storage.capacity)

key

A value that is hashable and is used to look up data. (The hash has to be consistent)

value

A value that is associated with a key.

collision

When 2 keys map to the same cell.

Hashing

Because a Map has a limited amount of space, hashing keys will most certainly end up in collisions of hashes.

The collision happens because the produced hash will have to be modularized so that it always points to a valid slot in the Map.

The less collision hashes a hash function generates, the closest to $O(1)$ the hashmap can stay for its operations.

There are several ways of dealing with collisions, for instace:

Backof

Avoiding backof

A way to avoid the linear or exponencial backof when two hashes collide, is to make these colliding hashes to ocupy the same slot in the Map, instead of finding an unocuppied slot.

Meaning that a slot would consist of a Linked List or similar DS.

Growing Maps Data Storage

As the Data Storage become close to full, the number of collisions increase, thus making the Map less efficient, no matter the strategy used for dealing with collisions.

The bigger the load factor the less $O(1)$ the Map is.

The ideal limit load factor is about 0.7. Above that value, the Data Storage should grow.

Growing the Data Storage means, re-hashing all the existing { key, value }.

Implementation

LRU

Least Recently Used is a caching mechanism. It evicts the least recently used item.

In LRU, you mix a Doubled Linked List with a HashMap.

The Doubled Linked List is used to maintain the order for the accessed items. This is crucial to keep the trimCache() $O(1)$ .
The HashMap is used to access Linked List items in $O(1)$ .

With this mix, you can access and update any cached values in constant time.

Implementation

type Node<T> = {
    value: T;
    next?: Node<T>,
    prev?: Node<T>
}

export default class LRU<K, V> {
    private length: number = 0;
    private head?: Node<T> | undefined = undefined;
    private tail?: Node<T> | undefined = undefined;
    private lookup = new Map<K, Node<V>>();
    private reverseLookup = new Map<Node<V>, K>();
    
    constructor(private capacity: number = 10) {}
    
    update(key: K, value?: V): void {
        let node = this.lookup.get(key);
        if (!node) {
            if (!value) return;
            node = { value } as Node<V>;
            this.length++;
            this.prepend(node);
            this.trimCache();
            this.lookup.set(key, node);
            this.reverseLookup.set(node, key);
        }
        // Key already exists
        else {
            this.detach(node);
            this.prepend(node);
            if (value) node.value = value;
        }
    }
    
    get(key: K): V | undefined {
        // Check cache for existance
        const node = this.lookup.get(key);
        if (!node) return undefined;
        
        // Update the value we found and move it to the front
        this.detach(node);
        this.prepend(node);
        
        // Return out the value found
        return node.value;
    }
    
    // Remove the node from its sequence on the List
    private detach(node: Node<V>): void {
        if (node?.prev) node.prev.next = node.next;
        if (node?.next) node.next.prev = node.prev;
        if (this.head === node) this.head = this.head?.next;
        if (this.tail === node) this.tail = this.tail?.prev;
        node.next = undefined;
        node.prev = undefined;
    }
    
    // Place the node to the List's head
    private prepend(node: Node<V>): void {
        if (!this.head) this.head = node;
        if (!this.tail) this.tail = node;
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }
    
    // Ensures that the Cache's size is not greater than the capacity
    private trimCache(): void {
        if (this.length <= this.capacity) return;
        const tail = this.tail;
        this.detach(this.tail);
        const tailKey = this.reverseLookup.get(tail);
        this.lookup.delete(key);
        this.reverseLookup.delete(tail);
        this.length--;
    }
}

PreviousComplexity or Asymptotic Behavior NextGraphs

Last updated 8 months ago