java - Java 中的自定义 LinkedList 具有维护的插入顺序

Question

我试图用Java实现一个链表。我想出了以下简单的实现

public class Node{
  public String data;
  public Node next;
  public Node(String data){
     this.data = data  
  }
}

public class LinkedLst{
  public Node currentNode;

  public void add(String data){
    Node newNode = new Node(data);
    newNode.next = currentNode;
    currentNode = newNode;
  }
  public Node remove(){
    Node temp = currentNode;
    currentNode = currentNode.next;
    return temp;
  }
  public void printList(){
    Node temp = currentNode;
    while(temp!=null){
      System.out.println(temp.data + ",");
      temp = temp.next;
    }
  }
}

但我在这里看到的一个明显问题是，由于我的设计缺陷，插入顺序被颠倒了。但在 LinkedList 中，应该保持插入的顺序。我将如何更改此代码来做到这一点。我现在无法从不同的角度思考。

Answer 1

尝试一次一步地分析问题。

假设您想要将以下数字序列添加到列表中 - 1、2、3、4、5。到底会发生什么？

LinkedList 类的对象中只有一个字段 (currentNode)。让我们尝试像这样可视化它；

LinkedList
  currentNode = null

此时，列表中没有任何数据。现在让我们插入第一个节点(我分配字母来表示它们)。

LinkedList
  currentNode = A

列表序列本身看起来像这样；

null <- A(value = 1)

现在让我们将第二个数据添加到列表中。注意发生了什么；

LinkedList
  currentNode = B

列表序列变为；

null <- A(value = 1) <- B(value = 2)

再加上一些元素，你就会遇到这种情况

LinkedList
  currentNode = E

序列为；

null <- A(value = 1) <- B(value = 2) <- C(value = 3) <- D(value = 4) <- E(value = 5)

在这种情况下，您可以遍历列表的唯一顺序是什么？相反。为什么？因为您只存储列表的最后一个(或尾部)节点。如果您想检索原始顺序，则需要更改逻辑，以便存储列表的头部而不是尾部。首先，我们将类中的字段重命名如下；

public class LinkedList {
    public Node HEAD;
}

我们需要解决的下一个更改是 add() 方法。考虑最终目标。您想如何在列表中存储内容？我怀疑这就是您要找的；

A(value = 1) -> B(value = 2) -> C(value = 3) -> D(value = 4) -> E(value = 5) -> null

如果您有上面列表中的第一个元素 (HEAD = A)，您将如何向列表中添加新元素？您需要遍历列表，直到到达最后一个节点并在那里插入新值。所以你的函数将变成；

public void add(String data) {
    Node newNode = new Node(data);
    // check if HEAD is empty or not
    if (HEAD == null) {
        HEAD = newNode;
        return;
    }
    Node temp = HEAD;
    while(temp.next != null) {
        temp = temp.next;
    }
    // we must be at the end of the list now.
    // add the next element in here.
    temp.next = newNode;
}

要验证这一点，需要对打印函数进行一些小更改(使用 HEAD 而不是 currentNode)。最终的类(class)看起来像这样；

public class LinkedList {
    public Node HEAD;

    public void add(String data) {
        Node newNode = new Node(data);
        // check if HEAD is empty or not
        if (HEAD == null) {
            HEAD = newNode;
            return;
        }
        Node temp = HEAD;
        while(temp.next != null) {
            temp = temp.next;
        }
        // we must be at the end of the list now.
        // add the next element in here.
        temp.next = newNode;
    }

    public void printList() {
        Node temp = HEAD;
        while(temp != null) {
            System.out.print(temp.data + " -> " );
            temp = temp.next;
        }
    }
}

就remove() 方法而言...我将把它留给您作为练习。不能就这样放弃一切吧？ ;)