вставка первого узла в пустой двусвязный список [как сделать]

Question

Это продолжение предыдущего поста . Сейчас я смотрю, как вставить первый узел в пустой список с двумя связями. Поначалу это кажется сложным, кажется ... я был бы благодарен за подсказку о том, что отсутствует в моем методе addFirst

...
public DLL()
{
    first = null ;
    last = null ;
}

...
DLL myList = new DLL() ;
DLLNode A = new DLLNode("Hello", null, null) ;
...

myList.addFirst(A) ;

...
public void addFirst(DLLNode v)
{
    v.pred = first ;
    v.succ = last ; 
}

[EDIT]

Решение, предложенное typo.pl:

public void addFirst(DLLNode v)
{
    v.pred = first ;
    v.succ = last ;
    first = v ;
    last = v ;
}

Answer 1

Вы только обновили информацию об узле.

Теперь вам нужно обновить информацию DLL относительно того, какие первые / последние узлы в списке. И это действительно легко обновить, когда вы добавляете один узел в пустой список. Есть только один выбор для первого узла и один выбор для последнего узла.

Answer 2

На самом деле вы можете улучшить это, притворившись, что используете циклически связанный список:

public class DLLNode {
    Object contents;
    DLLNode next, prev;
}

public class DLL extends DLLNode {
    public DLL() {
        // next and prev are the first and last entry
        // but they are set to this to indicate an empty list
        next = prev = this;
    }
    public void push(DLLNode v) {
        v.next = this;
        v.prev = this.next;
        this.next.prev = v;
        this.next = v;
    }
    public void shift(DLLNode v) {
        v.prev = this;
        v.next = this.prev;
        this.prev.next = v;
        this.prev = v;
    }
    public DLLNode pop() {
        return this.remove(this.next);
    }
    public DLLNode unshift() {
        return this.remove(this.prev);
    }
    public DLLNode remove(DLLNode v) {
        if (v == this) throw new IllegalArgumentException();
        v.next.prev = v.prev;
        v.prev.next = v.next;
        v.next = null;
        v.prev = null;
        return v;
    }
}

Обратите внимание, как работает push, даже если список пуст: this.next такой же, как этот, иthis.next.prev совпадает с this.prev.

Answer 3

Вы можете сделать что-то подобное

public void addFirst(DLLNode v){

    v.pred = null ; //v will be first node so its pred. is null
    v.succ = first; //v successor is the old first node

    if (first != null)
        first.pred = v; //the first pred. is the new node

    first  = v;     //v is now the first node in the linked list

    //if that was the first node to add , update the last pointer                    
    if (last == null)
       last = v;
}

Вы также можете использовать Узлы Стража