菜單項的雙向鏈接列表

Question

我有一個使用linkedList數據結構來處理菜單項（和子菜單項）的程序。我的程序工作除了刪除功能，如果刪除在現有元素之前插入的元素，但如果該元素插入到現有元素之後則不起作用。任何意見非常感謝！這裏的插入功能

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

我也意識到，我假設只有一個存在的元素，但是，如果我能刪除功能更通用那麼這將是最好的，我不想功能拆分成多種功能！這裏的刪除功能： -

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你插入一個新的節點。只有在列表的開頭或末尾插入時，如果您不在列表的開頭，則還需要更新先前/後面的元素的前一個/後一個元素旁邊插入到：

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

注：我也用，而不是兩個if小號

你刪除功能的else if聲明，也需要進行更新。你沒有更新的周圍的節點，只是要刪除的一個：

這似乎是不尋常，你會被搜索的節點之前/按值後插入

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

---

最後，搜索代碼不一樣，如果有列表中沒有的項目工作。下面一行將失敗，NullPointerException如果head爲null：

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

因爲你不能在一個空引用調用.equals(...)。