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
– WilQu, Commented Dec 2, 2016 at 15:25
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
– benjano, Commented Dec 2, 2016 at 15:31
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
– slim, Commented Dec 2, 2016 at 15:41
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, Commented Dec 2, 2016 at 15:44
@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, Commented Dec 2, 2016 at 15:59

slim · Accepted Answer · 2016-12-02 16:07:59Z

1

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.

edited Dec 2, 2016 at 16:07

answered Dec 2, 2016 at 15:32

slim

41.5k14 gold badges101 silver badges131 bronze badges

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

2 Comments

benjano Over a year ago

Hi slim, Thanks for the response. I have now added in my DLLNode code - I'm not allowed the change the structure of the code so I can only pass value into addItem. Do I just want to have another line of code in the else setting head to be the next node? Kind Regards

slim Over a year ago

I added a more OO version that should suit your needs. It's probably worth understanding how we got from the first one to the second.

Collectives™ on Stack Overflow

Doubly Linked List using tail recursion

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related