java - 单链表转循环链表

Question

我一直在尝试通过调整我的 add() 和 remove() 方法将我的单链表变成双循环链表。

这是我的代码:

private LLNode<E> head;     // the first node in the list
private LLNode<E> tail;     // the last node in the list

// Adds the specified new item to the back of the list.
public void add(E newData)
{
    if (head == null)   // if the list is empty...
        addToHead(newData);       
    else    
        addAfter(newData, nodeAt(size - 1));
}

// Removes and returns the item at the specified index of the list.
public E remove(int index)
{
    if (index == 0)         // if removing from the head...
        return removeFromHead();
    else
        return removeAfter(nodeAt(index - 1));
}

    private void addToHead(E newItem)
    {
        LLNode<E> newNode = new LLNode<E>();
        newNode.data = newItem;
        newNode.next = head;      
        head = newNode;
        head.prev = tail;
        tail.next = newNode;
        size++;
    }

// Removes the head node from the list.
private E removeFromHead()
{
    if (head != null) {
        E temp = head.data;
        head = head.next;
        head.prev = tail;
        tail.next = head;
        size--;
        return temp;
    } else
        throw new NoSuchElementException();
}

// Adds a new node containing the specified data, after the
//  specified node in the list.
private void addAfter(E newItem, LLNode<E> where)
{
    if (where != null) {
        LLNode<E> newNode = new LLNode<E>();
        newNode.data = newItem;
        newNode.next = where.next;
        where.next = newNode;
        newNode.prev = where;
        size++;
    } else {
        throw new NoSuchElementException();
    }
}

// Removes the node after the specified node in the list.
private E removeAfter(LLNode<E> where)
{
    if (where != null && where.next != null) {
        E temp = where.next.data;
        where.next = where.next.next;
        where.next.prev = where;
        size--;
        return temp;
    } else
        throw new NoSuchElementException();
}

在我的主要方法中:

TopSpinLinkedList<Integer> ll = new TopSpinLinkedList<Integer>(numTokens, spinSize);

    //fills LinkedList with tokens
    for(int i = 1; i <= numTokens; i++) {
        ll.add(i);
    }

当我尝试调用此方法时:

//shifts all elements in LinkedList to left by one
public void shiftLeft()
{
    if(head == null || head.next == null)
        return;
    LLNode<E> temp = new LLNode<E>();
    temp = head;
    head = head.next;
    temp.next = null;
    tail.next = temp;
    tail = temp;
}

运行时出现 NullPointerException。我很确定它与我的 add() 和 remove() 方法有关。我只是不明白我到底做错了什么，将其变成双循环链表。任何帮助将非常感激。

Answer 1

在您的 addToHead 方法中，您确定在执行 tail.next = newNode 时已经初始化了 tail 变量吗？

试试这个:

private void addToHead(E newItem)
    {
        LLNode<E> newNode = new LLNode<E>();
        newNode.data = newItem;
        head = newNode;
        tail = newNode;
        newNode.prev = newNode.next = newNode;
        size++;
    }