Question

Create a Java code that includes all the methods from the Lecture slides following the ADTs

LECTURE SLIDE

Collect/finish the Java code (interface and the complete working classes) from lecture slides for the following ADTS 2) ArrayList ADT that uses a linked list internally (call it LArrayList) Make sure you keep the same method names as in the slides (automatic testing will be performed)! For each method you develop, add comments and estimate the big-O running time of its algorithm. In the comments additionally explain the advantages of the array-based implementation over the linked- list-based implementation and vice versa. Keep your code nicely formatted and follow good programming practices. Try to make the code robust and try to use generics. The Array List ADT /**Simplified version of java.util. List */ public interface List { /**Returns the number of elements in this list */ public int size(); /**Returns whether the list is empty. */ public boolean isEmpty() /** Inserts an element e to be at index I, shifting all elements after this. */ public void add(int I, E e) throws IndexOutOfBoundsException; /** Returns the element at index I, without removing it. */ public E get(int i) throws IndexOutOfBoundsException; /** Removes and returns the element at index I, shifting the elements after this. */ public E remove(int i) throws IndexOutOfBounds Exception; /**Replaces the element at index I with e, returning the previous element at i. */ public E set(int I, E e) throws IndexOutOfBoundsException; }

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// LArrayList.java

public class LArrayList<E> implements List<E> {

      // pointer to head node

      private Node head;

      // current size of list

      private int size;

      // constructor initializes empty list

      public LArrayList() {

            head = null;

            size = 0;

      }

      // returns the size, works in O(1) time

      public int size() {

            return size;

      }

      // returns true if list is empty, works in O(1) time

      public boolean isEmpty() {

            return size == 0;

      }

      // adds an element to particular index, worst case running complexity is

      // O(n)

      public void add(int i, E e) throws IndexOutOfBoundsException {

            // validating index

            if (i < 0 || i > size) {

                  throw new IndexOutOfBoundsException();

            }

            // creating a node

            Node node = new Node(e);

            // adding before head if i is 0

            if (i == 0) {

                  node.next = head;

                  // updating head

                  head = node;

                  size++;

                  return;

            }

            Node temp = head;

            // finding node at i-1 position

            for (int index = 0; index < i - 1; index++) {

                  temp = temp.next;

            }

            // adding node between temp and temp.next

            node.next = temp.next;

            temp.next = node;

            size++; // updating size

      }

      // returns the data at index i, works in O(n) time (worst case)

      public E get(int i) throws IndexOutOfBoundsException {

            // validating index

            if (i < 0 || i >= size) {

                  throw new IndexOutOfBoundsException();

            }

            Node temp = head;

            // finding node at index i

            for (int index = 0; index < i; index++) {

                  temp = temp.next;

            }

            return temp.data;

      }

      // removes an element from a particular index, worst case running complexity

      // is O(n)

      public E remove(int i) throws IndexOutOfBoundsException {

            //validating index

            if (i < 0 || i >= size) {

                  throw new IndexOutOfBoundsException();

            }

            //updating head node if i is 0

            if (i == 0) {

                  //storing current data of head node

                  E data = head.data;

                  head = head.next;

                  size--;

                  //returning removed data

                  return data;

            }

            Node temp = head;

            //finding node at i-1 position

            for (int index = 0; index < i - 1; index++) {

                  temp = temp.next;

            }

            //removing node at temp.next position

            E data = temp.next.data;

            temp.next = temp.next.next;

            size--;

            return data;

      }

      // updates an element at particular index, returns the old value, works in

      // O(n) time (worst case)

      public E set(int i, E e) throws IndexOutOfBoundsException {

            if (i < 0 || i >= size) {

                  throw new IndexOutOfBoundsException();

            }

            Node temp = head;

            for (int index = 0; index < i; index++) {

                  temp = temp.next;

            }

            //storing old value

            E old = temp.data;

            //replacing with new value

            temp.data = e;

            //returning old value

            return old;

      }

      // private class to represent one node

      private class Node {

            E data;

            Node next;

            public Node(E data) {

                  this.data = data;

            }

      }

}