Bogue de liste liée - Numéros inconnus et fonction boguée

Question

J'ai récemment analysé les structures de données, en particulier la liste chaînée, et j'avais quelques difficultés à déterminer l'origine de certains nombres. Le numéro -2147483648 est affiché deux fois chaque fois que la liste est mise à jour et est toujours à la fin de la liste. Je n'ai aucune idée d'où vient ce nombre, mais il est toujours présent. Cela ne vaut rien que lorsque vous ajoutez un nouvel élément à la queue de la liste, la nouvelle valeur est placée entre les deux nœuds inconnus. Je vais mettre en évidence un exemple dans la sortie. Il est également intéressant de noter que la liste ne prend en compte que l'une des valeurs. Je vais aussi mettre cela en évidence dans la sortie. Enfin, la fonction remove, qui supprime un nœud spécifique, ne supprime aucun nœud qui n'est pas spécifié comme tête ou queue. Si j'essaie de supprimer un nœud au milieu, le nœud ne pourra pas être supprimé.

Toute aide déterminant la signification de ces nombres et une correction concernant la fonction de suppression sera appréciée. Merci!

Programmes de sortie:

//**with the two unknown numbers at the end, the list amounts to 10 elements, 
but the length variable returns 9. It is like this throughout the entire process**// 

Linked List Content:[1,2,3,4,5,6,7,8,-2147483648,-2147483648] 
Linked List Length:9 

//**adding the element 9 to the tail of the list places it between the two unknown numbers**// 

Updated Linked List Content:[1,2,3,4,5,6,7,8,-2147483648,9,-2147483648] 
Linked List Length:10 

//removes the tail node by calling removeTail function 
Updated Linked List Content:[1,2,3,4,5,6,7,8,-2147483648,-2147483648] 
Linked List Length:9 

//adds a new head node by calling insertHead function 
Updated Linked List Content:[0,1,2,3,4,5,6,7,8,-2147483648,-2147483648] 
Linked List Length:10 

//removes the head node by calling removeHead function 
Updated Linked List Content:[1,2,3,4,5,6,7,8,-2147483648,-2147483648] 
Linked List Length:9 

//adds a new node in the middle of the list by calling insert function 
Updated Linked List Content:[1,2,3,4,5,5,6,7,8,-2147483648,-2147483648] 
Linked List Length:10 

//**attempts to use the remove function to remove the extra 5 but it doesn't work**// 
Updated Linked List Content:[1,2,3,4,5,5,6,7,8,-2147483648,-2147483648] 
Linked List Length:10 

//clears the entire list by calling the clearList function 
Updated Linked List Content:[] 
Linked List Length:0 

Process finished with exit code 0 

La classe Node

public class ListNode { 
    private int data;     //the number or data that the node holds 
    public ListNode next;    //a pointer to the next node 
    public ListNode prev;    //a pointer pointing to the previous node 

    //constructors 
    public ListNode (int data, ListNode prev, ListNode next){ 
     this.data = data; 
     this.next = next; 
     this.prev = prev; 
    } 
    public ListNode (int data){ 
     this.data = data; 
     prev = null; 
     next = null; 
    } 

    //methods (getters and setters) 
    public int getData(){    //getter methods for the data variable 
     return data; 
    } 

    public void setData(int data){  //initializes that data object 
     this.data = data; 
    } 

    public ListNode getPrev(){return prev;} 

    public ListNode getNext(){return next;} 

    public void setPrev(ListNode where){prev = where;} 

    public void setNext(ListNode where){next = where;} 
    } 

La liste classe

public class LinkedLists { 
    private ListNode head;    //the first node in the list 
    private ListNode tail;    //the last node in the list 
    private int length;     //the length of the linked list 

    //specific constructor 
    //creating the list 
    public LinkedLists(){ 
     head = new ListNode(Integer.MIN_VALUE, null, null); 
     tail = new ListNode(Integer.MIN_VALUE, head, null); 
     head.setNext(tail); 
     length = 0; 
    } 

    //get the value at a given position 
    public int getValue(int position){ 
     return Integer.MIN_VALUE; 
    } 

    //find the position of the head value that is equal to the given value 

