ArrayList, LinkedList

ArrayListExample.java

public class ArrayListExample {
    public static void main(String[] args) {
        MyArrayList<Long> listOfInts = new MyArrayList<>();
        listOfInts.push(20L);
        listOfInts.push(23L);
        listOfInts.push(22L);
        listOfInts.push(24L);

        listOfInts.remove(23L);


        for (int i = 0; i < listOfInts.length(); i++) {
            System.out.println(listOfInts.get(i));
        }
    }
}

class MyArrayList<T> {
    Object[] a = new Object[5];
    int virtualSize = 0;

    int push(T newElement) {
        if (a.length == virtualSize) {
            Object[] b = new Object[virtualSize + a.length * 2];
            for (int i = 0; i < a.length; i++) {
                b[i] = a[i];
            }
            a = b;
        }

        a[virtualSize++] = newElement;
        return virtualSize;
    }

    T get(int index) {
        return (T) a[index];
    }

    int length() {
        return virtualSize;
    }

    public void remove(T el) {
        int bVirtualSize = 0;
        Object[] b = new Object[virtualSize];

        for (int i = 0; i < virtualSize; i++) {
            if (a[i] != el) {
                b[bVirtualSize++] = a[i];
            }
        }

        a = b;
        virtualSize = bVirtualSize;
    }
}

// a = [1 2 3 4 5]
// b = [1 2 4 5 null]

Complexity.txt

// ArrayList
// get element by index - O(1), Om(1)
// push element (to end) - O(1), Om(1) ~ O(n), Om(n)
// insert element (random) - O(n), Om(1) ~ O(n), Om(n)
// unshift element (to begin) - O(n), Om(1) ~ O(n), Om(n)
// remove element (random) - O(n), Om(1)
// remove element (begin) - O(n), Om(1)
// remove element (end) - O(1), Om(1)

// LinkedList
// get element by index - O(n), Om(1)
// push element (to end) - O(n), Om(1)
// insert element (random) - O(n), Om(1)
// unshift element (to begin) - O(1), Om(1)
// remove element (random) - O(n), Om(1)
// remove element (begin) - O(1), Om(1)
// remove element (end) - O(n), Om(1)

linkedlist.js

class LinkedListNode {
    next = null;
    data = null;

    constructor(d) {
        this.data = d;
    }
}

class LinkedList {
    head = null;

    push(el) {
        if (this.head === null) {
            this.head = new LinkedListNode(el);
        } else {
            let n = this.head;
            while(n.next != null) {
                n = n.next;
            }
            n.next = new LinkedListNode(el);
        }
    }

    get length() {
        let n = this.head;
        let count = 0;
        while(n != null) {
            count++;
            n = n.next;
        }

        return count;
    }

    unshift(el) {
        const newHead = new LinkedListNode(el);
        newHead.next = this.head;
        this.head = newHead;
    }

    get(idx) {
        let n = this.head;
        for (let i = 0; i < idx; i++) {
            n = n.next;
        }
        return n.data;
    }

    shift() {
        this.head = this.head.next;
    }

    forEach(fn) {
        let n = this.head;
        let c = 0;
        while(n != null) {
            fn(n.data, c);
            n = n.next;
            c++;
        }
    }
}

const ll = new LinkedList()
ll.push(5);
ll.push(10);
ll.unshift(1);

ll.forEach((d, i) => console.log(i, d))