鏈接列表問題 - 未知數字和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(); 
}