Week2

Question 1

Which of the following nodes is unnecessary when inserting a new node at a specified index of a standard LinkedList, given the implementation we saw in this module? Select all that apply

• Tail
• Node at index
• Node before the index
• Node after index

Answer 1

all except node before the index

knowing the node at or after the index is not useful because we cannot backtrack further to update the next field of the node before the index, to point to the newly created node.

Tail - Since we cannot traverse the singly-LinkedList in the opposite direction (from tail to head), we have no way to insert a node at a given index because we would have no links to follow to reach that index of the list nor to update the neighboring nodes.

Question 2

removeFirst Algo in LL

Answer 2

public void removeFirst() {
    if (head != null) {
        head = head.next;
    }
    if (head == null) {
        tail = null;
    }
}

public void removeFirst() {
    if (head == tail) {
        head = null;
        tail = null;
    } else {
        head = head.next;
    }
}

Question 3

The implementations of a Stack and Queue based on a LinkedList structure are very similar. Which of the following statements about the corresponding functions is true? Select all that apply.

Stack.peek() and Queue.peek() both return the element at the head of the underlying LinkedList.

Stack.pop() and Queue.remove() are implemented using the same underlying LinkedList functions where the node at the head of the LinkedList is removed, and its value returned.

Stack.push(E element) and Queue.add(E element) insert a new node at opposite ends of the underlying LinkedList.

Stack.push(E element) and Queue.add(E element) are implemented using the same underlying LinkedList functions where a new node is added at the tail of the LinkedList.

Answer 3

Stack.peek() and Queue.peek() both return the element at the head of the underlying LinkedList.

Stack.pop() and Queue.remove() are implemented using the same underlying LinkedList functions where the node at the head of the LinkedList is removed, and its value returned.

Stack.push(E element) and Queue.add(E element) insert a new node at opposite ends of the underlying LinkedList.

Question 4

LL implementation of Stack Code

Answer 4

import java.util.LinkedList;

public class Stack {
    protected LinkedList list = new LinkedList();

public void push(E value) {
    list.addFirst(value);
}

    public E pop() {
        if (list.isEmpty())
            return null; 
        return list.removeFirst();    
    }
}