更新删除后的链表索引

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

Updating LinkList index's after remove

问题

我在练习使用链表，并尝试从头开始创建一个移除节点的方法，该方法能够移除链表中的节点并更新我为每个节点关联的索引值。我已经尝试了一些逻辑来处理不同情况，但它们似乎都不正确。每种情况下的节点索引更新也似乎不正确。

链表类的实例变量：

  1. public class LinkedList<E> implements DynamicList<E> {
  2.     LLNode<E> head;
  3.     LLNode<E> tail;
  4.     int llSize;
  6.     LinkedList(){
  7.         this.head = null;
  8.         this.tail = null;
  9.         this.llSize = 0;
  10.     }
  11. }

节点类：

  1. public class LLNode<E> {
  2.     E obj;
  3.     LLNode<E> previousPointer;
  4.     LLNode<E> nextPointer;
  5.     int index;
  7.     public LLNode(E obj){
  8.         this.obj = obj;
  9.         this.index = 0;
  10.     }
  12.     // 省略了其他方法和getter/setter
  13. }

移除方法：

  1. @Override
  2. public E remove(E data) {
  3.     LLNode<E> nodeToRemove = new LLNode<>(data);
  5.     if(head == null){
  6.         return null;
  7.     }
  9.     if(head.getObj().equals(nodeToRemove.getObj())){
  10.         head = nodeToRemove.nextPointer;
  12.         // 不确定这段代码是否有效....
  13.         LLNode<E> currentNode = this.head;
  14.         for(int i = 0; i < size() - 2; i++){
  15.             currentNode.setIndex(i);
  16.             currentNode = currentNode.nextPointer;
  17.         }
  19.         return nodeToRemove.getObj();
  20.     }
  22.     if(nodeToRemove.nextPointer != null){
  23.         nodeToRemove.nextPointer.previousPointer = nodeToRemove.previousPointer;
  25.         LLNode<E> currentNode = nodeToRemove;
  27.         int startIndex = size() - countFrom(nodeToRemove);
  28.         for(int i = 0; i < countFrom(nodeToRemove); i++){
  29.             currentNode.setIndex(startIndex);
  30.             startIndex++;
  31.             currentNode = currentNode.nextPointer;
  32.         }
  34.         return nodeToRemove.getObj();
  35.     }
  37.     if(nodeToRemove.previousPointer != null){
  38.         nodeToRemove.previousPointer.nextPointer = nodeToRemove.nextPointer;
  40.         LLNode<E> currentNode = nodeToRemove;
  41.         int startIndex = size() - countFrom(nodeToRemove);
  42.         for(int i = 0; i < countFrom(nodeToRemove); i++){
  43.             currentNode.setIndex(startIndex);
  44.             startIndex++;
  45.             currentNode = currentNode.nextPointer;
  46.         }
  47.         
  48.         return nodeToRemove.getObj();
  49.     }
  50.     this.llSize--;
  51.     return null;
  52. }

countFrom方法：

  1. private int countFrom(LLNode<E> startNode){
  2.     int count = 0;
  3.     while(startNode != null){
  4.         startNode = startNode.nextPointer;
  5.         count++;
  6.     }
  8.     return count;
  9. }

如果需要更多的代码，请告诉我。

