Linked List

In this section, we will implement naive simple ArrayList here which utilised single linked list structure.

We first define head and tail references which point to internal structure that contain val and next reference.

class SSELinkedList{
    private SSELinkedListInternal head;
    private SSELinkedListInternal tail;

    private int size;

    private class SSELinkedListInternal{
        private int val;
        private SSELinkedListInternal next;
        public SSELinkedListInternal(int val){
            this.val = val;
            this.next = null;
        }
    }

    public SSELinkedList(int val){
        SSELinkedListInternal sseLinkedListInternal = new SSELinkedListInternal(val);
        head = sseLinkedListInternal;
        tail = sseLinkedListInternal;
        size = 1;
    }
    
    public int size(){
        return size;
    }
}

It is easy to define add function compare to array implementation of ArrayList. It is actually an O(1) operation because we just add at the tail.

     public void add(int toBeAdded){
        SSELinkedListInternal sseLinkedListInternal = new SSELinkedListInternal(toBeAdded);
        tail.next = sseLinkedListInternal;
        tail = sseLinkedListInternal;
        size += 1;
    }

Next is print function which iterates through all elements starting from head which means it is O(n) operation.

     public void print(){
        SSELinkedListInternal sseLinkedListInternal = head;
        while(sseLinkedListInternal!=null){
            System.out.print(sseLinkedListInternal.val + ",");
            sseLinkedListInternal = sseLinkedListInternal.next;
        }
        System.out.println("");
    }

Next is get function which needs to iterated until the index so it is an O(n) operation.

     public int get(int idx) throws Exception {
        if (idx>= size || idx < 0){
            throw new Exception("index bigger or equal to size and idx can't be smaller than 0");
        }
        int idxIterated = 0;
        SSELinkedListInternal sseLinkedListInternalPos = head;
        while(idxIterated!=idx){
            sseLinkedListInternalPos = sseLinkedListInternalPos.next;
            idxIterated = idxIterated + 1;
        }
        return sseLinkedListInternalPos.val;
    }

The next function is add function at specified index. which is on average is O(n) but it is also depend where you insert it.

     public void add(int idx, int toBeAdded) throws Exception {
        if (idx > this.size()){
            throw new Exception("index bigger than size");
        }else {
            SSELinkedListInternal sseLinkedListInternal = new SSELinkedListInternal(toBeAdded);

            if (idx == 0){
                sseLinkedListInternal.next = head;
                head = sseLinkedListInternal;
            }else if (idx == (size)){
                tail.next = sseLinkedListInternal;
                tail = sseLinkedListInternal;
            } else{
                int idxIterated = 0;
                SSELinkedListInternal sseLinkedListInternalPos = head;
                SSELinkedListInternal sseLinkedListInternalPrev = head;
                while(idxIterated!=idx){
                    sseLinkedListInternalPrev = sseLinkedListInternalPos;
                    sseLinkedListInternalPos = sseLinkedListInternalPos.next;
                    idxIterated = idxIterated + 1;
                }
                sseLinkedListInternalPrev.next = sseLinkedListInternal;
                sseLinkedListInternal.next = sseLinkedListInternalPos;
            }
            size += 1;
        }
    }

The last function is remove at specified index function. which is on average is O(n) except if you remove the head.

     public void remove(int idx) throws Exception {
        if (idx >= this.size() || idx < 0){
            throw new Exception("index bigger or equal to size and idx can't be smaller than 0");
        }else {
            if (idx == 0){
                head = head.next;
            }else if (idx == size -1){
                int idxIterated = 0;
                SSELinkedListInternal sseLinkedListInternalPos = head;
                SSELinkedListInternal sseLinkedListInternalPrev = head;
                while(sseLinkedListInternalPos!=tail){
                    sseLinkedListInternalPrev = sseLinkedListInternalPos;
                    sseLinkedListInternalPos = sseLinkedListInternalPos.next;
                    idxIterated = idxIterated + 1;
                }
                tail = sseLinkedListInternalPrev;
                sseLinkedListInternalPrev.next = null;
            }else{
                int idxIterated = 0;
                SSELinkedListInternal sseLinkedListInternalPos = head;
                SSELinkedListInternal sseLinkedListInternalPrev = head;
                while(idxIterated!=idx){
                    sseLinkedListInternalPrev = sseLinkedListInternalPos;
                    sseLinkedListInternalPos = sseLinkedListInternalPos.next;
                    idxIterated = idxIterated + 1;
                }
                sseLinkedListInternalPrev.next = sseLinkedListInternalPos.next;
            }
            size = size - 1;
        }
    }

Note: This implementation is naive and simple, haven't been thoroughly tested, please do not use in production, it is meant for simple explanation only. And also there can be better implementation that takes less time complexity.

You can try to run the code here:
Run on jdoodle