CODEWITHSUNDEEP
java
user1111880
user1111880

Reputation: 483

convert below singly Linked list to doubly linked list

I already wrote a small program of single linked list with add and traverse method in that. Now I want to convert it into a doubly linked list. I know all the concept of doubly linked list but I am facing little difficulty to implement it in my program.

public class SingleLinkList<T> {

private Node<T> head;
private Node<T> tail;




public void add(T element)
{
    Node<T> nd = new Node<T>();
    nd.setValue(element);

    if (head==null)
    {
        head = nd;
        tail = nd;
    }
    else
    {
        tail.setNextRef(nd);
        tail = nd;
    }
}

public void traverse(){

    Node<T> tmp = head;
    while(true){
        if(tmp == null){
            break;
        }
        System.out.println(tmp.getValue());
        tmp = tmp.getNextRef();
    }
}

public static void main (String args[])
{
    SingleLinkList<Integer> s1 = new SingleLinkList<Integer>();
    s1.add(2);
    s1.add(3);
    s1.add(3);

    s1.traverse();
}

}


class Node<T> {

private T value;
private Node<T> nextRef;
public T getValue() {
    return value;
}
public void setValue(T value) {
    this.value = value;
}
public Node<T> getNextRef() {
    return nextRef;
}
public void setNextRef(Node<T> nextRef) {
    this.nextRef = nextRef;
}

public int compareTo(T arg)
{
    if (arg==this.value)
    {
        return 0;}
        else
            {return 1;}
    }
}

Upvotes: 0

Views: 90

Answers (2)

Tim Biegeleisen
Tim Biegeleisen

Reputation: 521168

Add a Node<T> prevRef field to your list class with appropriate getters and setters and then add this method:

public void linkReverse(Node<T> head) {
    if (head == null) {
        return;
    }
    head.setPrevRef(null);
    if (head.getNextRef() == null) {
        return;
    }

    Node<T> prev = head;
    Node<T> curr = head.getNextRef();

    while (curr != null) {
        curr.setPrevRef(prev);
        prev = curr;
        curr = curr.getNextRef();
    }
}

This method will walk down a currently singly linked list and will link each node in reverse, leaving the list doubly linked.

Of course, you would need to modify the other methods as well, but this is at least a good starting point.

Upvotes: 1

Sharon Ben Asher
Sharon Ben Asher

Reputation: 14328

just add private Node<T> prevRef; instance variable to Node class, and set it during add() method. I suggest that traverse() will receive a boolean (or even better, enum) direction argument

Upvotes: 0

Related Questions