Question

The aim of this lab session is to make you familiar with implementing a linked list. In this lab you will complete the partially implemented LinkedIntegerList.

Specifically, you will implement the following methods.

• public boolean remove(int value)

• public int removeAt(int index)

• public boolean set(int index, int value)

• public int indexOf(int value)

Task-1

Add a new class named Lab3Tester class to test the current implementation of the linked list. (Note: you may reuse the code from SimpleIntegerListTester class.)

Make sure your code compiles and executes without any errors.

Task 2: Implement the remove Method

1. Implement the remove method in the LinkedIntegerList class. Make sure your code is commented and properly indented.

2. Test the new implementation using Lab3Tester class.

3. Commit code changes.

Task 3: Implement the removeAt Method

1. Implement the removeAt method in the LinkedIntegerList class. Make sure your code is commented and properly indented.

2. Test the new implementation using Lab3Tester class.

3. Commit code changes.

LInkedintegrelist :

public class LinkedIntegerList implements SimpleIntegerListADT {

   //Instance variables
   private IntegerNode head;
   private int itemCount;

   /**
   * Default constructor.
   */
   public LinkedIntegerList() {
       super();
       this.head = null;
       this.itemCount = 0;
   }

   @Override
   public boolean add(int value) {
       IntegerNode newNode = new IntegerNode(value);
       if(null == this.head) { //Adding to empty list
           this.head = newNode; //Set new node as head
           this.itemCount = 1; //Set item count to 1
           return true;
       }
       else {
           //Find the last node.
           IntegerNode currNode = this.head;
           //Last node does not have a next node (null). Therefore, update the currNode to current nodes' next while it is not null.
           while(null != currNode.getNext())
               currNode = currNode.getNext();
           //Set next of last node to new node.
           currNode.setNext(newNode);
           //Increment item count
           this.itemCount++;
           return true;
       }
   }

   @Override
   public boolean add(int index, int value) throws IndexOutOfBoundsException {
       //Check the validity of index.
       if(index < 0 || index > itemCount)
           throw new IndexOutOfBoundsException("The specified index (" + index + ") is not not valid. Index should be between 0 and " + this.itemCount);
       else if(0 == index){ //Add new value as the first (head) element
           IntegerNode newNode = new IntegerNode(value);
           //Update the next node of new node as the current head node
           newNode.setNext(this.head);
           //Update the head to point to this node
           this.head = newNode;
           //Increment item count
           this.itemCount++;
           return true;
       }
       else {
           IntegerNode newNode = new IntegerNode(value);
           //Find the node at location index-1
           IntegerNode currNode = this.head;
           for(int i=1; i<index; i++) //Note here i goes from 1 to index-1
               currNode = currNode.getNext();
           //Update the new node to point to the next node of the current node.
           newNode.setNext(currNode.getNext());
           //Update the current node to point to the new node.
           currNode.setNext(newNode);
           //Increment item count
           this.itemCount++;
           return true;
       }
   }

   @Override
   public boolean remove(int value) {
       //TODO: Implement this method
       /***********Dummy Implementation***********/
       return false;
   }

   @Override
   public int removeAt(int index) throws IndexOutOfBoundsException {
       //Check the validity of index.
       if( index < 0 || index >= this.itemCount)
           throw new IndexOutOfBoundsException("The specified index (" + index + ") is not present in the list. Number of items present in the list is " + this.itemCount);
       //TODO: Complete this method.
       /***********Dummy Implementation***********/
       return 0;
   }

   @Override
   public int get(int index) throws IndexOutOfBoundsException {
       //Check the validity of index.
       if( index < 0 || index >= this.itemCount)
           throw new IndexOutOfBoundsException("The specified index (" + index + ") is not present in the list. Number of items present in the list is " + this.itemCount);
       //Get the Node at the index.
       IntegerNode currNode = this.head;
       for(int i=0; i<index; i++) //Note here i goes from 0 to index-1
           currNode = currNode.getNext();
       //return the value of the node.
       return currNode.getValue();
   }

   @Override
   public boolean set(int index, int value) throws IndexOutOfBoundsException {
       //TODO: Implement this method
       /***********Dummy Implementation***********/
       return false;
   }

