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 · Accepted Answer · 2014-10-20 20:24:52Z

0

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

}

edited Oct 20, 2014 at 20:24

answered Oct 18, 2014 at 15:45

Oncaphillis

1,91813 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Toeffen Over a year ago

This is some difficult subject, hard to grasp entirely how this work.

Oncaphillis Over a year ago

@Toeffen You have a lot of code just checking for (1) and empty List (2) If your supposed to insert at head or (3) tail. This can all be circumvented by using an sentinel node see en.wikipedia.org/wiki/Sentinel_node . Insertion of node n1 after n0 (with a tmp node nt) then simply becomes {nt = n0.next;n0.next=n1;n1.prev=n0;n1.next=nt;nt.prev=n1;} Removal of n1 becomes n1.prev.next = n1.next; n1.next.prev = ne.prev;

Toeffen Over a year ago

Index can be anything between also, not just the head or tail. This code does the inserting and adding the pointers to the next nodes fine, but the previous nodes doesn't connect.

Oncaphillis Over a year ago

@Toeffen I've added an implementation if List<T> to demonstrate usage of sentinel node. What I've missed was the special handling of tail insertion where the current node has to be p.prev and not p.

Collectives™ on Stack Overflow

Java doubly linked list pointers to previous nodes

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related