Things We discussed

The main problem with array is that its size if fixed which only works when we know in advance how large our array will get. In most real world scenarios we don't really know in advance how large our array will get so we need a structure or mechanism through which we can create a list that automatically scales its size as we add elements.

There are 2 kinds of lists

1. ArrayList - It uses arrays underneath to store elements, and scales the array as and when needed, the advantage with this kind of list is that access is O(1) both for inserts and reads. The only case the above statement doesn't hold true is when the array becomes full in that scenario we need to create a bigger array then copy over all elements into it which is a O(N) process.
2. LinkedList - if we don't want to pay the above O(N) penality and we don't mind O(N) reads we can use a linkedlist. A linked list is just a connection of nodes each of which point to the next one, so all we have to do when we add a new element is to add new node to the last element. we will discuss this in detail in a later class.

Typically any List will need to provide the following methods as a basic functionality for it to be useable

1. add(element) - allows to add new elements to the end of the list
2. get(index)->element - gets the element at a specified location
3. set(index, element) - replaces the element at the specified index
4. remove(index) - removes the element at a specified index

We implemented a class that just does this called SimpleArrayList.java

package com.example.generics.arraylist;

import java.util.Arrays;

public class SimpleArrayList{
    /* Simple implementation of Java's ArrayList
     * Standard Java Methods
     * get :: Get Element at an index
     * put :: replace element at an index
     * add :: add/append new element at the end of the list
     * remove :: remove element at an index
     * size :: get the size of the list
    * */
    public int[] elements; // array to hold elements
    public int end; // track the next insertion point in the array

    public SimpleArrayList(){
        // [0,0,0,0]
        elements = new int[5];
    }

    public int get(int index){
        //get :: Get Element at an index
        if(index>=end) return -1;
        return elements[index];
    }

    public void put(int index, int value){
        //put :: replace element at an index
        if(index>=end) return; // throw exception
        elements[index]=value;
    }

    public void add(int value){
        // add :: add/append new element at the end of the list
        if(end>=elements.length) scaleArray(); // if capacity exceeds then scale/double up the array
        elements[end]=value;
        ++end; // increment end to point to next insertion point
    }

    public void remove(int index){
        // remove :: remove element at an index

        // if removal is after the end of the array then we don't have to do anything
        if(end>=elements.length) return;
        // remove the element and move the next elements back
        for(int i=index;i+1<end;++i) elements[i]=elements[i+1];
        --end; // move pointer back to replace the element as list size just shrank
    }

     void scaleArray(){
        // Scale up the array when capacity if the array exceeds original capacity
        int newElements[] = new int[elements.length*2]; // double the array

        // write elements to new array
        for(int i=0;i<elements.length;++i) newElements[i]=elements[i];
        elements = newElements;
    }

    public int size(){
        // size :: get the size of the list
        return end;
    }

    @Override
    public String toString(){
        // Created to make printing possible
        return Arrays.toString(elements);
    }
}

Things i got wrong / Mis understood

Sorry ! I Don't remember, please raise it if you do

Things We missed

Sorry ! I Don't remember, please raise it if you do