Insert new element in Double Linked List

Question

I have to implement double linked lists. The method prepend should insert a new element bevor the existing list. But I dont know how to link the reference "next" of the new element with the reference "prev" of the old list. Thanks in advance.

public class DoublyLinkedList {

private String info;
private DoublyLinkedList next;
private DoublyLinkedList prev;

public DoublyLinkedList(String info) {
    this.info = info;
    this.next = this.prev = null;
}

private DoublyLinkedList(String info, DoublyLinkedList prev, DoublyLinkedList next) {
    this.info = info;
    this.prev = prev;
    this.next = next;
}

DoublyLinkedList prepend(String info) {
    // Beginning of a list, insert new element
    if (prev == null) {
        prev = new DoublyLinkedList(info, null, next);
    } else {
        prev.prepend(info);
    }
    return prev;
}

Answer 1

Start by naming your class DoublyLinkedNode. A linked series of such objects would make a doubly linked list.

It's really important for your thinking to use the right class names. Once you fix your nsme ie node not list, the problem should becone a lot easier.

In pseudo code:

• set previous of root to new node
• set new node next to root
• set root to new node

Answer 2

You need to link the new node with the current node by setting the next_link of the new node with the current node.

public class DoublyLinkedList {
    ...
    DoublyLinkedList prepend(String info) {
        // Beginning of a list, insert new element
        if (prev == null) {
            // this is the changed line.
            prev = new DoublyLinkedList(info, null, this);
        } else {
            prev.prepend(info);
        }
        return prev;
    }
}