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 = последний; Я могу понять, почему, но я не уверен, как исправить это, не нарушая список. Любые решения? Возможно, нет необходимости использовать двусвязный формат (т. Е. Вообще удалить основной ссылочный узел)?

Answer 1

Вы избегаете исключения NullPointerException, избегая доступа к неинициализированным переменным.

В этом конкретном примере, оставить из:

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

в конструкторе и использовать оборонительное программирование и проверить нуль, если она может быть инициализирована, перед обращением к переменному.

Например в методе 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 пуст, нет «следующего» и «предыдущего». Он полностью пуст. Было бы «следующее» и «предыдущее» только после получения данных.

Поэтому, когда вы инициализируете Deque, вам не следует пытаться назначить prev и next на номера null. Тот факт, что они null указывает, что там ничего нет, поэтому, конечно, ничего не происходит раньше или после него.

И, конечно, размер должен быть равен нулю.

Тогда в ваших addFirst и addLast методы, вы должны обрабатывать случай, когда ваш first и last равны нулю. В этом случае вы должны инициализировать их как с тем же значением, где next и prev оба являются null. И установите размер в 1.

Выполняется только так, как вы это сделали (добавьте элемент, исправьте связь), если элемент в first или last соответственно не равен нулю.

И не забудьте проверить на null в ваших методах removeFirst и removeLast.

Краткая версия: случай с пустым списком является особым. Вы должны начать с пустого списка. Вы должны проверить этот специальный случай в своих методах add и remove.