Question

I need this written in Java, it is a Linked List and each of it's Methods. I am having trouble and would appreciate code written to specifications and shown how to check if each method is working with an example of one method being checked. Thank you.

public interface Sequence <T> {

    /**
     * Inserts the given element at the specified index position within the sequence. The element currently at that
     * index position (and all subsequent elements) are shifted to the right.
     *
     * @param index the index at which the given element is to be inserted
     * @param x     the element to insert
     * @return {@code true} if and only if adding the element changed the sequence
     * @throws IndexOutOfBoundsException if the index is invalid {@code (index < 0 || index > size())}
     * @throws NullPointerException      if the given element is {@code null}
     */
    boolean add(int index, T x) throws IndexOutOfBoundsException, NullPointerException;

    /**
     * Adds the specified element to the end of the sequence.
     *
     * @param x the element to add
     * @return {@code true} if and only if adding the element changed the sequence
     * @throws NullPointerException if the given element is {@code null}
     */
    boolean add(T x) throws NullPointerException;

    /**
     * Removes all of the elements from the sequence.
     */
    void clear();

    /**
     * Check if the given element belongs to the sequence.
     *
     * @param x the element to check for
     * @return {@code true} if and only if the sequence contains the given element
     * @throws NullPointerException if the given element is {@code null}
     */
    boolean contains(T x) throws NullPointerException;

    /**
     * Returns the element at the given position in the sequence.
     *
     * @param index the index of the element to return
     * @return the element at the given position in the sequence
     * @throws IndexOutOfBoundsException if the index is invalid {@code (index < 0 || index >= size())}
     */
    T get(int index) throws IndexOutOfBoundsException;

    /**
     * Returns the index position of the first occurrence of the given element within the sequence or -1 if it does not
     * belong.
     *
     * @param x the element to search for
     * @return the index position of the first occurrence of the given element within the sequence or -1 if it does not
     * belong
     * @throws NullPointerException if the given element is {@code null}
     */
    int indexOf(T x) throws NullPointerException;

    /**
     * Check if the sequence is empty.
     *
     * @return {@code true} if and only if the sequence is empty.
     */
    boolean isEmpty();

    /**
     * Removes the element at the given position in the sequence.
     *
     * @param index the index position of the element to be removed
     * @return the element at the given position in the sequence
     * @throws IndexOutOfBoundsException if the index is invalid {@code (index < 0 || index >= size())}
     */
    T remove(int index) throws IndexOutOfBoundsException;

    /**
     * Remove the first occurrence of the given element from the sequence (if present).
     *
     * @param x the element to be removed from this list
     * @return {@code true} if and only if removing the element changed the sequence
     * @throws NullPointerException if the given element is {@code null}
     */
    boolean remove(T x) throws NullPointerException;

    /**
     * Replaces the element at the given position of the sequence with the specified element.
     *
     * @param index index of the element to replace
     * @param x     the new element
     * @throws IndexOutOfBoundsException if the index is invalid {@code (index < 0 || index >= size())}
     * @throws NullPointerException      if the given element is {@code null}
     */
    void set(int index, T x) throws IndexOutOfBoundsException, NullPointerException;

    /**
     * Returns the number of elements in this sequence.
     *
     * @return the number of elements in this sequence
     */
    int size();

    /**
     * Returns an array containing all of the elements in this sequence (preserving their order).
     *
     * @return an array containing all of the elements in this sequence (preserving their order)
     */
    Object[] toArray();
}

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

Note: Two files are attached- SequenceList.java and Test.java, Test.java contains basic testing of most methods in SequenceList to make sure that everything is working correctly.

// SequenceList.java

public class SequenceList<T> implements Sequence<T> {

      // pointers to head and tail of the sequence

      private Node<T> head;

      private Node<T> tail;

      // current size

      private int size;

     

      //constructor initializes empty list

      public SequenceList() {

            head = null;

            tail = null;

            size = 0;

      }

      @Override

      public boolean add(int index, T x) throws IndexOutOfBoundsException,

