1

这是来自一个旧的作业问题，我已经上交了，但我无法弄清楚。我正在尝试使用我的用户定义的类从特定索引处的 LinkedList 中删除一个元素。下面是我正在处理的伪代码，但它没有与我相同的参数，所以我尝试修改它，但有一个问题。我是一个编程菜鸟（大约 6 个月的经验），仅供参考。我理解 ArrayLists 很好，但 LinkedLists 一直给我带来麻烦。

/*
 * Remove the nth element in the list.  The first element is element 1.
 * Return the removed element to the caller.

    function remove(List list, Node node)
        if node.prev == null
            list.firstNode := node.next
        else
            node.prev.next := node.next
        if node.next == null
            list.lastNode := node.prev
        else
            node.next.prev := node.prev
        destroy node
 */

我的方法要求用户输入要删除的索引位置。因为 int 和 LinkEntry 是不同的类型，所以我自然会遇到问题。我不知道如何合并通过参数传递的 int 。

public void remove(int n)
{
    LinkEntry<E> remove_this = new LinkEntry<E>();
    remove_this.element = n;

    for (remove_this = head; remove_this != null; remove_this = remove_this.next)
    {
        //removes the head if list is only 1 item long
        if (head.next == null)
            head = remove_this.next;
        else
            //sets previous element to the next element
            remove_this.previous.next = remove_this.next;

        //if nothing comes after remove_this, then remove the tail element
        if (remove_this.next == null)
            tail = remove_this.previous;
        else
            //sets next previous element to current previous element
            remove_this.next.previous = remove_this.previous;  
    }
}

如果您知道任何地方提供了另一个与我要解决的问题更相似的示例，我将不胜感激。我浏览了我的文字和在线，但没有运气。

4

2 回答 2

0

您应该将计数器设置为零，从第一个元素（显然名为“head”）浏览您的链表，然后递增计数器直到它等于 n（或者您到达列表的末尾）。

当 counter 等于 n 时，您必须将上一个条目连接到下一个，并且将下一个连接到上一个（因此它断开第 N 个）。您还必须注意特殊情况，当 n=1 时（您应该删除“head”条目，也就是说将 head 设置为 head.next），当 next 为空（n = 列表长度）时，以及当 n 为负数或大于列表长度时。

于 2012-10-06T20:56:20.880 回答
0

当我在遥远的银河系中了解到这一点时……它帮助我把它画在纸上。像这样的东西：

你有

              A       B       C
 next         *------>*------>*---->NULL
 prev NULL<---*<------*-------*

你想要

              A       C       
 next         *------>*---->NULL
 prev NULL<---*<------*

所以如果你找到B，你就知道该怎么做了。但是如何找到B？B 是我们上面示例中的第二个元素，因此我们将在从零开始的列表中给出“1”或在从一开始的列表中给出“2”。一个典型的场景是持有对列表第一个元素的引用。这通常被称为“头部”。现在你将从那个头开始并跟随它的next指针。你得到了什么？列表中的第二个元素。在我们的示例中，这已经是我们的“B”了。请注意，我们关注了next1 次……现在假设我们要删除 C。我们得到索引 2（或基于 1：3），我们从头开始，跟随next1 次并得到 B。1<2 所以遵循next再次。请注意，我们必须遵循 B 的 next 而不是“head”的所以如果使用循环，我们将不得不使用某种本地 var。现在我们有了第二个元素，即 C 并将其删除。请注意，C 的“下一个”是null. 所以我们在这个方向上已经完成了。

于 2012-10-06T21:23:58.610 回答