I've been brushing up on data structures recently, specifically linked list, and was having some trouble determining the origin of some numbers. The number -2147483648 is shown twice each time the list is updated and it is always at the end of the list. I have no idea where this number comes from, but it is always present. It is worth nothing that when adding a new element to the tail of the list, the new value is placed between the two unknown nodes. I will highlight an example in the output. It is also worth noting that the list only accounts for one of the values. I will also highlight this in the output.
我最近一直在研究数据结构，特别是链表，并且在确定某些数字的来源方面遇到了一些麻烦。每次更新列表时，数字-2147483648显示两次，它始终位于列表的末尾。我不知道这个号码来自哪里，但它始终存在。在向列表的尾部添加新元素时，新值放在两个未知节点之间是没有价值的。我将在输出中突出显示一个示例。值得注意的是，该列表仅考虑其中一个值。我还将在输出中突出显示这一点。
Lastly, the remove function, which removes a specific node fails to remove any node that isn't specified as the head or tail. If i try to remove any node in the middle, the node will fail to be removed.
最后，删除特定节点的remove函数无法删除未指定为head或tail的任何节点。如果我尝试删除中间的任何节点，将无法删除该节点。
Any help determining the significance of these numbers and a fix regarding the remove function will appreciated. Thanks!
任何确定这些数字的重要性的帮助和关于删除功能的修复都将受到赞赏。谢谢！
Programs Output:
节目输出：
//**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
The Node class
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;}
}
The List class
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;
}
}
The main file
主文件
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());
}
}
1 个解决方案
#1
1
Two unknown numbers you are seeing in your list are there because of
你在列表中看到的两个未知数字是因为
head = new ListNode(Integer.MIN_VALUE, null, null);
tail = new ListNode(Integer.MIN_VALUE, head, null);
Your insertTail() method is inserting node wrongly
您的insertTail（）方法错误地插入节点
public void insertTail(int newValue){
ListNode newNode = new ListNode(newValue, tail.getPrev(),tail);
newNode.getPrev().setNext(newNode);
tail.setPrev(newNode);
length++;
}
This will always add new node between Last and Second Last Node. You need to modify it something like this to add at end
这将始终在Last和Second Last Node之间添加新节点。您需要修改它，以便最后添加
public void insertTail(int newValue){
ListNode newNode = new ListNode(newValue, tail,null);
tail.setNext(newNode);
tail = newNode;
length++;
}
Similarly removing an item from tail shall be done
同样地，应该从尾部移除一个项目
public int removeTail(){
if (length ==0){
return Integer.MIN_VALUE;
}
ListNode returnNode = tail;
tail.getPrev().setNext(null);
tail = tail.getPrev();
length --;
return returnNode.getData();
}
#1
1
Two unknown numbers you are seeing in your list are there because of
你在列表中看到的两个未知数字是因为
head = new ListNode(Integer.MIN_VALUE, null, null);
tail = new ListNode(Integer.MIN_VALUE, head, null);
Your insertTail() method is inserting node wrongly
您的insertTail（）方法错误地插入节点
public void insertTail(int newValue){
ListNode newNode = new ListNode(newValue, tail.getPrev(),tail);
newNode.getPrev().setNext(newNode);
tail.setPrev(newNode);
length++;
}
This will always add new node between Last and Second Last Node. You need to modify it something like this to add at end
这将始终在Last和Second Last Node之间添加新节点。您需要修改它，以便最后添加
public void insertTail(int newValue){
ListNode newNode = new ListNode(newValue, tail,null);
tail.setNext(newNode);
tail = newNode;
length++;
}
Similarly removing an item from tail shall be done
同样地，应该从尾部移除一个项目
public int removeTail(){
if (length ==0){
return Integer.MIN_VALUE;
}
ListNode returnNode = tail;
tail.getPrev().setNext(null);
tail = tail.getPrev();
length --;
return returnNode.getData();
}