                  NullPointerException {

            //validating x

            if (x == null) {

                  throw new NullPointerException();

            }

            // validating index

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

                  // invalid

                  throw new IndexOutOfBoundsException("Invalid index");

            }

            // adding to front if index is 0, adding to last if index = size

            if (index == 0) {

                  Node<T> newNode = new Node<T>(x);

                  newNode.setNext(head);

                  head = newNode;

                  size++;

                  return true;

            } else if (index == size) {

                  // adding to end

                  return add(x);

            } else {

                  Node<T> temp = head;

                  // finding node at index-1

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

                        temp = temp.getNext();

                  }

                  // adding node between temp and temp.getNext()

                  Node<T> node = new Node<T>(x);

                  node.setNext(temp.getNext());

                  temp.setNext(node);

                  // updating size

                  size++;

                  return true;

            }

      }

      @Override

      public boolean add(T x) throws NullPointerException {

            //validating x

            if (x == null) {

                  throw new NullPointerException();

            }

            Node<T> node = new Node<T>(x);

            if (head == null) {

                  // first node

                  head = node;

                  tail = node;

            } else {

                  // appending to the tail

                  tail.setNext(node);

                  tail = node;

            }

            // updating size

            size++;

            return true;

      }

      @Override

      public void clear() {

            head = null;

            tail = null;

            size = 0;

      }

      @Override

      public boolean contains(T x) throws NullPointerException {

            //validating x

            if (x == null) {

                  throw new NullPointerException();

            }

            Node<T> p = head;

            //looping through the sequence until x is found or end is reached

            while (p != null && !p.getData().equals(x)) {

                  p = p.getNext();

            }

            if (p != null) {

                  // found

                  return true;

            }

            // not found

            return false;

      }

      @Override

      public T get(int index) throws IndexOutOfBoundsException {

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

                  throw new IndexOutOfBoundsException("Invalid index!");

            }

            Node<T> temp = head;

            // finding node at index

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

                  temp = temp.getNext();

            }

            // returning value of node at index

            return temp.getData();

      }

      @Override

      public int indexOf(T x) throws NullPointerException {

            //validating x

            if (x == null) {

                  throw new NullPointerException();

            }

            int index = 0;

            //looping through the sequence

            for (Node<T> temp = head; temp != null; temp = temp.getNext()) {

                  if (temp.getData().equals(x)) {

                        // found, returning index

                        return index;

                  }

                  index++;

            }

            return -1; // not found

      }

      @Override

      public boolean isEmpty() {

            return size == 0;

      }

      @Override

      public T remove(int index) throws IndexOutOfBoundsException {

            // validating index

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

                  throw new IndexOutOfBoundsException("Invalid index");

            }

            if (index == 0) {

                  //removing head node and returning removed element

                  T item = head.getData();

                  head = head.getNext();

                  if (head == null) {

                        tail = null;

                  }

                  size--;

                  return item;

            } else {

                  Node<T> temp = head;

                  // finding node at index-1 position

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

                        temp = temp.getNext();

                  }

                  T item = temp.getNext().getData();

                  // removing node between temp and temp.next.next

                  temp.setNext(temp.getNext().getNext());

                  // updating tail node if we just deleted the tail node

                  if (index == size - 1) {

                        if (temp.getNext() == null) {

                              tail = temp;

                        } else {

                              tail = temp.getNext();

                        }

                  }

                  size--;

                  return item;

            }

      }

      @Override

      public boolean remove(T x) throws NullPointerException {

            //validating x

            if (x == null) {

                  throw new NullPointerException();

            }

            if (head == null) {

                  // empty list

                  return false;

            }

            if (head.getData().equals(x)) {

                  // removing head

                  head = head.getNext();

                  if (head == null) {

                        // updating tail if list became empty

                        tail = null;

                  }

                  size--;

                  return true;

            }

            Node<T> node = head;

            Node<T> next = head.getNext();

            // finding node to be deleted, if exists

            while (next != null) {

                  if (next.getData().equals(x)) {

                        // found, updating next

                        node.setNext(next.getNext());

                        if (node.getNext() == null) {

                              // updating tail

                              tail = node;

                        }

                        size--;

                        return true; // success

                  }

                  // moving to next pair of nodes

                  node = node.getNext();

                  next = next.getNext();

            }

            return false; // not found

      }

      @Override

      public void set(int index, T x) throws IndexOutOfBoundsException,

                  NullPointerException {

            // validating x

            if (x == null) {

                  throw new NullPointerException();

            }

            // validating index

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

                  throw new IndexOutOfBoundsException("Invalid index");

            }

            Node<T> temp = head;

            // finding node at index

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

                  temp = temp.getNext();

            }

            // updating data

            temp.setData(x);

      }

      @Override

      public int size() {

            return size;

      }

      @Override

      public Object[] toArray() {

            //creating an array of size capacity

            Object[] arr = new Object[size];

            int index = 0;

            //looping through the sequence and adding all elements to the array

            for (Node<T> temp = head; temp != null; temp = temp.getNext()) {

                  arr[index] = temp.getData();

                  index++;

            }

            return arr;

      }

     

      @Override

      public String toString() {

            // returning a string containing list elements comma separated inside

            // square braces

            String data = "[";

            Node<T> p = head;

            while (p != null) {

                  data += p.getData();

                  p = p.getNext();

                  if (p != null) {

                        data += ", ";

                  }

            }

            data += "]";

            return data;

      }

}

