什么是双向链表 - Java？

Question

我目前正在使用Java学习算法，刚刚开始学习java双向链表算法。我部分理解了它背后的概念，但是我完全理解了单链表。在单链表中，linkedList 类将始终记住列表中最后一个链接，而最后一个链接之前的所有其他链接将依次记住其先前链接的引用。据我了解，双重列表在这里所做的是它们记住列表的下一个和上一个链接。但到了实施的时候就很难理解了。例如，当我考虑如何为尾部或头部添加新链接时，我完全感到困惑。任何人都可以解释一下双向链表实际上是什么。如果那么您可以提供示例代码吗？

Answer 1

一排孩子，每个孩子一只手放在前面孩子的肩膀上，这是一个链表。每个孩子都知道他们前面的孩子，但不知道他们后面的孩子。在 Java 中，列表中的每个元素都有一个成员，用于引用下一个元素。

孩子们手拉手排成一排，每个人都认识前面的孩子和后面的孩子。所以是一个双向链表。在Java中，每个元素都有两个成员，分别用于引用前面的元素和后面的元素。

---

插入元素涉及更改四个引用。

1. 将前导元素的“回顾”引用设置为指向新元素。

2. 新元素的“向前”引用被设置为指向该前导元素。

3. 并且您更改尾随元素的“前向”引用以指向新元素。

4. 新元素的“回顾”引用被设置为指向该尾随元素。

---

每个元素的内容或有效负载是位于内存中其他位置的对象。每个元素都带有一个指向其有效负载对象的指针。

因此，双向链表只是一系列三重指针（引用）。第一个和最后一个元素的 3 个指针中的一个都设置为 null。