Iterable Deque NullPointerException

Question

我正在嘗試通過實現雙向鏈表格式來創建一個Deque類（可以添加到並在兩端引用的Stack/Queue）。

import java.util.Iterator; 

公共類的Deque實現了Iterable {

Node first; 
Node last; 
int size; 

public Deque() 
{ 
    first = null; 
    last = null; 
    size = 2; 

    first.next = last; 
    last.prev = first; 
} 

private class Node 
{ 
    Node next; 
    Node prev; 
    Item item; 
} 

private class ListIterator implements Iterator<Item> 
{ 
    private Node current = first; 

    public boolean hasNext() 
    { 
     return current.next != null; 
    } 
    public Item next() 
    { 
     Item item = current.item; 
     current = current.next; 
     return item; 
    } 
    public void remove() 
    { 
     /* not supported */ 
    } 
} 

public boolean isEmpty() 
{ 
    if(first == null&&last == null) 
     return true; 
    return false; 
} 

public int size() 
{ 
    return size; 
} 

public void addFirst(Item item) 
{ 
    Node oldfirst = first; 
    first = new Node(); 
    first.item = item; 
    first.next = oldfirst; 
    oldfirst.prev = first; 
    size++; 
} 

public void addLast(Item item) 
{ 
    Node oldlast = last; 
    last = new Node(); 
    last.item = item; 
    last.prev = oldlast; 
    oldlast.next = last; 
    size++; 
} 

public Item removeFirst() 
{ 
    Item item = first.item; 
    first = first.next; 
    size--; 
    return item; 
} 

public Item removeLast() 
{ 
    Item item = last.item; 
    last = last.next; 
    size--; 
    return item; 
} 

@Override 
public Iterator<Item> iterator() 
{ 
    return (new ListIterator()); 
} 

public static void main(String[] args) 
{ 
    Deque<Integer> deque = new Deque<Integer>(); 
    for(int i=0; i<5; i++) 
    { 
     deque.addFirst(i); 
     deque.addLast(9-i); 
    } 

    for(Integer i : deque) 
    { 
     StdOut.println(i); 
    } 
} 

}

當我運行代碼，我得到一個NullPointerException異常時，它試圖做first.next =最後;我可以理解爲什麼，但我不確定如何修復它，而不會破壞列表。任何解決方案可能沒有必要使用雙向鏈接格式（即完全刪除prev引用節點）？

Answer 1

通過避免訪問未初始化的變量，避免了NullPointerException。

在特定的例子中，離開了：

first.next = last; 
last.prev = first; 

在構造函數

，並使用防禦性編程和檢查null如果能夠未初始化，訪問變量之前。

例如，在您的addfirst僅方法：

public void addFirst(Item item) 
{ 
    Node oldfirst; 
    if (first != null){ 
     oldfirst = first; 
    } 

    first = new Node(); 
    first.item = item; 

    if (oldfirst != null){ 
     first.next = oldfirst; 
     oldfirst.prev = first; 
    } 
    size++; 
} 

等

順便說一句，這是一個學習的過程？如果沒有，Java庫確實已經準備使用Deques，包括鏈表： http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

Answer 2

你的尺寸是從2開始的？它應該是0，直到您添加Item。

您的初始條件應該是prev和next都是null。當您添加單個項目時，大小應爲1，並且prev和next都應該指向該對象。

Answer 3

當Deque爲空時，不存在「next」和「previous」。它完全是空的。只要有數據，就會有「下一個」和「前一個」。

所以當你初始化Deque時，你不應該試圖分配一個prev和next到null引用。他們是null這一事實表明這裏沒有什麼東西，所以當然之前或之​​後沒有任何東西出現。

當然，大小應該爲零。

然後，在您的addFirst和addLast方法中，您應該處理您的first和last爲空的情況。在這種情況下，您必須將它們初始化爲相同的值，其中next和prev都是null。並且將尺寸設置爲1.

如果first或last中的項目分別不爲空，則只能按照您的操作（添加項目，更正鏈接）繼續。

並記得在您的removeFirst和removeLast方法中檢查null。

簡短版本：空列表的情況很特殊。你應該從一個空的列表開始。你應該在你的add和remove方法中檢查這個特殊情況。