更新删除后的链表索引

huangapple
go评论73阅读模式
英文:

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&lt;E&gt; implements DynamicList&lt;E&gt; {
LLNode&lt;E&gt; head;
LLNode&lt;E&gt; tail;
int llSize;
LinkedList(){
this.head = null;
this.tail = null;
this.llSize =0;
}

Node class

public class LLNode&lt;E&gt;{
E obj;
LLNode&lt;E&gt; previousPointer;
LLNode&lt;E&gt; nextPointer;
int index;
public LLNode(E obj){
this.obj = obj;
this.index=0;
}
public E getObj() {
return obj;
}
public LLNode&lt;E&gt; getPreviousPointer() {
return previousPointer;
}
public LLNode&lt;E&gt; 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&lt;E&gt; nodeToRemove = new LLNode&lt;&gt;(data);
if(head == null){
return null;
}
if(head.getObj().equals(nodeToRemove.getObj())){
head = nodeToRemove.nextPointer;
//not sure if this works....
LLNode&lt;E&gt; currentNode = this.head;
for(int i=0; i &lt; 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&#39;s previous to point to its new next?
LLNode&lt;E&gt; currentNode = nodeToRemove;
int startIndex = size()- countFrom(nodeToRemove);
for(int i = 0; i &lt; 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&lt;E&gt; currentNode = nodeToRemove;
int startIndex = size()- countFrom(nodeToRemove);
for(int i = 0; i &lt; countFrom(nodeToRemove); i++){
currentNode.setIndex(startIndex);
startIndex++;
currentNode = currentNode.nextPointer;
}
return nodeToRemove.getObj();
}
this.llSize--;
return null;
}

countFrom method

private int countFrom(LLNode&lt;E&gt; 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&lt;E&gt; nodeToRemove = new LLNode&lt;&gt;(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&lt;E&gt; 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&lt;E&gt; prev = current.previousPointer;
LLNode&lt;E&gt; 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>

huangapple
  • 本文由 发表于 2020年10月21日 04:05:17
  • 转载请务必保留本文链接：https://go.coder-hub.com/64452585.html
  • java
  • linked-list
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定