英文:
Updating LinkList index's after remove
问题
我在练习使用链表,并尝试从头开始创建一个移除节点的方法,该方法能够移除链表中的节点并更新我为每个节点关联的索引值。我已经尝试了一些逻辑来处理不同情况,但它们似乎都不正确。每种情况下的节点索引更新也似乎不正确。
链表类的实例变量:
public class LinkedList<E> implements DynamicList<E> {
LLNode<E> head;
LLNode<E> tail;
int llSize;
LinkedList(){
this.head = null;
this.tail = null;
this.llSize = 0;
}
}
节点类:
public class LLNode<E> {
E obj;
LLNode<E> previousPointer;
LLNode<E> nextPointer;
int index;
public LLNode(E obj){
this.obj = obj;
this.index = 0;
}
// 省略了其他方法和getter/setter
}
移除方法:
@Override
public E remove(E data) {
LLNode<E> nodeToRemove = new LLNode<>(data);
if(head == null){
return null;
}
if(head.getObj().equals(nodeToRemove.getObj())){
head = nodeToRemove.nextPointer;
// 不确定这段代码是否有效....
LLNode<E> currentNode = this.head;
for(int i = 0; i < size() - 2; i++){
currentNode.setIndex(i);
currentNode = currentNode.nextPointer;
}
return nodeToRemove.getObj();
}
if(nodeToRemove.nextPointer != null){
nodeToRemove.nextPointer.previousPointer = nodeToRemove.previousPointer;
LLNode<E> currentNode = nodeToRemove;
int startIndex = size() - countFrom(nodeToRemove);
for(int i = 0; i < countFrom(nodeToRemove); i++){
currentNode.setIndex(startIndex);
startIndex++;
currentNode = currentNode.nextPointer;
}
return nodeToRemove.getObj();
}
if(nodeToRemove.previousPointer != null){
nodeToRemove.previousPointer.nextPointer = nodeToRemove.nextPointer;
LLNode<E> currentNode = nodeToRemove;
int startIndex = size() - countFrom(nodeToRemove);
for(int i = 0; i < countFrom(nodeToRemove); i++){
currentNode.setIndex(startIndex);
startIndex++;
currentNode = currentNode.nextPointer;
}
return nodeToRemove.getObj();
}
this.llSize--;
return null;
}
countFrom方法:
private int countFrom(LLNode<E> startNode){
int count = 0;
while(startNode != null){
startNode = startNode.nextPointer;
count++;
}
return count;
}
如果需要更多的代码,请告诉我。
英文:
I'm practicing with LinkLists and trying to make a remove method from scratch that removes the node in the linked list and also updates index values that I have associated with each node. I have tried some logic for different cases but they don't seem right. The node index updating for each case doesn't seem right either.
LinkedList Class instance variables
public class LinkedList<E> implements DynamicList<E> {
LLNode<E> head;
LLNode<E> tail;
int llSize;
LinkedList(){
this.head = null;
this.tail = null;
this.llSize =0;
}
Node class
public class LLNode<E>{
E obj;
LLNode<E> previousPointer;
LLNode<E> nextPointer;
int index;
public LLNode(E obj){
this.obj = obj;
this.index=0;
}
public E getObj() {
return obj;
}
public LLNode<E> getPreviousPointer() {
return previousPointer;
}
public LLNode<E> getNextPointer() {
return nextPointer;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
}
remove method
@Override
public E remove(E data) {
LLNode<E> nodeToRemove = new LLNode<>(data);
if(head == null){
return null;
}
if(head.getObj().equals(nodeToRemove.getObj())){
head = nodeToRemove.nextPointer;
//not sure if this works....
LLNode<E> currentNode = this.head;
for(int i=0; i < size()-2; i++){
currentNode.setIndex(i);
currentNode = currentNode.nextPointer;
}
return nodeToRemove.getObj();
}
//this is not right
if(nodeToRemove.nextPointer != null){
nodeToRemove.nextPointer.previousPointer = nodeToRemove.previousPointer;
// do I have to update the nodeToRemove's previous to point to its new next?
LLNode<E> currentNode = nodeToRemove;
int startIndex = size()- countFrom(nodeToRemove);
for(int i = 0; i < countFrom(nodeToRemove); i++){
currentNode.setIndex(startIndex);
startIndex++;
currentNode = currentNode.nextPointer;
}
return nodeToRemove.getObj();
}
if(nodeToRemove.previousPointer != null){
nodeToRemove.previousPointer.nextPointer = nodeToRemove.nextPointer;
//node index updating
LLNode<E> currentNode = nodeToRemove;
int startIndex = size()- countFrom(nodeToRemove);
for(int i = 0; i < countFrom(nodeToRemove); i++){
currentNode.setIndex(startIndex);
startIndex++;
currentNode = currentNode.nextPointer;
}
return nodeToRemove.getObj();
}
this.llSize--;
return null;
}
countFrom method
private int countFrom(LLNode<E> startNode){
int count=0;
while(startNode != null){
startNode = startNode.nextPointer;
count++;
}
return count;
}
Let me know if more code is needed.
答案1
得分: 0
你只需要重新编号在移除节点之后的节点。
所以:
public E remove(E data) {
LLNode<E> nodeToRemove = new LLNode<>();
if (head == null) {
return null;
}
// 在必要时调整头部和尾部
if (tail.getObj().equals(nodeToRemove.getObj())) {
tail = nodeToRemove.previousPointer;
}
if (head.getObj().equals(nodeToRemove.getObj())) {
head = nodeToRemove.nextPointer;
}
// 重连链表,跳过要移除的节点
if (nodeToRemove.nextPointer != null) {
nodeToRemove.nextPointer.previousPointer = nodeToRemove.previousPointer;
}
if (nodeToRemove.previousPointer != null) {
nodeToRemove.previousPointer.nextPointer = nodeToRemove.nextPointer;
}
// 重新编号在移除节点之后的节点。
// (之前的节点保留其索引)
LLNode<E> currentNode = nodeToRemove.nextPointer;
int index = nodeToRemove.getIndex();
while (currentNode != null) {
currentNode.setIndex(index);
index++;
currentNode = currentNode.nextPointer;
}
this.llSize--;
return nodeToRemove.getObj();
}
英文:
You should only need to renumber the nodes that follow after the removed node.
So:
public E remove(E data) {
LLNode<E> nodeToRemove = new LLNode<>(data);
if(head == null){
return null;
}
// Adapt head and tail when necessary
if(tail.getObj().equals(nodeToRemove.getObj())){
tail = nodeToRemove.previousPointer;
}
if(head.getObj().equals(nodeToRemove.getObj())){
head = nodeToRemove.nextPointer;
}
// Rewire the list so it skips the node to remove
if(nodeToRemove.nextPointer != null){
nodeToRemove.nextPointer.previousPointer = nodeToRemove.previousPointer;
}
if(nodeToRemove.previousPointer != null){
nodeToRemove.previousPointer.nextPointer = nodeToRemove.nextPointer;
}
// Renumber the nodes that follow the removed node.
// (Those before it retain their index)
LLNode<E> currentNode = nodeToRemove.nextPointer;
int index = nodeToRemove.getIndex();
while (currentNode != null) {
currentNode.setIndex(index);
index++;
currentNode = currentNode.nextPointer;
}
this.llSize--;
return nodeToRemove.getObj();
}
答案2
得分: 0
我已经解决了这个问题,现在看起来运行良好,以下是我的更改。
get() 方法
我添加了一个计数变量,用于与传入的参数进行比较,同时我的 while 循环比较部分之前是检查 current.next 而不是 current,因此出现了空指针。
```java
public E get(int index) {
LLNode<E> current = this.head;
int count = 0;
while (current != null) {
if (index == count) {
return current.getObj();
}
current = current.nextPointer;
count++;
}
return null;
}
remove() 方法
我使用了 while 循环替代了之前的逻辑,并且大大简化了逻辑。
@Override
public E remove(E data) {
LLNode<E> current = this.head;
while (current != null) {
if (current.getObj().equals(data)) {
LLNode<E> prev = current.previousPointer;
LLNode<E> next = current.nextPointer;
if (prev != null) {
prev.nextPointer = next;
}
if (next != null) {
next.previousPointer = prev;
}
llSize--;
return current.getObj();
}
current = current.nextPointer;
}
return null;
}
<details>
<summary>英文:</summary>
I figured it out and this seems to be working well now, here are my changes.
get() Method
Added a count variable to compare with the passed parameter also my while comparison was checking current.next and not current and was getting null pointer.
public E get(int index) {
LLNode<E> current = this.head;
int count = 0;
while(current != null){
if(index == count) {
return current.getObj();
}
current = current.nextPointer;
count++;
}
return null;
}
remove() Method
I used a while instead of the previous logic. and simplified the logic quite a bit.
@Override
public E remove(E data) {
LLNode<E> current = this.head;
while(current != null){
if(current.getObj().equals(data)) {
LLNode<E> prev = current.previousPointer;
LLNode<E> next = current.nextPointer;
if(prev != null) {
prev.nextPointer = next;
}
if(next != null) {
next.previousPointer = prev;
}
llSize--;
return current.getObj();
}
current = current.nextPointer;
}
return null;
}
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论