Question

based on the code below, answer the questions

Question 1: The LinkedList class uses another class called Node (which is defined inside LinkedList.java). What are the fields in the Node class?

Question 2: The Node class uses generics. Why?

Question 3: The linkFirst method contains the following lines of code: if (f == null) last = newNode; else f.prev = newNode; What is the value of the linked list’s size attribute at this point in the code if f == null is true?

Question 4: True or False: the removeLast method will take longer to execute the more items are in the linked list.

Question 5: True or False: the public void add(E e)method always adds the new item at the beginning of the linked list. Question 6: True or False: the public void add(E e) method will take longer to execute the more items are in the linked list.

Question 7: The unlink method contains the following lines of code: if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } If the method is called with the first Node in the list as the parameter value, which of these will be executed: the if clause or the else clause?

Question 8: True or false: in general, the contains method takes longer to execute the more items there are in the linked list.

***linkedlistclass ****-question1and 2

public class LinkedList<E>

    extends AbstractSequentialList<E>

    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

{

    transient int size = 0;

    /**

     * Pointer to first node.

     * Invariant: (first == null && last == null) ||

     *            (first.prev == null && first.item != null)

     */

    transient Node<E> first;

    /**

     * Pointer to last node.

     * Invariant: (first == null && last == null) ||

     *            (last.next == null && last.item != null)

     */

    transient Node<E> last;

    /**

     * Constructs an empty list.

     */

    public LinkedList() {

    }

    /**

     * Constructs a list containing the elements of the specified

     * collection, in the order they are returned by the collection's

     * iterator.

     *

     * @param c the collection whose elements are to be placed into this list

     * @throws NullPointerException if the specified collection is null

     */

    public LinkedList(Collection<? extends E> c) {

        this();

        addAll(c);

    }

**********end of code for question 1*************8

**linkFirst method*** (question 3)

private void linkFirst(E e) {

        final Node<E> f = first;

        final Node<E> newNode = new Node<>(null, e, f);

        first = newNode;

        if (f == null)

            last = newNode;

        else

            f.prev = newNode;

        size++;

        modCount++;

    }
****end of linkFirst method************

**removeLast method****(question 4)

public E removeLast() {

       final Node<E> l = last;

        if (l == null)

            throw new NoSuchElementException();

        return unlinkLast(l);

    }

end of remove last method***********

****public void add (E e) method ****(question 5 and 6)

public void add(E e) {

            checkForComodification();

            lastReturned = null;

            if (next == null)

                linkLast(e);

            else

                linkBefore(e, next);

            nextIndex++;

            expectedModCount++;

        }

****end of public add method****

****unlink method**** question 7

/**

     * Unlinks non-null node x.

     */

    E unlink(Node<E> x) {

        // assert x != null;

        final E element = x.item;

        final Node<E> next = x.next;

        final Node<E> prev = x.prev;

        if (prev == null) {

            first = next;

        } else {

            prev.next = next;

            x.prev = null;

        }

        if (next == null) {

            last = prev;

        } else {

            next.prev = prev;

            x.next = null;

        }

        x.item = null;

        size--;

        modCount++;

        return element;

    }

***end of unlink methood*****

***contains method*******question 8

/**

     * Returns {@code true} if this list cs the specified element.

     * More formally, returns {@code true} if and only if this list contains

     * at least one element {@code e} such that

     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.

     * @param o element whose presence in this list is to be tested

     * @return {@code true} if this list contains the specified element

     */

    public boolean contains(Object o) {

        return indexOf(o) != -1;

    }

Answer 1

Here are the solutions for the first 4 problems:

Question 1: The LinkedList class uses another class called Node (which is defined inside
           LinkedList.java). What are the fields in the Node class?
Answer 1: The fields in the Node class include:
               -> item of type E.
               -> next of type Node, which points to the next node.
               -> prev of type Node, which points to the previous node.  
                      
Question 2: The Node class uses generics. Why?
Answer 2:   Generics are used for the Node class, to specify that the node items can be
           of any data type.
          
Question 3: The linkFirst method contains the following lines of code: if (f == null)
           last = newNode; else f.prev = newNode; What is the value of the linked list’s
           size attribute at this point in the code if f == null is true?
Answer 3:   f = null will happen, when the first node pointer itself is pointing to null.
           i.e., there are no nodes in the list. Therefore, the size attribute will be 0.
                      
Question 4: True or False: the removeLast method will take longer to execute the more
           items are in the linked list.
Answer 4:   False. As there is a first, and last pointer, where first points to first node,
           and last points to last node. And the other point is that, every node has a
           next pointer as well as the previous pointer, so, to remove the last node, you
           have to traverse atmost one node, starting from last pointer.