Delete Item - Doubly Linked list using Tail Recursion

Question

I am currently learning Doubly Linked Lists.

I have managed to convert write a doubly linked list that was nearly 100% functional. However I need to learn how to write it with tail recursion.

Below is my DLLNode code:

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

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

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

    public String GetDataItem()
    {
        return value;
    }

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


    public DLLNode GetPreviousNode()
    {
        return previous;
    }

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


    public DLLNode GetNextNode()
    {
        return next;
    }

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

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

}

I have managed to get my AddItem working using tail recursion and I'm now looking into getting delete Item working. I'm guessing that like addItem I need deleteItem adding to my DLLNode.

Below is my DoublyLinkedList class:

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 DeleteItem(int index)
    {
        if (index ==0)
        {
            System.out.println("Out of Bounds");
        }
        if (index > noOfItems)
        {
            System.out.println("Out of Bounds");
        }
        if (head == null)
        {
            System.out.println("No Item to remove");
        }
        else if (index == 1)
        {
            head = head.GetNextNode();
            noOfItems--;
        }
        else
        {
            int position = 0;
            DLLNode currentNode = head;

            while (currentNode != null) {
                if (position == index-1) {
                    currentNode.setNextNode(
                            currentNode.GetNextNode().GetNextNode());
                    noOfItems--;
                    break;
                }
                currentNode = currentNode.GetNextNode();
                position++;
            }
        }
    }
}

Any tips on where I can get started with converting this code would be greatly appreciated.

Kind Regards, Ben.

P.S. Apologies for the way the code has formatted - I've tried to fix it but it won't seem to sort. Can anyone good at formatting code on her please try and sort it out?

pnkkr pnkkr · Accepted Answer · 2016-12-10T14:40:57

Without further testing I think that you are forgetting to re-set the head reference of the node following the removed node:

if (position == index-1) {
    // Tail of currentNode is set to the node following
    // next node, but head of that node still points to the
    // node which should be removed from list
    currentNode.setNextNode(
        currentNode.GetNextNode().GetNextNode());
    noOfItems--;
    break;
}

Delete Item - Doubly Linked list using Tail Recursion

2 Answers