删除项目 - 使用尾递归的双向链表

Question

我目前正在学习双向链表。

我已经设法转换成一个几乎 100% 可用的双向链表。但是我需要学习如何用尾递归来写它。

下面是我的 DLLNode 代码：

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);
        }
    }

}

我已经设法让我的 AddItem 使用尾递归工作，我现在正在研究让 delete Item 工作。我猜想像 addItem 一样，我需要将 deleteItem 添加到我的 DLLNode。

下面是我的 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++;
            }
        }
    }
}

任何有关我可以从哪里开始转换此代码的提示，我们将不胜感激。

亲切的问候，本.

P.S。对代码格式化的方式表示歉意 - 我试图修复它，但它似乎无法排序。有谁擅长格式化她的代码，请尝试整理一下？

Answer 1

private void DeleteItemHelper(final int indexToDelete, int curIndex, DLLNode curNode) {
    if (curIndex == indexToDelete) {
        // Handle removing a node with both a previous and next nodes.
    }

    else {
        DeleteItemHelper(indexToDelete, curIndex + 1, curNode.getNextNode());
    }
}


public void DeleteItem(int index) {
    DeleteItemHelper(index, 0, head);
}

Answer 2

未经进一步测试，我认为您忘记重新设置已删除节点之后的节点的头部引用：

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

java

algorithm

linked-list

doubly-linked-list