我现在正在制作一个项目来练习双链表,并且我一直在我的双链表类中研究一种切换节点位置的方法。当尝试切换非相邻节点时它工作正常,但是当尝试切换相邻节点时会出现错误。
如果起始列表是:
输出将是
我试图找出错误,但我的知识缺乏,任何帮助都会很棒,我很感激!
我尝试创建一个临时节点来保存节点的原始上一个和下一个节点,但这不起作用。 我尝试了 if 语句来检查上一个和下一个是否相等,但这不起作用。
这是我的代码
public void switchNodes(int firstSpace, int secondSpace){
//If statement which checks isEmpty(), and if firstSpace and secondSpace is less than 0.
if(isEmpty()|| firstSpace < 0 || secondSpace < 0){
System.out.println("List is empty or one of spaces is entered does not have anything in it.");//If any of the previous if scenarios is met, prints a message telling the user that.
}
else{
Node<E> firstN = current(firstSpace); //Creates a node firstN by calling the current method and using the imported firstSpace int.
Node<E> secondN = current(secondSpace); //Creates a node secondN by calling the current method and using the imported secondSpace int.
switchSpace(firstN, secondN);//Calls the switchSpace method with nodes firstN and secondN.
}
}
/**
*Private method which takes in two nodes and switches their positions on the list.
* Done by creating two nodes with the information imported from the switchNodes method.
* The created nodes contain the same element and the swapped prev and next.
* The nodes around the swapped nodes are then accessed and replaced to the swapped nodes address.
*/
private void switchSpace(Node<E> firstSwitch, Node<E> secondSwitch){
//Creates switchedFirst node to contain the element of the imported firstSwitch node and the addresses of the secondSwitch node.
Node<E> switchedFirst = new Node<E>(firstSwitch.getElement(), secondSwitch.getPrev(), secondSwitch.getNext());
//Creates switchedSecond node to contain the element of the imported secondSwitch node and the addresses of the firstSwitch node.
Node<E> switchedSecond = new Node<E>(secondSwitch.getElement(), firstSwitch.getPrev(), firstSwitch.getNext());
switchedFirst.getNext().setPrev(switchedFirst);//The node after the switchedFirst nodes new position is accessed and the prev address is set to switchedFirst.
switchedFirst.getPrev().setNext(switchedFirst);//The node before the switchedFirst nodes new position is accessed and the next address is set to switchedFirst.
switchedSecond.getNext().setPrev(switchedSecond);//The node after the switchedSecond nodes new position is accessed and the prev address is set to switchedSecond.
switchedSecond.getPrev().setNext(switchedSecond);//The node before the switchedSecond nodes new position is accessed and the next address is set to switchedSecond.
}
您的问题来自于您创建更新节点的方式。假设你有这个清单(抱歉画得不好):
a <--> b <--> c <--> d
并且你想交换 b 和 c。
您正在通过将其
ub
和 prev
分别设置为 c 的 next
和 prev
来创建更新的 b(next
)。
类似地,更新后的 c(uc
) 是通过将其 prev
和 next
分别设置为 b 的 prev
和 next
来创建的。
<----ub---->
/ \
a <--> b <--> c <--> d
\ /
<------uc--->
现在您正在尝试将旧的上一个和下一个链接到新的。
<---ub<---->
/ \
a <--- b <--> c --> d
\ /
<--->uc----->
现在,如果你遍历它,你会得到
a
、uc
、c
、d
仅当 prev/next 指向任何要替换的节点时,才会出现此问题。要解决此问题,如果有任何 next/prev 指向旧节点,则需要用更新的节点替换旧节点。这是更新后的代码
private void switchSpace(Node<E> firstSwitch, Node<E> secondSwitch){
// Creates updatedFirst node to contain the element of the second node
// Don't set the prev and next yet
Node<E> updatedFirst = new Node<E>(secondSwitch.getElement(), null, null);
// Creates updatedSecond node to contain the element of the First node
// Don't set the prev and next yet
Node<E> updatedSecond = new Node<E>(firstSwitch.getElement(), null, null);
// Find the prev and next of the old nodes. If any prev/next point to any old element that is
// about to be replaced, use the new one in its place
Node<E> prev1 = firstSwitch.getPrev() == secondSwitch ? updatedSecond : firstSwitch.getPrev();
Node<E> next1 = firstSwitch.getNext() == secondSwitch ? updatedSecond : firstSwitch.getNext();
Node<E> prev2 = secondSwitch.getPrev() == firstSwitch ? updatedFirst : secondSwitch.getPrev();
Node<E> next2 = secondSwitch.getNext() == firstSwitch ? updatedFirst : secondSwitch.getNext();
// Set the prev and next of the updated nodes
if (next2 != null) {
next2.setPrev(updatedSecond);
updatedSecond.setNext(next2);
}
if (prev2 != null) {
prev2.setNext(updatedSecond);
updatedSecond.setPrev(prev2);
}
if (next1 != null) {
next1.setPrev(updatedFirst);
updatedFirst.setNext(next1);
}
if (prev1 != null) {
prev1.setNext(updatedFirst);
updatedFirst.setPrev(prev1);
}
// Check if the head needs to be updated
// if (head == firstSwitch) {
// head = updatedFirst;
// } else if (head == secondSwitch) {
// head = updatedSecond;
// }
}
此外,如果第一个节点被替换,您将必须更新列表的
head
。最后四行注释掉了。
交换两个节点的最简单方法是仅交换元素。这样你就不需要打扰其他链接了。
private void switchSpace(Node<E> firstSwitch, Node<E> secondSwitch){
// Swap the elements
E temp = firstSwitch.getElement();
firstSwitch.setElement(secondSwitch.getElement());
secondSwitch.setElement(temp);
}
希望这有帮助。