链接列表问题 - 未知数字和Bugged函数

Question

我一直在刷新最近的数据结构，特别是链表，并且在确定某些数字的起源时遇到了一些麻烦。每次列表更新时，编号为-2147483648的数字会显示两次，并且它始终位于列表的末尾。我不知道这个数字来自哪里，但它始终存在。当向列表尾部添加新元素时，新值将放置在两个未知节点之间，这是毫无价值的。我将在输出中突出显示一个示例。值得注意的是，该清单仅仅是其中一个值。我也会在输出中突出显示这一点。

最后，删除特定节点的remove函数无法删除未指定为头部或尾部的任何节点。如果我尝试删除中间的任何节点，该节点将无法删除。

任何帮助确定这些数字的重要性和修复有关删除功能将赞赏。谢谢！

程序输出：

//**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 

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;} 
    } 

List类

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; 
    } 
} 

主要文件

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

个

两个你看到在你的列表未知号码是那里，因为

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

你insertTail（）方法插入节点错误

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

的这会随时添加最后和倒数第二个节点之间的新节点。您需要修改它像这样在结尾处添加

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

同样去除尾应做

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