одинарный связанный список в круговой связанный список

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


java linked-list doubly-linked-list circular-list
person GreatBambino    schedule 15.04.2013    source источник
comment
в хвосте.следующий = новыйУзел; в методе addToHead()   -  person GreatBambino    schedule 15.04.2013

Ответы (3)


arrow_upward
1
arrow_downward

В вашем методе addToHead вы уверены, что инициализировали свою переменную tail, когда делаете tail.next = newNode?

Попробуй это :

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

arrow_upward
0
arrow_downward 

private void addToHead(E newItem){
    LLNode<E> newNode = new LLNode<E>();
    newNode.data = newItem;

    // head and tail are empty
    head = newNode;
    tail = newNode;
    head.next = newNode;
    tail.next = newNode;
    head.prev = newNode;
    tail.prev = newNode;
}


private void addAfter(E newItem, LLNode<E> where){
    if (where != null) {
        LLNode<E> newNode = new LLNode<E>();
        newNode.data = newItem;


        //this part is what you need
        newNode.next = where;
        newNode.prev = where.prev;
        where.prev.next = newNode; 
        where.prev = newNode;
        size++;
    } else {
        throw new NoSuchElementException();
    }
}

// Я изменил свой код, теперь это должно работать. // Я сдвинул элемент where на одну позицию вправо и вставил новый узел на его место.

Кроме того, если вы используете дважды круговой связанный список, вам не нужно иметь хвост. Вы можете просто избавиться от него.

person smttsp    schedule 15.04.2013

arrow_upward

arrow_downward

person    schedule
comment
Возможно, вы захотите предоставить некоторый контекст для этих ошибок, которые вы обнаружили, и как вы их исправили. Таким образом, мы все могли бы учиться. - person rajah9; 16.11.2016