    public int getPosition(int data){ 
     //go looking for data 
     ListNode temp = head; 
     int pos = 0; 
     while (temp != null){ 
      if (temp.getData() == data){ 
       //return the position if found 
       return pos; 
      } 
      pos = pos+ 1; 
      temp = temp.getNext(); 
     } 
     //else return some larger value 
     return Integer.MIN_VALUE; 
    } 

    //return the current length of the LinkedList 
    public int length(){ 
     return length; 
    } 

    //add a new value to the front of the list 
    public void insertHead(int newValue){ 
     ListNode newNode = new ListNode(newValue, head, head.getNext()); 
     newNode.getNext().setPrev(newNode); 
     head.setNext(newNode); 
     length = length + 1; 
    } 

    //add a new value to the list at a given position 
    //all the values at the position to the end move over to make room 
    public void insert(int data, int position){ 
     //fix the position 
     if (position < 0){ 
      position = 0; 
     } 
     if (position > length){ 
      position = length; 
     } 
     //if the list is empty, make it be the only element 
     if (head == null){ 
      head = new ListNode(data); 
      tail = head; 
     } 
     //if adding at the front of the list 
     else if (position == 0){ 
      ListNode temp = new ListNode(data); 
      temp.next = head; 
      head = temp; 
     } 
     //else find the correct position and insert 
     else{ 
      ListNode temp = head; 
      for (int i = 1; i < position; i = i+1){ 
       temp = temp.getNext(); 
      } 
      ListNode newNode = new ListNode(data); 
      newNode.next = temp.next; 
      newNode.prev = temp; 
      newNode.next.prev = newNode; 
      temp.next = newNode; 
     } 
     //the list is now one value longer 
     length ++; 
    } 

    //add a new value to the rear of the list 
    public void insertTail(int newValue){ 
     ListNode newNode = new ListNode(newValue, tail.getPrev(),tail); 
     newNode.getPrev().setNext(newNode); 
     tail.setPrev(newNode); 
     length++; 
    } 

    //remove the value at a given position 
    public void remove(int position){ 
     //if the position is less than 0, remove the value at position 0 
     if (position < 0){ 
      position = 0; 
     } 
     //if the position is greater than 0, remove the value at the last position 
     if (position > 0){ 
      position = length - 1; 
     } 
     //if the list is empty, do nothing 
     if (head == null){ 
      return; 
     } 
     //if removing the head element 
     if (position ==0){ 
      head = head.getNext(); 
      if (head == null){ 
       tail = null; 
      } 
      //else advance to the correct position and remove 
      else{ 
       ListNode temp = head; 
       for (int i = 1; i< position; i++){ 
        temp = temp.getNext(); 
       } 
       temp.getNext().setPrev(temp.getPrev()); 
       temp.getPrev().setNext(temp.getNext()); 
      } 
      //reduce the length of the list 
      length --; 
     } 
    } 
    //remove a node matching a specified node from the list 
    public synchronized void removeMatched(ListNode node){ 
     if (head == null){ 
      return; 
     } 
     if (node.equals(head)){ 
      head = head.getNext(); 
      if (head == null){ 
       tail = null; 
      } 
      return; 
     } 
     ListNode p = head; 
     while (p!= null){ 
      if (node.equals(p)){ 
       p.prev.next = p.next; 
       p.next.prev = p.prev; 
       return; 
      } 
     } 
    } 

    //remove the head value from the list 
    //if the list is empty, do nothing 
    public int removeHead(){ 
     if (length ==0){ 
      return Integer.MIN_VALUE; 
     } 
     ListNode save = head.getNext(); 
     head.setNext(save.getNext()); 
     save.getNext().setPrev(head); 
     length --; 
     return save.getData(); 
    } 

    ////remove the tail value from the list 
    //if the list is empty, do nothing 
    public int removeTail(){ 
     if (length ==0){ 
      return Integer.MIN_VALUE; 
     } 
     ListNode save = tail.getPrev(); 
     tail.setPrev(save.getPrev()); 
     save.getPrev().setNext(tail); 
     length --; 
     return save.getData(); 
    } 

