Question

Implement the addSecond method in IntSinglyLinkedList. This method takes an Integer as an argument and adds it as the second element in the list.

Here is an example of adding the Integer 7 to a list with two elements.

Abstract view: addSecond(7) on the list [12, 100] turns the list into [12, 7, 100]

Implement the rotateLeft method in IntSinglyLinkedList. It moves all elements closer to the front of the list by one space, moving the front element to be the last.

For example, here is what it looks like to rotateLeft once.

Abstract view: rotateLeft() on the list [12, 7, 100] turns the list into [7, 100, 12]

IntSinglyLinkedListTest.java

package net.datastructures;

import org.junit.Test;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.*;

public class IntSinglyLinkedListTest {

    @Test
    public void addSecondTest1() {
        IntSinglyLinkedList s = new IntSinglyLinkedList();
        s.addFirst(12);
        s.addSecond(7);
        // System.out.println(s);
        assertEquals(2, s.size());
        assertEquals(7, (int)s.last());
        assertEquals(12, (int)s.first());
    }

    @Test
    public void addSecondTest2() {
        IntSinglyLinkedList s = new IntSinglyLinkedList();
        s.addFirst(12);
        s.addFirst(7);
        s.addSecond(6);
        assertEquals(3, s.size());
        assertEquals(12, (int)s.last());
        assertEquals(7, (int)s.first());
    }

    @Test
    public void addSecondTest3() {
        IntSinglyLinkedList s = new IntSinglyLinkedList();
        s.addFirst(12);
        s.addSecond(7);
        s.addSecond(6);
        s.addSecond(1);
        assertEquals(4, s.size());
        assertEquals(7, (int)s.last());
        assertEquals(12, (int)s.first());
        assertEquals(12, (int)s.removeFirst());
        assertEquals(1, (int)s.first());
        assertEquals(1, (int)s.removeFirst());
        assertEquals(6, (int)s.first());
    }

    @Test
    public void rotateLeft1() {
        IntSinglyLinkedList s = new IntSinglyLinkedList();
        s.addFirst(7);
        s.addFirst(6);
        s.addFirst(5);
        s.addFirst(4);
        s.addFirst(3);
        s.rotateLeft();
        assertEquals(4, (int)s.first());
        assertEquals(3, (int)s.last());
        s.rotateLeft();
        assertEquals(5, (int)s.first());
        assertEquals(4, (int)s.last());
        s.rotateLeft();
        assertEquals(6, (int)s.first());
        assertEquals(5, (int)s.last());
        s.rotateLeft();
        assertEquals(7, (int)s.first());
        assertEquals(6, (int)s.last());
        s.rotateLeft();
        assertEquals(3, (int)s.first());
        assertEquals(7, (int)s.last());
    }
}

IntSinglyLinkedList.java

/*
 * Copyright 2014, Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
 *
 * Developed for use with the book:
 *
 *    Data Structures and Algorithms in Java, Sixth Edition
 *    Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
 *    John Wiley & Sons, 2014
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package net.datastructures;

/**
 * A basic singly linked list implementation.
 *
 * @author Michael T. Goodrich
 * @author Roberto Tamassia
 * @author Michael H. Goldwasser
 */

/* CS2230
This version of IntSinglyLinkedList replaces the generic type Integer
with Integer. It may be easier to read if generic types
are hurting your brain.
*/

public class IntSinglyLinkedList {
    //---------------- nested Node class ----------------
    /**
     * Node of a singly linked list, which stores a reference to its
     * element and to the subsequent node in the list (or null if this
     * is the last node).
     */
    private static class Node {

        /** The element stored at this node */
        private Integer element;            // reference to the element stored at this node

        /** A reference to the subsequent node in the list */
        private Node next;         // reference to the subsequent node in the list

        /**
         * Creates a node with the given element and next node.
         *
         * @param e  the element to be stored
         * @param n  reference to a node that should follow the new node
         */
        public Node(Integer e, Node n) {
            element = e;
            next = n;
        }

        // Accessor methods
        /**
         * Returns the element stored at the node.
         * @return the element stored at the node
         */
        public Integer getElement() { return element; }

        /**
         * Returns the node that follows this one (or null if no such node).
         * @return the following node
         */
        public Node getNext() { return next; }

        // Modifier methods
        /**
         * Sets the node's next reference to point to Node n.
         * @param n    the node that should follow this one
         */
        public void setNext(Node n) { next = n; }
    } //----------- end of nested Node class -----------

    // instance variables of the IntSinglyLinkedList
    /** The head node of the list */
    private Node head = null;               // head node of the list (or null if empty)

    /** The last node of the list */
    private Node tail = null;               // last node of the list (or null if empty)

