InsertItem 在索引 0 - DoublyLinkedList

Question

我目前正在创建一个使用尾递归的 DoublyLinkedList。

除了我的插入项目，我已经成功地使我的所有方法完全起作用。

它适用于在除 0 以外的任何索引处插入。我尝试编写一个处理此问题的 if 语句，但我的代码仍然运行，尽管它增加了 noOfItems。它从不将项目添加到我的列表中。

问题可能出在我的 toString 上吗？还是我的 if 案例中遗漏了什么？

这是我的 DLLNode class:

    public class DLLNode
{
    private DLLNode previous;
    public DLLNode next;
    private String value;

    public DLLNode(String value)
    {
        this.value = value;
        this.previous = previous;
        this.next = next;
    }

    public DLLNode(String value, DLLNode next, DLLNode previous)
    {
        this.value = value;
        this.next = next;
        this.previous = previous;
    }

  public String GetDataItem()
  {
    return value;
  }

  public void setDataItem()
  {
      this.value = value;
  }


  public DLLNode GetPreviousNode()
  {
    return previous;
  }

  public void setPrevious(DLLNode previous)
  {
      this.previous = previous;
  }


  public DLLNode GetNextNode()
  {
    return next;
  }

  public void setNextNode(DLLNode next)
  {
      this.next = next;
  }

  public void addItem(String value) {
     if(this.next == null) {
          DLLNode newNode = new DLLNode(value);
          this.next = newNode;
     } else {
          this.next.addItem(value);
     }
}


  public void InsertItemHelper(String value, int indexToInsert, int current, DLLNode currNode)
  {
      if (indexToInsert == 0)
      {
          DLLNode newNode = new DLLNode(value);
          currNode.GetNextNode().setPrevious(newNode);
      }
      else if (current == indexToInsert-1)
      {
          DLLNode newNode = new DLLNode(value); 
          newNode.setNextNode(currNode.GetNextNode());
          currNode.setNextNode(newNode);
          currNode.GetNextNode().setPrevious(newNode);
          newNode.setPrevious(currNode);          
      }
      else
      {
          InsertItemHelper(value, indexToInsert, current+1, currNode.GetNextNode());
      }
  }

    public void DeleteItemHelper(int indexToDelete, int current, DLLNode currNode)
  {
      if (current == indexToDelete-1)
      {
          currNode.setNextNode(currNode.GetNextNode().GetNextNode());
      }
      else
      {
          DeleteItemHelper(indexToDelete, current+1, currNode.GetNextNode());
      }
  }

}

这是我的 DoublyLinkedList class:

    public class DoublyLinkedList
{
    private int noOfItems;
    private DLLNode head;
    private DLLNode tail;
  // Default constructor
  public DoublyLinkedList()
  {
     head = null;
     tail = null;
     this.noOfItems = 0;

  }

  public int GetNoOfItems()
  {
    return noOfItems;
  }

  public String GetItemByIndex(int index)
  {
    int count = 0;
    while (count < index)
    {
        head = head.GetNextNode();
        count++;
    }
    return head.GetDataItem();

  }

  public DLLNode GetNodeByIndex(int index)
  {
      int count = 0;
    while (count < index)
    {
        head = head.GetNextNode();
        count++;
    }
    return head;
  }

  public void AddItem(String value)
  {
      if (head == null)
      {
          DLLNode newNode = new DLLNode(value);
          head = newNode;
          noOfItems++;
      }
      else
      {
      head.addItem(value);
      noOfItems++;
      }
       }



  public void InsertItem(int index, String value)
  {
      if (index > noOfItems)
      {
          AddItem(value);
      }
      else {
        head.InsertItemHelper(value, index, 0, head); 
        noOfItems++;
      }


  }

  public void DeleteItem(int index)
  {

          if (index ==0)
          {
              System.out.println("Out of Bounds");
          }
          if (index > noOfItems)
          {
             System.out.println("Out of Bounds");
          }
          if (head == null)
          {
              System.out.println("No Item to remove");
          }
          else if (index == 1)
          {
              head = head.GetNextNode();
              noOfItems--;
          }
          else
          {
              head.DeleteItemHelper(index, 0, head);
              noOfItems--;
          }

  }

  public int getNoOfItems()
  {
      return this.noOfItems;
  }

  public boolean isEmpty()
  {
      return (head == null);
  }




  public String toString()
  {
    DLLNode currentNode = head;
    StringBuilder sb = new StringBuilder();
    while (currentNode != null) {
        sb.append(currentNode.GetDataItem());

        if (currentNode.GetNextNode() != null)
        {
            sb.append(",");
        }
        currentNode = currentNode.GetNextNode();
    }
        return sb.toString();
    }

}

我已将以下代码添加到我的插入项中：

   if (index ==0)
  {
      DLLNode newNode = new DLLNode(value);
      head.setNextNode(head);
     // newNode.next= head.GetNextNode();
      head = newNode;
      noOfItems++;
  }

如果我包含注释掉的行，我会收到与字符串生成器有关的错误。

将注释掉的行添加到链接列表中的位置 0，但不添加任何其余部分。但是它确实会正确增加 noOfItems。

出现以下错误：

线程 "main" java.lang.OutOfMemoryError 异常：Java 堆 space 在 java.util.Arrays.copyOf(Arrays.java:2367) 在 java.lang.AbstractStringBuilder.expandCapacity(AbstractStringBuilder.java:130) 在 java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:114) 在 java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:415) 在 java.lang.StringBuilder.append(StringBuilder.java:132) 在 ads2.DoublyLinkedList.toString(DoublyLinkedList.java:155) 在 java.lang.String.valueOf(String.java:2847) 在 java.lang.StringBuilder.append(StringBuilder.java:128) 在 ads2.Main.printList(Main.java:62) 在 ads2.Main.main(Main.java:38) Java 结果：1 构建成功（总时间：1 秒）

如果您需要有关该错误的更多详细信息，请告诉我。

Answer 1

在位置 0 添加时需要更新头部

因为你没有更新head，旧的head还在list对象中链接，而next() returns新的list对象index 1应该是什么，所以你结束了使用相同的列表

您可以通过确认

来确认这一点

list.getNodeByIndex(0) != list.getNodeByIndex(1).previousNode();

InsertItem 在索引 0 - DoublyLinkedList

InsertItem at Index 0 - DoublyLinkedList

java

algorithm

doubly-linked-list