Java doubly linked list pointers to previous nodes

Question

I'm making a method to add a Node into a list called "public void add(int index, T value)".

This method will put a value into an index, and then will have pointers to the next and previous elements in the list. I have messed up on the pointers to the previous nodes, which I have been sitting and experimenting but don't get to make it work.

Example: We have a list with Integer values [2, 4, 6] Instance variables: Node head, tail; int amount, changes;

Instance variables for the inner class are: T value; Node prev, next;

Input:

add(1, 3);
System.out.println(list.toString());
System.out.println(list.backwardsString());

Expected output:

[2, 3, 4, 6]
[6, 4, 3, 2]

My code so far:

public void add(int index, T value) {
if (index < 0 || index > amount) {
        throw new IndexOutOfBoundsException("Index is not between 0 and amount!");
    }

    if (value== null) {
        throw new NullPointerException("Value can't be null!");
    }

    if (amount == 0) {
        head = tail= new Node<>(value, null, null);
    }
    else if (index == 0) {
        head = head.prev= new Node<>(value, null, head);
    }
    else if (index == amount) {
        tail = tail.next= new Node<>(value, tail, null);
    } 
    else {
        Node<T> p = head;  
        for (int i = 1; i < index; i++) {
            p = p.next;
        }
        p.next= new Node<>(value, p, p.next);


        p = tail;
        for (int i = amount; i > index; i--) {
            p.prev= new Node<>(value, p.prev, p);
            p = p.prev;
        }*/
    }

    amount++;
    changes++;
}

In this occasion I would also ask how does

p.prev.next or p.next.prev

work?

Oncaphillis Oncaphillis · Accepted Answer · 2014-10-18T15:45:56

You may heavily simplify your design by introducing an empty pseudo node into your List class.

Since this node always exists you don't need a special case like:

if (amount == 0) {
    head = tail= new Node<>(value, null, null);
}
else if (index == 0) {
    head = head.prev= new Node<>(value, null, head);
}

The first node pseudo can be initialized with

pseudo.next = pseudo;
pseudo.prev = pseudo;

The List is empty if

pseudo.next == pseudo.prev

The real List start will be pseudo.next and the last list entry will be pseudo.prev. So your List will be actually a ring.

Your search loop will become

   Node<T> p = pseudo.next;  
   for (int i = 0; i < index && p!=pseudo; i++) {
        p = p.next;
   }

However here:

   p.next= new Node<>(value, p, p.next);

You have to manipulate p.next.prev which also points (or better refers) to an illegal Node<> now.

But I leave that as a homework -- which this clearly seems to be ;-)

EDIT:

Full List implementation demonstrating the sentinel Node

public class List {

public class  Node {
    T value = null;
    Node(T v) {
        value=v;
    }
    Node()   {
    }
    public Node getNext() {
        return next;
    }

    public Node getPrev () {
        return prev;
    }
    public T getValue() {
        return value;
    }

    Node prev = null;
    Node next = null;
};

private Node pseudo = new Node();

List() {
    pseudo.next = pseudo.prev = pseudo;
}

public Node getBegin() {
    return pseudo.next;
}

public Node getEnd() {
    return pseudo;
}

public boolean add(int index, T value) {
    Node p = pseudo.next;

    for (int i = 0; i < index && p!=pseudo; i++) {
        p = p.next;
    }

    // Correct for tail insertion
    if(p == getEnd())
        p = p.prev;

    Node ptm = p.next;

    p.next      = new Node(value);
    p.next.next = ptm;
    p.next.prev = p;
    ptm.prev    = p.next;

    return true;
}

public void delete(int i) {

    Node p = pseudo.next;

    for (int ix = 0; ix < i && p!=pseudo; ix++) {
        p = p.next;
    }

    if(p != getEnd()) {
        Node ptm = p.prev;
        p.prev.next = p.next;
        p.next.prev = ptm;
    }       
}

}

Java doubly linked list pointers to previous nodes

1 Answers