I need help with the two empty methods in the code below. You need to loop though head to tail before returning removefirstoccurance(Object o) or removeLastoccurance(Object o) ??

Question

public class LinkedListDeque<E> extends AbstractDeque<E> {

private Deque<Integer>list;

private Node<E> head;

private Node<E> tail;

private int size;

@Override

public boolean offerFirst(E e) {

Node<E> temp = new Node<>(e);

if(isEmpty()) {

tail = head = temp;

}else {

head.prev=temp;

temp.next=head;

head=temp;

}

size++;

return true;

}

@Override

public boolean offerLast(E e) {

Node<E> temp = new Node<>(e);

if (isEmpty()) {

tail = head = temp;

}else {

temp.prev=tail;

tail.next=temp;

tail=temp;

}

size++;

return true;

}

@Override

public E pollFirst() {

Node<E>temp;

if (isEmpty()) {

return null;

}

temp = head;

head = head.next;

if(head!=null) {

head.prev = null;

}else {

tail = null;

}

size--;

return temp.value;

}

@Override

public E pollLast() {

Node<E>temp;

if (isEmpty()) {

return null;

}

temp = tail;

tail = tail.prev;

if(tail != null) {

tail.next=null;

}else {

head=null;

}

size--;

return temp.value;

}

@Override

public E peekFirst() {

Node<E>temp;

if (isEmpty()) {

return null;

}

if(head !=null) {

temp=head;

}else {

temp=tail;

}

return temp.value;

}

@Override

public E peekLast() {

Node<E>temp;

if (isEmpty()) {

return null;

}

if(tail != null) {

temp=tail;

}else {

temp=head;

}

return temp.value;

}

public boolean removeFirstOccurrence(Object o) {

}

public boolean removeLastOccurrence(Object o) {

}

@Override

public boolean contains(Object o) {

while(head != null) {

if(head.value.equals(o)) {

return true;

}

}

return false;

}

@Override

public int size() {

return size;

}

@Override

public boolean isEmpty() {

return size == 0;

}

@Override

public void clear() {

head = null;

tail = null;

size = 0;

}

private boolean remove(Node<E> n) {

if(isEmpty()) {

return false;

}

if(head.equals(n)) {

head = head.next;

return true;

}

return false;

}

public class Node<R>{

private R value;

private Node<R> next;

private Node<R> prev;

private Node(R value) {

this(value,null,null);

}

private Node(Node<R> next,Node<R> prev) {

this(null,next,prev);

}

private Node(R value,Node<R> next, Node<R> prev) {

this.value = value;

this.next = next;

this.prev = prev;

}

public String toString() {

return null;

}

}

}

Answer 1

I took a look at the code and can see a few issues with some of the methods already filled out but it mainly has to do with the looping that you are confused about which is good news because we can complete the two empty methods while learning how to fix the others in the future.

(background)

The first thing to note (you may already know this) is that a deque in java stands for double ended queue. A good way to picture this is like a deck of cards. You can take a card from the top or bottom very easily but grabbing a card from the middle isn't as easily achievable. The head node can be seen as the top card in this deck and the tail node can be seen as the bottom.

(what we know so far)

lets start by looking at removefirstoccurence. Our overall goal is to remove the first node that contains a value equal to the Object o. For any node, assuming your pre-written code in the "contains" method works, we already know how to check if a node's value equals o:

if(currentNode.value.equals(o)) {

return true;

}

(steps to implement removefirstoccurence)

We can split our main goal in to two separate sub goals. 1 is to loop through each node in our deque (to check if its value equals o), and 2 is to remove that node from the deque while making sure our deque still functions properly.

(looping through the nodes)

To loop through the nodes from the beginning we start at the head node.

Node<E>temp = head;

We use a temporary node reference because it is going to need to change to refer to each node in our deque. Now we need to actually go through and look at each node by repeatedly getting the "next" node until the node we are looking at has a value equal to o:

while(!temp.value.equals(o)) {

temp = temp.next

}

(removing the node)

Removing the node can be simple but with a few catches. For any node somewhere in the middle of our deque, we can link the previous node with the next node, leaving our current node unlinked from the other nodes in the deque. To do this we can set the previous node's "next" value to the current nodes reference to the next node, then the next node's "prev" value to the previous node. If the node is the tail or the head you will need to remove it the way you already have been.

(removeLastOccurrence)

As for removeLastOccurrence we can do the same thing but starting from the tail and moving to previous nodes.

Hope this helps!