   @Override
   public int indexOf(int value) {
       //TODO: Implement this method
       /***********Dummy Implementation***********/
       return -1;
   }

   @Override
   public boolean contains(int value) {
       //Search using the indexOf method.
       if(this.indexOf(value) >= 0)
           return true;
       //Item not found.
       return false;
   }

   @Override
   public int size() {
       return this.itemCount;
   }

   @Override
   public void clear() {
       this.head = null;
       this.itemCount = 0;
   }

   @Override
   public String toString() {
       if(null == this.head || 0 == this.itemCount)
           return "List is empty!";
       String retVal = "List Items (Count: " + this.itemCount + "): ";
       IntegerNode currNode = this.head;
       while(null != currNode) {
           retVal += currNode.getValue() + ", ";
           currNode = currNode.getNext();
       }
       return retVal.substring(0, retVal.length()-2);
   }
}
r

import java.util.Scanner;

public class SimpleIntegerListTester {

   public static void main(String[] args) {
       SimpleIntegerListADT myList = null;
       System.out.println("Select the implementation type.\n\t1 for ArrayBasedIntegerList.\n\t2 for GrowingArrayBasedIntegerList.\n\t3 for LinkedIntegerList.");
       Scanner myScanner = new Scanner(System.in);
       int option = myScanner.nextInt();
       myScanner.close();
       switch(option) {
       case 3:
           myList = new LinkedIntegerList();
           break;
       case 2:
           myList = new GrowingArrayBasedIntegerList();
           break;
       case 1:
       default:
           myList = new ArrayBasedIntegerList();
       }
      
       System.out.println(myList);
       for(int i=2; i<8; i+=2)
           myList.add(i);
       System.out.println(myList);
       myList.add(1, 10);
       System.out.println(myList);
       myList.add(66);
       System.out.println(myList);
       myList.add(44);
       System.out.println(myList);
      
       myList.remove(66);
       System.out.println(myList);
       myList.remove(4);
       System.out.println(myList);
       myList.remove(2);
       System.out.println(myList);
      
       myList.add(0, 44);
       System.out.println(myList);
      
       myList.add(3, 22);
       System.out.println(myList);
      
       myList.add(4, 33);
       System.out.println(myList);
      
       myList.add(5, 55);
       System.out.println(myList);
      
       myList.add(2, 55);
       System.out.println(myList);
      
       System.out.println(myList.contains(44));
       System.out.println(myList.indexOf(44));
       System.out.println(myList.contains(10));
       System.out.println(myList.indexOf(10));
       System.out.println(myList.contains(33));
       System.out.println(myList.indexOf(33));
       System.out.println(myList.contains(11));
       System.out.println(myList.indexOf(11));
      
   }

}

Answer 1

public class LinkedIntegerList implements SimpleIntegerListADT {

    //Instance variables
    private IntegerNode head;
    private int itemCount;
 
    /**
    * Default constructor.
    */
    public LinkedIntegerList() {
        super();
        this.head = null;
        this.itemCount = 0;
    }
 
    @Override
    public boolean add(int value) {
        IntegerNode newNode = new IntegerNode(value);
        if(null == this.head) { //Adding to empty list
            this.head = newNode; //Set new node as head
            this.itemCount = 1; //Set item count to 1
            return true;
        }
        else {
            //Find the last node.
            IntegerNode currNode = this.head;
            //Last node does not have a next node (null). Therefore, update the currNode to current nodes' next while it is not null.
            while(null != currNode.getNext())
                currNode = currNode.getNext();
            //Set next of last node to new node.
            currNode.setNext(newNode);
            //Increment item count
            this.itemCount++;
            return true;
        }
    }
 
