Doubly Linked List using tail recursion

Question

I am working on trying to make my doubly linked list use tail recursion.

public class DoublyLinkedList
{
    private int noOfItems;
    private DLLNode head;
    private DLLNode tail;
  // Default constructor
  public DoublyLinkedList()
  {
     head = null;
     tail = null;
     this.noOfItems = 0;

  }

public void AddItem(String value)
{
   DLLNode newNode = new DLLNode(value);

   if (head == null)
   {
       head = newNode;
       noOfItems++;
   }
   else {
       DLLNode current = head;

       while(current != null) {
           if (current.GetNextNode() == null) {
               current.setNextNode(newNode);

               newNode.setPrevious(newNode);
               noOfItems++;
               break;
           }
           current = current.GetNextNode();

           }
       }

   }
}

My Node class is as follows:

public class DLLNode
{
    private DLLNode previous;
    public DLLNode next;
    private String value;

    public DLLNode(String value)
    {
        this.value = value;
    }
  /* This method returns the String item of data held in this node */
  public String GetDataItem()
  {
    return value;
  }

  public void setDataItem()
  {
      this.value = value;
  }

  /* This method returns the node immediately prior to this node in the list or
   * null if there is no such node */
  public DLLNode GetPreviousNode()
  {
    return previous;
  }

  public void setPrevious(DLLNode previous)
  {
      this.previous = previous;
  }

  /* This method returns the node immediately after this node in the list or null
   * if there is no such node. */
  public DLLNode GetNextNode()
  {
    return next;
  }

  public void setNextNode(DLLNode next)
  {
      this.next = next;
  }

   public void AddItem(String value)
    {
       if (next == null)
       {
           next = new DLLNode(value);
       }
       else
           next.AddItem(value);
    }



}

This is the code I have for my Add Item. I have also attempted to make this use tail recursion which is the code shown below:

 public void AddItem(String value)
  {
       if (head == null)
       {
           head = new DLLNode(value);
           noOfItems++;
       }
       else {

          head.AddItem(value);
       }

 }

The recursive version I have written works. However it isn't doubly linked.

I understand that for it to be a doubly linked list a node needs to know what comes next and what has come before it. So in my Add Item do I need something to let the next node know what has come before it? If so any advice on how to do this?

Thanks in Advance.

Please post the whole code. It’s hard to answer without knowing what head refers to. — WilQu
Hi, I have now added the majority of my code - if anything else is required please let me know. But I think everything relating to my add item has been posted. — benjano
The Java convention is for method calls to start with a lower case letter, and class names to start with uppercase. So addItem() and DLLNode Sounds picky, but we get confused if we see a method that looks like a class or a constructor! — slim
Hi Slim, the skeleton of this code was given to me and I'm not allowed to change it due to the way the piece of work is marked. If I change any of the skeleton I will get 0 marks even if it functions fully. — benjano
@benjano Then "innocently" ask your teacher why they're not following common Java style conventions... You can always make the code presentable for questions on SO, then change it back to your teacher's style before submitting. — slim

slim slim · Accepted Answer · 2016-12-02T15:32:58

Using hypothetical Node class of my own -- you can adapt this to your DLLNode:

void addItem(Node head, Node item) {
     if(node.next == null) {
          // Stopping condition
          node.next = item;
          item.previous = node;
     } else {
          // Recurse
          addItem(node.next, item);
     }
}

Alternatively, a bit more OO, assuming this code is part of Node, just replace head with this, and you need fewer method parameters:

void addItem(Node item) {
     if(this.next == null) {
          // Stopping condition
          this.next = item;
          item.previous = this;
     } else {
          // Recurse
          this.next.addItem(item);
     }
}

Or if you don't want to be passed a Node, instead creating one:

public void addItem(String value) {
     if(this.next == null) {
          // Stopping condition
          Node newNode = new Node(value, this, null);
          this.next = newNode;
     } else {
          // Recurse
          this.next.addItem(value);
     }
}

This assumes a constructor:

public Node(String value, Node previous, Node next) {
     this.value = value;
     this.previous = previous;
     this.next = next;
}

I think this shows the basics neatly. You can improve it by using getters/setters, etc.

I've given you methods for a Node, but you have a DoublyLinkedList class that wraps around it. It's quite common for a list class to be quite a thin wrapper around methods on the nodes:

 public class DoublyLinkedList {
       private Node head;

       public addItem(String value) {
            head.addItem(value);
       }
 }

(You will need to deal with the situation where head is null, too. I've left that out for brevity)

Note that in Java, this recursive solution isn't ideal, since the language doesn't optimise tail recursion, and for a long list you'll get a stack overflow. The iterative solution doesn't consume stack.

Doubly Linked List using tail recursion

1 Answers