java - 链接列表错误 - 未知数字和错误函数

Question

我最近一直在温习数据结构，特别是链表，并且在确定某些数字的来源时遇到了一些麻烦。每次更新列表时，数字 -2147483648 都会显示两次，并且始终位于列表末尾。我不知道这个数字从何而来，但它始终存在。值得注意的是，当向列表尾部添加新元素时，新值被放置在两个未知节点之间。我将在输出中突出显示一个示例。还值得注意的是，该列表仅占其中一个值。我还将在输出中突出显示这一点。

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

任何帮助确定这些数字的重要性以及有关删除功能的修复的帮助将不胜感激。谢谢!

程序输出:

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

节点类

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

列表类

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