    //return a string representation of this collection 
    public String toString(){ 
     String result = "[]"; 
     if (length == 0){ 
      return result; 
     } 
     result = "[" + head.getNext().getData(); 
     ListNode temp = head.getNext().getNext(); 
     while(temp != null){ 
      result += "," + temp.getData(); 
      temp = temp.getNext(); 
     } 
     return result + "]"; 
    } 

    //remove everything from the list 
    public void clearList(){ 
     head = null; 
     tail = null; 
     length = 0; 
    } 
} 

Le fichier principal

public class main { 
    public static void main(String args[]){ 
     //Linked list declaration 
     LinkedLists linkedlist = new LinkedLists(); 

     //add more elements to the list 
     linkedlist.insert(0,1); 
     linkedlist.insert(1,2); 
     linkedlist.insert(2,3); 
     linkedlist.insert(3,4); 
     linkedlist.insert(4,5); 
     linkedlist.insert(5,6); 
     linkedlist.insert(6,7); 
     linkedlist.insert(7,8); 
     linkedlist.insert(8,9); 

     //display linked list contents and its length 
     System.out.println("Linked List Content:" + linkedlist); 
     System.out.println("Linked List Length:" + linkedlist.length()); 


     //add an element to the end of the list and also print out its length 
     //O(n) 
     linkedlist.insertTail(9); 
     System.out.println("Updated Linked List Content:" + linkedlist); 
     System.out.println("Linked List Length:" + linkedlist.length()); 
     //the new list should now be [1,2,3,4,5,6,7,8,9] 


     //remove the element at the end of the list that was just added 
     linkedlist.removeTail(); 
     System.out.println("Updated Linked List Content:" + linkedlist); 
     System.out.println("Linked List Length:" + linkedlist.length()); 


     //add an element to the head of the list 
     linkedlist.insertHead(0); 
     System.out.println("Updated Linked List Content:" + linkedlist); 
     System.out.println("Linked List Length:" + linkedlist.length()); 
     //the new list should be: [0,1,2,3,4,5,6,7,8] 


     //delete that same element from the front of the list 
     linkedlist.removeHead(); 
     System.out.println("Updated Linked List Content:" + linkedlist); 
     System.out.println("Linked List Length:" + linkedlist.length()); 



     //Insert an element into the middle of the list 
     linkedlist.insert(5,6); 
     System.out.println("Updated Linked List Content:" + linkedlist); 
     System.out.println("Linked List Length:" + linkedlist.length()); 



     //remove a value into the middle of the list 
     //BUG INSIDE THE REMOVE FUNCTION!!! THE VALUE REMAINS INSIDE THE LIST 
     linkedlist.remove(6); 
     System.out.println("Updated Linked List Content:" + linkedlist); 
     System.out.println("Linked List Length:" + linkedlist.length()); 
     //the 5 should be removed from the list 



     //clear the entire list 
     linkedlist.clearList(); 
     System.out.println("Updated Linked List Content:" + linkedlist); 
     System.out.println("Linked List Length:" + linkedlist.length()); 
    } 
} 

Answer 1

Deux numéros inconnus que vous voyez dans votre liste sont là à cause de

head = new ListNode(Integer.MIN_VALUE, null, null); 
tail = new ListNode(Integer.MIN_VALUE, head, null); 

Votre méthode insertTail() est le nœud Insertion mal

public void insertTail(int newValue){ 
    ListNode newNode = new ListNode(newValue, tail.getPrev(),tail); 
    newNode.getPrev().setNext(newNode); 
    tail.setPrev(newNode); 
    length++; 
} 

Ce sera toujours ajouter un nouveau noeud entre le dernier et l'avant-dernier noeud . Vous devez modifier quelque chose comme ceci à ajouter à la fin

public void insertTail(int newValue){ 
    ListNode newNode = new ListNode(newValue, tail,null); 
    tail.setNext(newNode); 
    tail = newNode; 
    length++; 
} 

De même la suppression d'un élément de queue doit être fait

public int removeTail(){ 
    if (length ==0){ 
     return Integer.MIN_VALUE; 
    } 
    ListNode returnNode = tail; 
    tail.getPrev().setNext(null); 
    tail = tail.getPrev(); 
    length --; 
    return returnNode.getData(); 
}