Добавить в конец дважды связанного списка

Question

Я действительно пытаюсь добавить узел в конце двойного связанного списка, добавив в голову, было легко, теперь я действительно не могу найти способ добавить к концу. Это кажется глупым, но я теряю много времени, поэтому, если кто-то может помочь, это будет оценено по достоинству. Вот моя частичная реализация на Java.

public class DoublyLinkedList implements Iterable<Node>, Iterator<Node> { 

private Node head = new Node(); 
private Node tail = head; 
private Node current; 
private Node previous; 

@Override 
public Iterator<Node> iterator() { 
    current = head; 
    previous = null; 
    return this; 
} 

public void addToHead(Node node) { 
    Node next = head.getNext(null); 
    Node previous = head.getNext(next); 
    head.setNext(previous, node); 
    node.setNext(null, head); 
    head = node; 
} 

@Override 
public boolean hasNext() { 
    return current != tail; 
} 

@Override 
public Node next() { 
    Node tmp = previous; 
    previous = current; 
    current = current.getNext(tmp); 
    return previous; 
} 

А вот Node Class

public class Node { 
Node next = null; 
Node previous = null; 


Node getNext(Node node){ 
    if(node == next){ 
     return previous; 
    } 

    if(node == previous){ 
     return next; 
    } 

    throw new IllegalStateException("something went wrong"); 
} 

void setNext(Node node, Node next){ 
    if(node == previous){ 
     previous = next; 
    } 
    else if(node == this.next){ 
     this.next = next; 
    } 
    else{ 
     throw new IllegalStateException("something went wrong"); 
    } 
} 


} 

Я надеюсь, что вы поймете код, приведенный выше, в основном я буду нуждаться в следующем:

public void addToEnd(Node node) { 
    // implementation 
} 

Answer 1

Основная идея так же, как добавление в начале списка.

Мы можем разделить его на две части:

1. добавления элемента в список
2. обновляемых голову/хвост-узел списка

В псевдокоде:

node to_insert 

//step 1 
tail.setNext(to_insert) 
to_insert.setPrevious(tail) 

//step 2 
tail = to_insert 

Answer 2

Какой интерфейс вы намерены реализовать в этом двойном списке? То, как вы реализовали getNext и setNext, не является четким способом сделать это. Если у вас только один узел, и вы пытаетесь сделать setNext с null значением для node, нет способа сообщить, если вы не посмотрите на код, в котором ваш новый узел будет в конечном итоге. Наряду с этим, я не уверен, есть ли у вас хороший способ установить предыдущий узел нового хвостового узла так, как вы его реализовали. Это очень двусмысленно.

Могу ли я рекомендую вместо того, чтобы реализовать getNext(), setNext(Node), getPrevious() и setPrevious(Node) методы в вашем Node классе? Это значительно упростит и очистит ваш код.

Вы могли бы быстро реализовать свой метод addToEnd(Node).

public void addToEnd(Node node) { 
    node.setPrevious(tail); 
    tail.setNext(node); 
    tail = node; 
} 

Если вы хотите, чтобы иметь возможность перебирать список в обоих направлениях с помощью «GetNext()» и «hasNext()», вы могли бы обеспечить прямой или обратной Iterator реализации. Есть примеры того, как создавать Iterators, плавающие вокруг. Первый ответ на этот question имеет пример обратного итератора.