c++ - node.prev.next =…和node =之间的区别

Question

对于所示的代码，区别到底是什么。根据我的理解，它应该返回current.data值，并将current的指针更改为current.next。另外，任何人都可以解释current.prev.next = ...和current = ...的复杂性吗？ DoubleLinkedLists，仍然让我有些困惑。谢谢!

public T next() {
    if (!hasNext()){
        throw new NoSuchElementException();
    }
    T data = current.data;
    current = current.next;
    return data;
}

与

public T next() {
    if(!hasNext()) {
        throw new NoSuchElementException();
    }
    current = current.next;
    return current.prev.data;
}

Answer 1

TL; DR 〜

如果您有一个双向链接列表和，则该节点既有先前的node又有next节点。说node->previous->next确实会使您回到起点。但是，如果您位于列表的开头或结尾，则代码将崩溃(因为它正在尝试NULL->next)。所以不要那样做。

好吧，让我们暂时忽略一下数据结构。

想象一个“节点”是一个穿着T恤的人。整个T恤上都写着他们的名字(数据)。

在第一种情况下，人们排成一列，所有人都面对着相同的方向，而后面的人则伸了伸胳膊，指着前面的人。如果要查找“Joe”，则可以查看当前人员是否为“Joe”，以及是否要检查另一个人(“Joe”指向的人，或者他是最后一个人)。

这是一个单链接列表。每个人只知道自己，而下一个人知道。每个人只能“看见”前面的人，而不是后面的人。要找出一个人的名字，您必须问这个人自己或指着他们的人。也就是说，询问node.data或node->next.data。您可以向此人询问下一个谁，而不是前一个。他们不知道以前是谁。

现在想象一下人们在一条直线上，指向两边的两个人。这是一个双向链接列表。每个人都指向前一个人和下一个人。任何给定的人都可以告诉您他们的名字，以及他们所指向的人的名字。也可以沿人员列表在两个方向上移动，因为他们可以告诉您在两个方向上指向谁。

这给了我们一些代码:

structure NodeSingle
{
    String       name;
    NodeSingle   next;
}

和

structure NodeDouble
{
    String       name;
    NodeDouble   previous;
    NodeDouble   next;
}

因此，我们从一个空(单链接)列表开始。

随之而来的是“鲍勃”。 Bob没有人要指向(没有下一个，也没有上一个)，因此在数据方面，我们得到["Bob", <>]。

然后是“莎莉”。无论出于何种原因，我们都希望列表按字母顺序排序。因此，我们看了鲍勃，并决定萨莉需要下一个。因此，我们将鲍勃指向萨利。 ["Bob", <Sally>]和["Sally", <>]。

然后是“恩斯特”，他必须在鲍勃和萨莉之间走:["Bob", <Ernst>] ["Ernst",<Sally>] ["Sally", <>]
用编程术语来说，这就是node->next的使用位置。当我们添加“Sally”时，我们可以说["Bob"]->next = new NodeSingle("Sally")。

如果[Sally]必须介于[Bob]和[Tina]之间，那么显然["Bob"]->next = new NodeSingle("Sally", <Tina>)
双向链表几乎相同，除了前面的指针也要注意。

因此，在编程时，可以引用节点:node->next->next ...等。如果定义了next和prev(如果很大)，则可以沿链移动。

想象一个简单的搜索功能:

// Return the node with name = <for_this_name> or NULL
NodeSingle *find(NodeSingle *list, String for_this_name)
{
    while (list != NULL && list->name != for_this_name)
        list = list->next;  // skip to next node
    return list; 
}