英文:

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

  2. public class LinkedList&lt;E&gt; implements DynamicList&lt;E&gt; {
  3. LLNode&lt;E&gt; head;
  4. LLNode&lt;E&gt; tail;
  5. int llSize;
  6. LinkedList(){
  7. this.head = null;
  8. this.tail = null;
  9. this.llSize =0;
  10. }

Node class

  1. public class LLNode&lt;E&gt;{
  2. E obj;
  3. LLNode&lt;E&gt; previousPointer;
  4. LLNode&lt;E&gt; nextPointer;
  5. int index;
  6. public LLNode(E obj){
  7. this.obj = obj;
  8. this.index=0;
  9. }
  10. public E getObj() {
  11. return obj;
  12. }
  13. public LLNode&lt;E&gt; getPreviousPointer() {
  14. return previousPointer;
  15. }
  16. public LLNode&lt;E&gt; getNextPointer() {
  17. return nextPointer;
  18. }
  19. public int getIndex() {
  20. return index;
  21. }
  22. public void setIndex(int index) {
  23. this.index = index;
  24. }
  25. }

remove method

  1. @Override
  2. public E remove(E data) {
  3. LLNode&lt;E&gt; nodeToRemove = new LLNode&lt;&gt;(data);
  4. if(head == null){
  5. return null;
  6. }
  7. if(head.getObj().equals(nodeToRemove.getObj())){
  8. head = nodeToRemove.nextPointer;
  9. //not sure if this works....
  10. LLNode&lt;E&gt; currentNode = this.head;
  11. for(int i=0; i &lt; size()-2; i++){
  12. currentNode.setIndex(i);
  13. currentNode = currentNode.nextPointer;
  14. }
  15. return nodeToRemove.getObj();
  16. }
  17. //this is not right
  18. if(nodeToRemove.nextPointer != null){
  19. nodeToRemove.nextPointer.previousPointer = nodeToRemove.previousPointer;
  20. // do I have to update the nodeToRemove&#39;s previous to point to its new next?
  21. LLNode&lt;E&gt; currentNode = nodeToRemove;
  22. int startIndex = size()- countFrom(nodeToRemove);
  23. for(int i = 0; i &lt; countFrom(nodeToRemove); i++){
  24. currentNode.setIndex(startIndex);
  25. startIndex++;
  26. currentNode = currentNode.nextPointer;
  27. }
  28. return nodeToRemove.getObj();
  29. }
  30. if(nodeToRemove.previousPointer != null){
  31. nodeToRemove.previousPointer.nextPointer = nodeToRemove.nextPointer;
  32. //node index updating
  33. LLNode&lt;E&gt; currentNode = nodeToRemove;
  34. int startIndex = size()- countFrom(nodeToRemove);
  35. for(int i = 0; i &lt; countFrom(nodeToRemove); i++){
  36. currentNode.setIndex(startIndex);
  37. startIndex++;
  38. currentNode = currentNode.nextPointer;
  39. }
  40. return nodeToRemove.getObj();
  41. }
  42. this.llSize--;
  43. return null;
  44. }

countFrom method

  1. private int countFrom(LLNode&lt;E&gt; startNode){
  2. int count=0;
  3. while(startNode != null){
  4. startNode = startNode.nextPointer;
  5. count++;
  6. }
  7. return count;
  8. }

Let me know if more code is needed.

答案1

得分: 0

你只需要重新编号在移除节点之后的节点。

所以：

  1. public E remove(E data) {
  2.     LLNode<E> nodeToRemove = new LLNode<>();
  4.     if (head == null) {
  5.         return null;
  6.     }
  8.     // 在必要时调整头部和尾部
  9.     if (tail.getObj().equals(nodeToRemove.getObj())) {
  10.         tail = nodeToRemove.previousPointer;
  11.     }
  12.     if (head.getObj().equals(nodeToRemove.getObj())) {
  13.         head = nodeToRemove.nextPointer;
  14.     }
  16.     // 重连链表，跳过要移除的节点
  17.     if (nodeToRemove.nextPointer != null) {
  18.         nodeToRemove.nextPointer.previousPointer = nodeToRemove.previousPointer;
  19.     }
  20.     if (nodeToRemove.previousPointer != null) {
  21.         nodeToRemove.previousPointer.nextPointer = nodeToRemove.nextPointer;
  22.     }
  24.     // 重新编号在移除节点之后的节点。
  25.     // （之前的节点保留其索引）
  26.     LLNode<E> currentNode = nodeToRemove.nextPointer;
  27.     int index = nodeToRemove.getIndex();
  28.     while (currentNode != null) {
  29.         currentNode.setIndex(index);
  30.         index++;
  31.         currentNode = currentNode.nextPointer;
  32.     }
  34.     this.llSize--;
  35.     return nodeToRemove.getObj();
  36. }
英文:

You should only need to renumber the nodes that follow after the removed node.

So:

  2. public E remove(E data) {
  3. LLNode&lt;E&gt; nodeToRemove = new LLNode&lt;&gt;(data);
  4. if(head == null){
  5. return null;
  6. }
  7. // Adapt head and tail when necessary
  8. if(tail.getObj().equals(nodeToRemove.getObj())){
  9. tail = nodeToRemove.previousPointer;
  10. }
  11. if(head.getObj().equals(nodeToRemove.getObj())){
  12. head = nodeToRemove.nextPointer;
  13. }
  14. // Rewire the list so it skips the node to remove
  15. if(nodeToRemove.nextPointer != null){
  16. nodeToRemove.nextPointer.previousPointer = nodeToRemove.previousPointer;
  17. }
  18. if(nodeToRemove.previousPointer != null){
  19. nodeToRemove.previousPointer.nextPointer = nodeToRemove.nextPointer;
  20. }
  21. // Renumber the nodes that follow the removed node. 
  22. // (Those before it retain their index)
  23. LLNode&lt;E&gt; currentNode = nodeToRemove.nextPointer;
  24. int index = nodeToRemove.getIndex();
  25. while (currentNode != null) {
  26. currentNode.setIndex(index);
  27. index++;
  28. currentNode = currentNode.nextPointer;
  29. }
  30. this.llSize--;
  31. return nodeToRemove.getObj();
  32. }

答案2

得分: 0

  1. 我已经解决了这个问题，现在看起来运行良好，以下是我的更改。
  3. get() 方法
  5. 我添加了一个计数变量，用于与传入的参数进行比较，同时我的 while 循环比较部分之前是检查 current.next 而不是 current，因此出现了空指针。
  7. ```java
  8. public E get(int index) {
  9.     LLNode<E> current = this.head;
  10.     int count = 0;
  12.     while (current != null) {
  13.         if (index == count) {
  14.             return current.getObj();
  15.         }
  16.         current = current.nextPointer;
  17.         count++;
  18.     }
  19.     return null;
  20. }

remove() 方法

我使用了 while 循环替代了之前的逻辑，并且大大简化了逻辑。

  1. @Override
  2. public E remove(E data) {
  3.     LLNode<E> current = this.head;
  4.     while (current != null) {
  5.         if (current.getObj().equals(data)) {
  6.           
  7.             LLNode<E> prev = current.previousPointer;
  8.             LLNode<E> next = current.nextPointer;
  9.             if (prev != null) {
  10.                 prev.nextPointer =  next;
  11.             }
  12.             if (next != null) {
  13.                 next.previousPointer = prev;
  14.             }
  15.             llSize--;
  16.             return current.getObj();
  17.         }
  18.         current = current.nextPointer;
  19.     }
  20.     return null;
  21. }
  2. <details>
  3. <summary>英文:</summary>
  4. I figured it out and this seems to be working well now, here are my changes.
  5. get() Method
  6. 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;

  1.     while(current != null){
  2. if(index == count) {
  3. return current.getObj();
  4. }
  5. current = current.nextPointer;
  6. count++;
  7. }
  8. return null;
  9. }
  2. remove() Method
  3. 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)) {

  1.             LLNode&lt;E&gt; prev = current.previousPointer;
  2. LLNode&lt;E&gt; next = current.nextPointer;
  3. if(prev != null) {
  4. prev.nextPointer =  next;
  5. }
  6. if(next != null) {
  7. next.previousPointer = prev;
  8. }
  9. llSize--;
  10. return current.getObj();
  11. }
  12. current = current.nextPointer;
  13. }
  14. return null;
  15. }
  2. </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:

确定