    @Override
    public boolean add(int index, int value) throws IndexOutOfBoundsException {
        //Check the validity of index.
        if(index < 0 || index > itemCount)
            throw new IndexOutOfBoundsException("The specified index (" + index + ") is not not valid. Index should be between 0 and " + this.itemCount);
        else if(0 == index){ //Add new value as the first (head) element
            IntegerNode newNode = new IntegerNode(value);
            //Update the next node of new node as the current head node
            newNode.setNext(this.head);
            //Update the head to point to this node
            this.head = newNode;
            //Increment item count
            this.itemCount++;
            return true;
        }
        else {
            IntegerNode newNode = new IntegerNode(value);
            //Find the node at location index-1
            IntegerNode currNode = this.head;
            for(int i=1; i<index; i++) //Note here i goes from 1 to index-1
                currNode = currNode.getNext();
            //Update the new node to point to the next node of the current node.
            newNode.setNext(currNode.getNext());
            //Update the current node to point to the new node.
            currNode.setNext(newNode);
            //Increment item count
            this.itemCount++;
            return true;
        }
    }
 
    @Override
    public boolean remove(int value) {
        
        IntegerNode current = this.head;

        if(current.getValue() == value){
            head = current.getNext();
            this.itemCount--;
            return true;
        }

        while(current.getNext()!=null){
            IntegerNode next = current.getNext();
            if(next.getValue() == value){
                current.setNext(next.getNext());
                this.itemCount--;
                return true;
            }
            current = current.getNext();
        }
        return false;
    }
 
    @Override
    public int removeAt(int index) throws IndexOutOfBoundsException {
        //Check the validity of index.
        if( index < 0 || index >= this.itemCount)
            throw new IndexOutOfBoundsException("The specified index (" + index + ") is not present in the list. Number of items present in the list is " + this.itemCount);
        
        if(index == 0){
            IntegerNode toRemove = head;
            head = head.getNext();
            this.itemCount--;
            return toRemove.getValue();
        }
        IntegerNode curr = this.head;
            for(int i=0;i<index-1;i++){
                curr = curr.getNext();
        }
        IntegerNode toRemove = curr.getNext();
        curr.setNext(toRemove.getNext());
        this.itemCount--;
        return toRemove.getValue();
        
    }
 
    @Override
    public int get(int index) throws IndexOutOfBoundsException {
        //Check the validity of index.
        if( index < 0 || index >= this.itemCount)
            throw new IndexOutOfBoundsException("The specified index (" + index + ") is not present in the list. Number of items present in the list is " + this.itemCount);
        //Get the Node at the index.
        IntegerNode currNode = this.head;
        for(int i=0; i<index; i++) //Note here i goes from 0 to index-1
            currNode = currNode.getNext();
        //return the value of the node.
        return currNode.getValue();
    }
 
    @Override
    public boolean set(int index, int value) throws IndexOutOfBoundsException {
       //Check the validity of index.
        if( index < 0 || index >= this.itemCount)
            throw new IndexOutOfBoundsException("The specified index (" + index + ") is not present in the list. Number of items present in the list is " + this.itemCount);
           
        
        IntegerNode curr = head;
        for(int i=0;i<index;i++){
            curr = curr.getNext();
        }
        curr.setValue(value);
        return true;
    }
 
    @Override
    public int indexOf(int value) {
       
        IntegerNode curr = head;
        int index = 0;
        while(curr != null){
            if(curr.getValue() == value){
                return index;
            }
            curr = curr.getNext();
            index++;
        }
        return -1;
    }
 
    @Override
    public boolean contains(int value) {
        //Search using the indexOf method.
        if(this.indexOf(value) >= 0)
            return true;
        //Item not found.
        return false;
    }
 
    @Override
    public int size() {
        return this.itemCount;
    }
 
    @Override
    public void clear() {
        this.head = null;
        this.itemCount = 0;
    }
 
    @Override
    public String toString() {
        if(null == this.head || 0 == this.itemCount)
            return "List is empty!";
        String retVal = "List Items (Count: " + this.itemCount + "): ";
        IntegerNode currNode = this.head;
        while(null != currNode) {
            retVal += currNode.getValue() + ", ";
            currNode = currNode.getNext();
        }
        return retVal.substring(0, retVal.length()-2);
    }
 }

The completed LinkedIntegerList class is given above. The code has been run against the tester code given and runs fine. I will be glad to resolve any queries in the comments.

Please consider dropping an upvote to help a struggling college student :)

Happy Coding !!