Question

Write in Java! (Not Javascript)

Consider the LinkedList class we discussed in class (see the slides for lecture 8). Add the following methods to the class and submit the completed LinkedList class.

• int size() which returns the size of the linked list
• Link getElementByIndex(int index) which returns the Link/node specified by the index. For example, getElementByIndex(0) should return the first Link, getElementByIndex(2) should return the third Link. If index is not in range, your method should return null.
• boolean hasDuplicate() which returns true if the linked list contains duplicate data, returns false if there is no duplicate data in the list.
• Link reverse() which reverses the linked list and returns the new head/first of the linked list (which is of type Link)

your file to be submitted to Gradescope should be named LinkedList.java. and here is the skeleton:

class Link

{

    public int data; // assuming integer data

    public Link next; // reference to the next Link

    //--------------------------------------------------------------

    // Constructor

    public Link(int data)

    {

        this.data = data;

        next = null;

    }

}

public class LinkedList

{

// implement this class

}

Answer 1

Sol: Here is the java code

class Link
{
    public int data; // assuming integer data
    public Link next; // reference to the next Link
    //--------------------------------------------------------------
    // Constructor
    public Link(int data)
    {
        this.data = data;
        next = null;
    }
}
public class LinkedList
{
    Link head;
// implement this class
    public int size() 
    { 
        Link temp = head; 
        int count = 0; 
        while (temp != null) 
        { 
            count++; 
            temp = temp.next; 
        } 
        return count; 
    } 
    public int getElementByIndex(int index) 
    { 
        Link current = head; 
        int count = 0; /* index of Node we are 
                          currently looking at */
        while (current != null) 
        { 
            if (count == index) 
                return current.data; 
            count++; 
            current = current.next; 
        } 
  
        /* if we get to this line, the caller was asking 
        for a non-existent element so we assert fail */
        assert(false); 
        return 0; 
    } 
    public boolean hasDuplicate() {
    int currentIndex = 0;
    for (Link current = head; current != null; current = current.next) {
        //with each node in list, compare it to all element of list
        int nodeIndex = 0;
        for (Link node = head; node != null; node = node. next) {
            if (currentIndex != nodeIndex && node.equals(current)) {
                return true;
            }
            nodeIndex++;
        }
        currentIndex++;
    }
    return false;
    }
    Link reverse() 
    { 
        Link prev = null; 
        Link current = head; 
        Link next = null; 
        while (current != null) { 
            next = current.next; 
            current.next = prev; 
            prev = current; 
            current = next; 
        } 
        node = prev; 
        return node; 
    }
}