双重链接的菜单项列表

Question

我有一个程序，它使用linkedList数据结构处理菜单项(和子菜单项)。我的程序工作，除了delete函数，如果删除插入的元素之前的一个现有的元素，但不如果元素插入后，现有的元素。任何建议都非常感谢!下面是插入函数

public Item insert(String newElem, String existingElem, int key) {
    // search for given existing element starting at head
    currentNode = new Item("");
    currentNode = head;
    while (!currentNode.element.equals(existingElem)) {
        currentNode = currentNode.next;
        if (currentNode == null)
            break; // cannot find the given key
    }
    // create a new node
    newNode = new Item(newElem);
    if (key == 1) // if key = 1 insert after the existing element
    {
        newNode.next = currentNode.next;
        newNode.prev = currentNode;
        currentNode.next = newNode;
        tail = newNode;
        tail.next = null;
        counter++;
    }
    if (key == 2) // if key = 2 insert before the existing element
    {
        newNode.next = currentNode;
        newNode.prev = currentNode.prev;
        currentNode.prev = newNode;
        head = newNode;
        head.prev = null;
        counter++;
    }
    return newNode;
}

我也意识到我假设只有一个现有的元素，但是，如果我能使删除函数更通用，那么它将是最好的，我不想将函数分割成多个函数!下面是delete函数:-

public Item delete(String elem) {
    // search for given existing element starting at head
    currentNode = new Item("");
    currentNode = head;
    while (!currentNode.element.equals(elem)) {
        currentNode = currentNode.next;
        if (currentNode == null)
            break; // cannot find the given key
    }
    // check if element is the first element
    if (currentNode == head) {
    head = currentNode.next;
    } else {
        currentNode.prev = currentNode.next;
    }
    // check if element is the last element
    if (currentNode == tail) {
        tail = currentNode.prev;
    } else {
        currentNode = currentNode.prev;
    }
    return currentNode;
}

Answer 1

问题

您不应该在每次插入新节点时更新tail和head。你应该只在列表的开始或结束插入时这样做，如果你不在列表的开始，你还需要更新元素的prev/next，它曾经在你插入的元素之前/之后:

if (key == 1) // if key = 1 insert after the existing element
{
    newNode.next = currentNode.next;
    newNode.prev = currentNode;
    currentNode.next = newNode;
    if (newNode.next == null)
        tail = newNode;
    else
        newNode.next.prev = newNode;
}
else if (key == 2) // if key = 2 insert before the existing element
{
    newNode.next = currentNode;
    newNode.prev = currentNode.prev;
    currentNode.prev = newNode;
    if (newNode.prev == null)
        head = newNode;
    else
        newNode.prev.next = newNode;
}

注意:我也使用 else if 语句，而不是两个 if s

你的删除功能也需要更新。您没有更新周围的节点，只是要删除的节点:

if (currentNode.prev == null) { // is head 
    head = currentNode.next;
} else {
    currentNode.prev.next = currentNode.next;
}
if (currentNode.next == null) { // is tail
    tail = currentNode.prev;
} else {
    currentNode.next.prev = currentNode.prev;
}

其他评论

似乎不寻常的是，你会搜索节点插入之前/之后的值，如果我有一个这样的列表:[1,2,2,2,3]?在该列表中的多个位置插入一个值是不可能的。当然，你的API应该基于Item s:

public Item insert(String newValue, Item existingItem, int key);
public Item delete(Item item);

或indicies:

public Item insert(String newValue, int index, int key);
public Item delete(int index);

您可以使用另一种方法来查找特定值的Item或索引:

public Item find(String value);

或:

public int indexOf(String value);

并像这样使用它们来获得你的方法的等价物:

list.insert("value", list.find("other value"), 1);

---

您可能需要考虑将insert方法更改为insertBefore和insertAfter方法，或者至少将key参数更改为枚举类型:

public enum Position {
    BEFORE,
    AFTER,
}

毕竟，当key为0或23时会发生什么?

---

你目前有currentItem作为一个类成员，它应该是函数的一个局部变量(毕竟，它在这些函数之外有什么用)，你也不需要初始化它为一个新元素，只需要将它直接设置为head:

public Item insert(String newElem, String existingElem, int key) {
    Item currentNode = head;
    ...
}

---

最后，如果列表中没有项目，您的搜索代码将无法工作。如果head为空，下面一行将失败，因为NullPointerException:

while (!currentNode.element.equals(existingElem))

因为你不能在空引用上调用.equals(...)