// class to represent each node in the linked list

class Node<T> {

      private T data;

      private Node<T> next;

      // constructor taking value for the data

      public Node(T data) {

            this.data = data;

            next = null;

      }

      // getters and setters

      public Node<T> getNext() {

            return next;

      }

      public void setNext(Node<T> next) {

            this.next = next;

      }

      public T getData() {

            return data;

      }

      public void setData(T data) {

            this.data = data;

      }

}

// Test.java

public class Test {

      public static void main(String[] args) {

            //creating an integer sequence list

            SequenceList<Integer> intSequenceList = new SequenceList<Integer>();

            //adding numbers from 1 to 10

            for (int i = 1; i <= 10; i++) {

                  intSequenceList.add(i);

            }

            //performing various tests on the sequence

            System.out.println(intSequenceList);

            intSequenceList.add(0, 100);

            System.out.println(intSequenceList);

            intSequenceList.add(5, 500);

            System.out.println(intSequenceList);

            System.out.println("Contains 500: " + intSequenceList.contains(500));

            System.out.println("Contains 501: " + intSequenceList.contains(501));

            System.out.println("get(5): " + intSequenceList.get(5));

            intSequenceList.set(5, 999);

            System.out.println("set(5,999)");

            System.out.println(intSequenceList);

            System.out.println("Size: " + intSequenceList.size());

            System.out.println("Index of 1000: " + intSequenceList.indexOf(1000));

            System.out.println("Index of 10: " + intSequenceList.indexOf(10));

            // removing element at index 0

            intSequenceList.remove(0);

            System.out.println("after removing element at index 0");

            System.out.println(intSequenceList);

            // removing element 999. note the difference, if we want to remove an

            // element, we pass an Integer object, not int.

            intSequenceList.remove((Integer) 999);

            System.out.println("after removing element 999");

            System.out.println(intSequenceList);

            intSequenceList.clear();

            System.out.println("after clearing");

            System.out.println(intSequenceList);

      }

}

/*OUTPUT*/

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

[100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

[100, 1, 2, 3, 4, 500, 5, 6, 7, 8, 9, 10]

Contains 500: true

Contains 501: false

get(5): 500

set(5,999)

[100, 1, 2, 3, 4, 999, 5, 6, 7, 8, 9, 10]

Size: 12

Index of 1000: -1

Index of 10: 11

after removing element at index 0

[1, 2, 3, 4, 999, 5, 6, 7, 8, 9, 10]

after removing element 999

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

after clearing

[]