    /** Number of nodes in the list */
    private int size = 0;                      // number of nodes in the list

    /** Constructs an initially empty list. */
    public IntSinglyLinkedList() { }              // constructs an initially empty list

    // access methods
    /**
     * Returns the number of elements in the linked list.
     * @return number of elements in the linked list
     */
    public int size() { return size; }

    /**
     * Tests whether the linked list is empty.
     * @return true if the linked list is empty, false otherwise
     */
    public boolean isEmpty() { return size == 0; }

    /**
     * Returns (but does not remove) the first element of the list
     * @return element at the front of the list (or null if empty)
     */
    public Integer first() {             // returns (but does not remove) the first element
        if (isEmpty()) return null;
        return head.getElement();
    }

    /**
     * Returns (but does not remove) the last element of the list.
     * @return element at the end of the list (or null if empty)
     */
    public Integer last() {              // returns (but does not remove) the last element
        if (isEmpty()) return null;
        return tail.getElement();
    }

    // update methods
    /**
     * Adds an element to the front of the list.
     * @param e  the new element to add
     */
    public void addFirst(Integer e) {                // adds element e to the front of the list
        head = new Node(e, head);              // create and link a new node
        if (size == 0)
            tail = head;                           // special case: new node becomes tail also
        size++;
    }

    /**
     * Adds an element to the end of the list.
     * @param e  the new element to add
     */
    public void addLast(Integer e) {                 // adds element e to the end of the list
        Node newest = new Node(e, null);    // node will eventually be the tail
        if (isEmpty())
            head = newest;                         // special case: previously empty list
        else
            tail.setNext(newest);                  // new node after existing tail
        tail = newest;                           // new node becomes the tail
        size++;
    }

    /**
     * Removes and returns the first element of the list.
     * @return the removed element (or null if empty)
     */
    public Integer removeFirst() {                   // removes and returns the first element
        if (isEmpty()) return null;              // nothing to remove
        Integer answer = head.getElement();
        head = head.getNext();                   // will become null if list had only one node
        size--;
        if (size == 0)
            tail = null;                           // special case as list is now empty
        return answer;
    }

    @SuppressWarnings({"unchecked"})
    public boolean equals(Object o) {
        if (o == null) return false;
        if (getClass() != o.getClass()) return false;
        IntSinglyLinkedList other = (IntSinglyLinkedList) o;   // use nonparameterized type
        if (size != other.size) return false;
        Node walkA = head;                               // traverse the primary list
        Node walkB = other.head;                         // traverse the secondary list
        while (walkA != null) {
            if (!walkA.getElement().equals(walkB.getElement())) return false; //mismatch
            walkA = walkA.getNext();
            walkB = walkB.getNext();
        }
        return true;   // if we reach this, everything matched successfully
    }

    public void rotateLeft() {

    }

    public void addSecond(Integer e) {

    }

    /**
     * Produces a string representation of the contents of the list.
     * This exists for debugging purposes only.
     */
    public String toString() {
        StringBuilder sb = new StringBuilder("(");
        Node walk = head;
        while (walk != null) {
            sb.append(walk.getElement());
            if (walk != tail)
                sb.append(", ");
            walk = walk.getNext();
        }
        sb.append(")");
        return sb.toString();
    }

    public static void main(String[] args) {
        IntSinglyLinkedList sl = new IntSinglyLinkedList();
        sl.addLast(100);
        sl.addLast(200);
        sl.addLast(300);
        System.out.println(sl.toString());
        System.out.println("Removed " + sl.removeFirst());
        System.out.println(sl.toString());
    }
}

Answer 1

Screenshot of the code added:

The output of the test's running successfully:

The Code of the two functions added:

public void rotateLeft() {
    if(!isEmpty()){  //checking if the list is not empty.
        Node temp = head.getNext();    //store the 2nd node of the list in temp, which eventually becomes the head.
        head.setNext(null);  //setting the head's next to null, this is because head is about to become the last node.
        tail.setNext(head);  //now tails will start pointing to the head.
        head = temp;  //head will start pointing to the 2nd node.
        tail = tail.getNext();  //tail will start pointing to the last node.
    }
}

public void addSecond(Integer e) {
    Node newest = new Node(e, null);
    if(!isEmpty()){  //check if the list is not empty.
        newest.setNext(head.getNext());  //setting the newest node as the second node.
        head.setNext(newest);  //getting the head node to point to the newest node.
        //if the size is 1 therefore after the addition of the second node the size will be 2, one node will be the head
        //and the other will be the tail node.
        if(size==1)
        {
            tail = newest;
        }
        this.size++; //increasing the size by one.
    }
}

I hope you like the solution. In case of any doubts regarding the solution feel free to ask it in the comment section. If you like the solution please give a thumbs up.