Insert first node into empty doubly linked list [how]

Question

This is a continuation of the previous message. Now I will look at how to insert the first node into an empty double-linked list. This seems to be hard to do first ... I would be grateful for a hint about what is missing in my addFirst method.

... 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]

The solution proposed by typo.pl:

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

Answer 1

You have only updated the node information.

Now you need to update the DLL information about what are the first / last nodes in the list. And it is very easy to update when you add one node to an empty list. There is only one choice for the first node and one choice for the last node.

Answer 2

you can do something like that

 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; } 

you can also use sentinel nodes

Answer 3

In fact, you can improve this by pretending to use a circular list:

 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; } } 

Notice how push works even when the list is empty: this.next is the same as this and this.next.prev is the same as this.prev.