Double Linked List

Question

//I have a single linked list that looks like this

node head = new Node ();
head.info = 3;
head.next = new Node ();
head.next.info = 6 ();
head.next.next = new Node ();
head.next.next.info = 9;
head.next.next.next = null;

//How would I write a double linked list?

class Double Node
{
    info;
    doubleNode prev;
    doubleNode next;
}

Answer 1

Here is the part for creating a double linked list and adding nodes to it. You can update it by adding remove and insert functions as you want.

class Node{
    Node prev;
    Node next;
    int value;

    public Node(int value) {
        this.value = value;
    }
}

class DoubleLinkedList{
    Node head;
    Node tail;

    public DoubleLinkedList(Node head) {
        this.head = head;
        this.tail = head;
        head.next = null;
        head.prev = null;
    }

    public void addNode(Node node){
        tail.next = node;
        node.prev = tail;
        tail = node;
    }
}

public class Main {
    public static void main(String args[]){
        Node head= new Node(3);
        DoubleLinkedList list = new DoubleLinkedList(head);
        list.addNode(new Node(5));
        list.addNode(new Node(6));
        list.addNode(new Node(7));
        list.addNode(new Node(8));
    }
 }

Answer 2

This would be the idea:

node head = new Node();
head.info = 3;
node prev, actual, next;
prev = head;
actual.prev = prev;
actual.info = 6;
actual = actual.next = new Node();
actual.prev = prev;
actual = actual.next = new Node();
actual.info = 9;
...

Assuming that you will have the behavior in your example, you can automate it with a function, in c# would be something like:

function GetDoubleLinkedList(Node head, int from, int end, int jumps)
{
   head.info = from;
   node prev = head, actual, next;
   for(var i = from+jumps; i <= end; i+=jumps)
   {
      actual.prev = prev;
      actual.info = i;
      actual = actual.next = new Node();
   }
   actual.info = end;
   return head;
}

//...
//then you can do
node head = new Node();
head = GetDoubleLinkedList(head, 3, 9, 3);
//...

Answer 3

Double linked list are like single linked list with the exception that they have two pointer in the declaration of structure

a previous pointer and a next pointer

For sample implementation see this link

Answer 4

Here is an implementation of a DoubleLinkedList in Java (along with some examples that might help you understand how it's working):

public class Node {
    public int value;
    public Node prev;
    public Node next;

    public Node(int value) {
        this.value = value;
        this.prev = null;
    }

    public Node(int value, Node prev) {
        this.value = value;
        this.prev = prev;
    }

    public Node add(int value) {
        if(this.next == null) {
            this.next = new Node(value, this);
        } else {
            this.next.add(value);
        }
        return this;
    }

    public Node last() {
        if(this.next == null) {
            return this;
        } else {
            return this.next.last();
        }
    }

    public String toString() {
        String out = value+" ";
        if(this.next != null) {
            out += this.next.toString();
        }
        return out;
    }

    public static void main(String...arg) {
        Node list = (new Node(3)).add(6).add(5).add(9);

        System.out.println(list.toString());
        //Output:3 6 5 9 
        System.out.println(list.last().toString());
        //Output:9 
        System.out.println(list.last().prev.prev.toString());
        //Output:6 5 9 
    }
}

Answer 5

You can use following DoubleLinkedList class.

public class DoubleLinkedList<T>
{
    Node<T> start;
    Node<T> end;

    public void AddFirst(T dataToAdd)
    {
        Node<T> tmp = new Node<T>(dataToAdd);
        if (start == null)
        {
            start = tmp;
            end = start;
            return;
        }
        start.previous = tmp;
        tmp.next = start;
        start = tmp;


        if (start.next == null)
        {
            end = start;
        }
    }

    public void AddLast(T dataToAdd)
    {
        if (start == null)
        {
            AddFirst(dataToAdd);
            return;
        }
        Node<T> tmp = new Node<T>(dataToAdd);
        end.next = tmp;
        tmp.previous = end;
        end = tmp;
    }

    public T RemoveFirst()
    {
        if (start == null) return default(T);

        T saveVal = start.data;
        start = start.next;
        start.previous = null;
        if (start == null) end = null;

        return saveVal;
    }

    public T RemoveLast()
    {
        if (start == null) return default(T);

        T saveVal = end.data;
        end = end.previous;
        end.next = null;
        if (start == null) end = null;

        return saveVal;
    }


    public void PrintAll()
    {
        Node<T> tmp = start;
        while (tmp != null)
        {
            Console.WriteLine(tmp.data.ToString());
            tmp = tmp.next;
        }
    }
}

And Use the following Node class

class Node<T>
{
    public T data;
    public Node<T> next;
    public Node<T> previous;

    public Node(T newData)
    {
        data = newData;
        next = null;
        previous = null;

    }
}