Вставка с фиктивной головой и хвостом в конец связанного списка - PullRequest
Новая
       96

Вставка с фиктивной головой и хвостом в конец связанного списка

0 голосов
/ 20 июня 2020

Как указано в заголовке, я пытаюсь вставить узел в конец двусвязного списка с фиктивной головой и узлом. Это проект, над которым я работаю для школы, и поэтому сейчас я использую то, что работает, пока я работаю над остальным, что нужно сделать. А пока, если кто-то может помочь мне отладить, я был бы признателен, так как я действительно не могу найти, почему я получаю ошибку NULLPOINTER.

Я знаю, почему возникает нулевой указатель, но из того, что я Из ресурсов, которые я искал (некоторые из них находятся в конце этого сообщения), я понял, что то, что я написал, должно работать.

Я получаю ошибку NULLPOINTER на tempNode.prev = tail.prev; и, насколько я понимаю, Играя с моим кодом, я больше не могу получить доступ к хвосту или его следующему и предыдущему. Но дело не в фиктивном узле, что я продолжаю перемещать его указатели для управления списком?

То, с чем мне нужна помощь:

  • Как перемещать указатели фиктивных узлов?
  • Что я здесь делаю не так?
  • Какая альтернатива?

Прошу прощения за мой абзац комментариев, я поговорите с моим кодом. 

public void insert(T data) //insert data into the linked list --  at the end
{
    /* create a node with the incoming "data"
     * Assigns the data to tempNode.data and the .next pointer is null */
    Node<T> tempNode = new Node();
    tempNode.data = data;
    tempNode.next = null;

    /*
     * head and tail are dummy nodes and we need to add to the end of the list
     * To do so, we don't add to tail, we add to .prev of tail. 
     * It doesn't matter if the list is empty or not.
     * 
     * Starting by moving the pointers of the node before tail:
     *      the .next of the node before tail should now point to tempNode
     *      the .prev of tempNode should point to the node before tail.
     * 
     * Now we move the pointers of tail itself.
     *      the .prev of tail points to tempNode
     *      the .next of tempNode should point to tail.
     * 
     * Node is inserted, now the next time a node is added, it follows the same steps.
     */
    
    /*
     * This is so far the only way it works. I can't use it this way since it doesn't
     *      account for dummy nodes and instead, replaces them.
    if(head == null)
    {
        head = tempNode;
        tail = tempNode;
    }
    else
    {
                    
        tail.next = tempNode;
        tempNode.prev = tail;
        tail = tempNode;         
    }
    */ 
    
    tempNode.prev = tail.prev;
    tail.prev.next = tempNode;
    
    tail.prev = tempNode;
    tempNode.next = tail;
}

/*************************************************************************/

public class LinkedList<T> implements Iterable<T>
{
    public static void main(String [] args)
    {
      Double A[]={0.1,0.34,0.7,23.1,-0.75};
      LinkedList<Double> M = new LinkedList<Double>(A);
      System.out.println("Linked List: " + M);
    }

    public LinkedList(T [] A) //create a linked list from an array
    {
      int i = 0;
      int sizeOfArray = A.length - 1;

      for(i = 0; i <= sizeOfArray; i++)
      {
        LinkedList.this.insert(A[i]);
      }
    }

    private class Node<T>
    {
      Node(){}
      Node(T data){ this.data=data; }
      public T data;
      public Node<T> next;
      public Node<T> prev; //for doubly linked list
    }

    Node<T> head; //pointing to the location BEFORER the first element
    Node<T> tail; //for doubly linked list
    //pointing to the location AFTER the last element

    public LinkedList() //constructor
    {
      head=new Node<T>();
      tail=new Node<T>();
      head.next=tail;
      tail.prev=head;
    }

    public String toString()
    {
      String S="(";
      for(T t : this) S=S+t+", ";
      if(is_empty()==false) S=S.substring(0,S.length()-2);
      S=S+")";
      return S;
    }
}

C / C ++: Связанный список фиктивного главного узла | Реализация двусвязного списка с фиктивной головой и хвостом

JAVA: GeeksforGeeks: похоже на то, что я написал * Я думаю * | OpenDataStructures: это тоже похоже | связанный список с пустой головой java

РЕДАКТИРОВАТЬ:

  1. Добавлены важные части кода для запуска insert ()
  2. insert ( ) должен быть в классе LinkedList, но форматирование становилось немного странным, поэтому я оставил его вверху.
...