java - Deque JAVA中的removeLast/addFirst方法

Question

我需要帮助来解决我的 removeLast 和 addFirst 方法。

我想不出一种方法来将元素添加到队列的头部并将头部指向该元素，因为我只能访问 head.element/head。下一步。

同样，在删除最后一个对象后，我找不到引用队列尾部的方法，因为我仅限于 queue.element 和 queue.next

如有任何帮助，我们将不胜感激!

public class DequeImpl implements Deque{

    private Node head;
    private Node tail;
    private int size;

    public DequeImpl(){
        head=null;
        tail=null;
        size=0;
    }

    //This is a toString
    public String toString(){
        String toSend = "";
        Node baladeur = head;
        while(baladeur != null) {
            toSend += " " + baladeur.element;
            baladeur = baladeur.next;
        }
        return toSend;
    }

    // renvoie true if empty
    public boolean isEmpty(){
        return size==0;
    }


    public int size(){
        return this.size;
    }

   //To complete ///////
    public void addFirst(Object element){
        Node element2 = new Node(element, head);
        if(isEmpty()){
            head=tail=element2;
        }
        else{

        }
        size++;
    }

    public void addLast(Object element){
        Node element3 = new Node(element, null);
        if(isEmpty()){
            head=tail=element3;
        }
        else{
            tail.next=element3;
            tail = tail.suivant;
        }
        size++;
    }

    public Object removeFirst() throws QueueEmptyException{
        if(isEmpty())throw new QueueEmptyException("");
        Object element4 = head.element;
        if(size==1){
            head=tail=null;
        }
        else{
            head=head.next;
        }
            size--;
        return element4;
    }

   //To complete ///////

    public Object removeLast()throws QueueEmptyException{
        if(isEmpty())throw new QueueEmptyException("");
        Object element5 = tail.element;
        if(size==1){
            head=tail=null;
        }
        else{
            tail.next=null;
        }
        return null;
    }

    public Object first()throws QueueEmptyException{
        if(isEmpty())throw new QueueEmptyException("");
        return head.element;

    }

    public Object last()throws QueueEmptyException{
        if(isEmpty())throw new QueueEmptyException("");
        return tail.element;
    }


    private class Node{
        private Object element;
        private Node next;

        private Node(Object element, Node next){
            this.element = element;
            this.next = next;
        }

    }
} 

Answer 1

重新分配head很容易:

Node newHead = ... whatever you do here
newHead.next = head;
head = newHead;

不过，我感觉到你尾部的疼痛。如果您没有来自 tail 的后向指针，您所能做的就是迭代整个列表，并且:

if (tail.equals(thisNode.next)) {
  thisNode.next = null;
  tail = thisNode;
  break;
}

更多上下文表明您可以迭代整个列表:

Node thisNode = head;
while (thisNode != null) {
  if (tail.equals(thisNode.next)) {
    thisNode.next = null;
    tail = thisNode;
    break;
  }
  thisNode = thisNode.next;
}