Java中的双向链表问题
双向链表（Doubly Linked List）是一种常见的数据结构，它由一系列节点组成，每个节点包含指向前一个节点和后一个节点的指针。与单向链表不同，双向链表可以在任意节点处进行双向遍历。
双向链表的优势在于可以快速地在任意位置插入或删除节点，而无需像数组那样进行元素的移动。它还可以支持双向遍历，使得在某些场景下的操作更加方便。
双向链表在Java中可以通过自定义类来实现。以下是一个简单的双向链表的Java实现示例：
class Node {
int data;
Node prev;
Node next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
Node head;
public DoublyLinkedList() {
this.head = null;
}
// 在链表头部插入节点
public void insertAtHead(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
}
// 在链表尾部插入节点
public void insertAtTail(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}
}
// 在指定位置插入节点
public void insertAtPosition(int data, int position) {
if (position <= 0) {
insertAtHead(data);
} else {
Node newNode = new Node(data);
Node current = head;
int currentPosition = 0;
while (current != null && currentPosition < position) {
current = current.next;
currentPosition++;
}
if (current != null) {
newNode.next = current;
newNode.prev = current.prev;
current.prev.next = newNode;
current.prev = newNode;
} else {
insertAtTail(data);
}
}
}
// 删除指定位置的节点
public void deleteAtPosition(int position) {
if (head == null) {
return;
}
if (position <= 0) {
head = head.next;
head.prev = null;
} else {
Node current = head;
int currentPosition = 0;
while (current != null && currentPosition < position) {
current = current.next;
currentPosition++;
}
if (current != null) {
current.prev.next = current.next;
if (current.next != null) {
current.next.prev = current.prev;
}
}
}
}
// 打印链表
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}这是一个简单的双向链表的实现，包括在链表头部插入节点、在链表尾部插入节点、在指定位置插入节点、删除指定位置的节点以及打印链表的功能。
双向链表在实际开发中有许多应用场景，例如：
- 编辑器中的撤销和重做功能：双向链表可以用于保存操作历史，支持撤销和重做操作。
- LRU缓存淘汰算法：双向链表可以用于实现LRU缓存淘汰算法，将最近使用的数据放在链表头部，当缓存满时，淘汰链表尾部的数据。
- 浏览器的前进和后退功能：双向链表可以用于保存浏览器的访问历史，支持前进和后退操作。
腾讯云提供了多种云计算相关产品，其中与双向链表相关的产品可能没有直接的对应关系。然而，腾讯云提供了强大的计算、存储和数据库等基础设施服务，可以支持开发者构建和部署各种应用程序。您可以参考腾讯云的官方文档和产品介绍页面，了解更多关于腾讯云的产品和服务：
相关·内容
1回答
我看到LinkedList的JDK实现内部包含Node内部类，其中包含指向下一个和上一个的地址。
所以我的疑问不是LinkedList在java中是一个双向链表。若否，原因为何？
如何实现我们自己的双向链表？
浏览 1提问于2015-07-12得票数 34
回答已采纳
1回答
我想用java.util库不包含的函数实现一个单链表，比如:返回链表中的中间节点，并在链表中插入一个新的头。我的问题是: java.util链表是什么类型的链表(例如，单次、双次)？其次，我想知道您是否建议我从头开始实现链表。我关心的是能够在没有第三方库的情况下维护我自己的代码(因为依赖)，并且能够对其进行自定义。我还想实现合并排序，我觉得有一个中间节点方法很重要。谢谢！！
浏览 11提问于2020-11-18得票数 0
2回答
对于一个处理访问控制列表的赋值，它需要首先构造一个双向链表，因为Java在SUN API中没有包含这个链表。我可以理解如果教授想让我们从头开始创建双向链表，以了解它是如何工作的(就像编写排序程序与使用baked in方法)，但为什么要将它排除在库之外？
这让我开始思考，是什么决定了数据结构是否包含在basic语言库中？例如，在Java中，为什么有LinkedList类而没有DoublyLinkedList？
浏览 1提问于2010-01-04得票数 2
回答已采纳
1回答
我主要接受过Java方面的培训，所以这对我来说从来都不是问题，但我正在尝试为我正在处理的一份智能合同创建一个可靠的链表。在其中，我使用了一个这样编写的结构：
struct Node {
address addr;
Node _next;
Node prev;
}
虽然我仍在研究是否值得将其作为单链表或双链表，但主要问题是我在Node结构中引用Node结构时遇到了递归结构定义问题。我有点不确定我的替代方案是什么。这仅仅是语言的一个限制吗？我读了，但我真的不知道给出的答案是否比“视情况而定”更多。
感谢您的反馈；如果我能提供更多信息，请告诉我。
浏览 4提问于2017-10-23得票数 0
6回答
在Java中，我被要求将整数值存储在一个单向链表中，然后打印存储在该列表中的元素。这是我想出来的：
int max = 10;
List<Integer> list = new ArrayList<Integer>();
for (int num = 0; i < max; i++){
list.add(num);
}
System.out.print(list);
我想知道，ArrayList和单链表是一回事吗？我想确保我正确地回答了这个问题。这有意义吗？谢谢!
浏览 0提问于2012-12-13得票数 6
回答已采纳
2回答
嗨，我是数据结构方面的新手。我需要一个代码来理解java中循环链表中节点的添加和删除。如果你上传一些图片来演示会更好。
浏览 0提问于2011-05-23得票数 0
回答已采纳
3回答
根据我的理解，java中的链表实现是基于双端链表，而不是双向链表(因为我们没有任何方法可以向后返回)。虽然我可以看到descendingIterator方法，它会把我们带回过去。不确定我们应该称它为双向链表实现吗？
浏览 0提问于2011-08-06得票数 1
回答已采纳
8回答
在今天的一次面试中，我被问到这个问题。
除了回答、颠倒列表和向前和向后遍历之外，面试官还不断强调其中有一些“基本”的东西。我放弃了，当然在面试后做了一些研究。在双向链表中插入和删除似乎比单链表更有效。我不太确定如何才能更有效地使用双向链表，因为很明显需要更改更多的引用。有人能解释一下背后的秘密吗？老实说，我做了相当多的研究，但未能理解我的主要问题是，双向链表仍然需要O(n)搜索。
浏览 0提问于2013-03-22得票数 51
回答已采纳
4回答
双向链表实现
、、
我已经看了这里关于双向链表的大多数帖子，但仍然不清楚下面的内容。
我正在用Java练习Goodrich和Tamassia这本书。关于双向链表，如果我错了，请纠正我，它与单链表的不同之处在于，节点可以插入到任何地方，而不仅仅是在头部之后或尾部之后，使用next和prev节点，而在单链表中，在列表中的任何地方插入都是不可能的？
如果要在双向链表中插入节点，则默认参数应该是要插入的节点之后的节点或要插入的节点之前的节点？但如果是这样，那么我不知道如何在之前或之后传递节点。我们是否应该显示到目前为止已插入的所有节点，并要求用户选择要插入某个新节点之前或之后的节点？我的疑问是如何传递这个默认节点。因为我
浏览 1提问于2011-01-05得票数 1
回答已采纳
根据定义，链表是一个列表，它的每个元素都指向下一个元素(如果我们谈论的是双向链表，也可以是前一个元素) 。
然而，在Java语言中，LinkedList实现了List、Queue、Deque等等。
在LinkedList中找不到提供列表中下一个或上一个对象的方法，最好的方法是获取迭代器和对象。我的问题是，为什么Java将这种数据结构称为LinkedList，而它并不是真正的链表？链表可以在Java中实现，如下所示：
Public class MyLinkedList{
public int value;
public MyLinkedList next;
}
浏览 1提问于2013-02-12得票数 10
回答已采纳
在我的考试中，有一个类似这样的问题，我一直在想，用C编写销毁双链表和单链表的销毁算法有什么不同？
浏览 2提问于2020-05-01得票数 0
假设我有一个带有sentinel的单链表。要在O(1)时间内删除最后一个元素，我需要维护最后2个元素的句柄。但是维护最后两个元素的句柄会使add操作变得复杂。
有没有一种方法可以在不保留最后两个元素的句柄的情况下删除O(1)中带有标记的单链表的最后一个元素？我非常感谢任何用java编写的示例代码。
谢谢。
浏览 4提问于2012-07-08得票数 1
回答已采纳
2回答
假设我在一个程序中构建了一个链表，然后在另一个程序中我必须访问它。我该怎么做呢？
我试图在一个程序中使用Java中的全局链表数据结构，但在另一个程序中似乎无法访问它。我猜在下一个程序中无法获得对链表的引用。
我该如何解决这个问题？
浏览 0提问于2012-06-26得票数 2
2回答
注意:这并不是特定于Java/C/C++的，但是链表就像它们一样常见，我选择在这些语言和双向链表下标记它。如果这是错误的，我可以改变它！
假设你有一个标准的双向链表实现：
struct List {
int Number;
struct List *blink;
struct List *flink;
};
你有下面的列表：
1 <--> 2 <--> 3 <--> 4 <--> 5
现在，在我的例子中，我一直使用flink作为某种终结器，并在一个方向上取消节点的链接：
1 <--> 2 <-->
浏览 0提问于2014-11-18得票数 1
我正在编写一个包含一些有用函数的脚本来编辑双向链表，并且我没有使用OOP。所以没有使用任何类。
下面是一个双向链表的示例：
dll = ['So true', ['^very much', ['try it', ['Not yet', None, [...]], [...]], [...]], None]
注意，ddl元素的结构类似于:字符串，指向上一个节点的指针，指向下一个节点的指针
我正在尝试创建一个变量，它将双向链表中字符'^'的值作为“游标”(只是一个虚拟游标，但它实际上只是'^'字符的索引
浏览 1提问于2018-11-10得票数 1
在我的Java项目中，我有一个用于双向链表的class，它可以很好地将输出放到控制台窗口中，但我想知道如何将输出放到我创建的另一个JFrame的JList中？干杯
浏览 0提问于2020-04-25得票数 1
1回答
我正在编写一个二进制搜索树实现，我希望有一个函数来查找节点，并返回路径中所有节点的双向链表。我知道双向链表可以转换成二叉树，所以能够使用相同的类将会很好(也很酷)。 但是，如果我对沿途的所有节点进行浅层复制，并开始更改它们的指针来构建我想要返回的二进制搜索树，那么我显然会破坏原始的树。我不能只制作所有节点的深度副本，因为我需要对原始节点的引用，我将使用它来更改原始树(可以是删除、平衡等)。 例如，我可能有一个调用find的add函数，它将路径中的最后一个节点返回到新节点要去的位置，我可以简单地将它作为其中的一个子节点。如果我正在编写一个自平衡的二叉树类(Red/Black Tree，AVL
浏览 15提问于2020-03-20得票数 0
回答已采纳
我被问到这样的问题，我有自己的说法，但我真的不确定该怎么说利弊？微软向其中一位候选人提出了这个问题。
单链表允许您单向访问。而双向链表具有next和previous双向。
这是一张很好的图片，画出了单色和双色的LinkedLists。
然而，如何以更有序的方式解释这些项目的优缺点？
浏览 8提问于2012-05-23得票数 22
回答已采纳
3回答
克隆单链表
、、
我有一个单链表。除了正常的"Next“指针之外，每个节点中还有一个指针(随机ptr)，它指向列表中的某个随机节点。如何创建这样一个列表的克隆？(小于O(n^2))。
使用Java有什么建议或解决方案吗？
浏览 1提问于2012-07-29得票数 3
回答已采纳
1回答
我正在用Java实现一个链表。是否可以在list集合类中创建、创建和使用实例变量"lastNode“？或者我应该总是通过从第一个节点开始跟随节点的链接来访问最后一个节点？
浏览 3提问于2010-12-20得票数 1
回答已采纳
1回答
我正在尝试用Java语言创建一个通过链表实现的PriorityQueue类。在队列中，具有不同优先级的对象将以不特定的顺序添加到列表的末尾，因此添加一个元素将是O(1)，删除具有最高优先级的元素将是O(n)。但是，我在编写remove方法时遇到了困难。我已经在我的链表类中创建了一个"removeHighestPriorityNode“方法，但是我被卡住了。这就是我到目前为止所知道的：
public void removeHighestPriorityNode()
{
if(head == null)
{
浏览 1提问于2012-04-12得票数 0
回答已采纳
4回答
如何在纯函数式语言中实现双向链表？也就是说，像Haskell这样的东西，你不在Monad中，所以你没有突变。有可能吗？(单链表显然非常简单)。
浏览 1提问于2009-12-04得票数 49
回答已采纳
我有一个包含一些特殊元素的元素列表，我需要在固定时间内找到这些元素的邻居。使用双向链表听起来很简单:只需存储对包含这些特定元素的节点的引用，并检查它们的前一个和下一个节点。(我也喜欢使用链表，因为我经常删除和添加元素。列表很大，性能尤其重要。)
但是，Java的LinkedList似乎不允许我存储包含元素的节点。是那么回事吗？如果是这样的话，有没有一种干净的方法来做我需要做的事情？这应该不难，但我没有找到解决方案。
这需要在列表不断变化的情况下工作，并且我更喜欢在更改期间不必更新任何东西(例如，如果我使用一个数组，那么每当它们在数组中移动时，我就必须不断地更新它们的索引)。此外，将来我可能需要
浏览 1提问于2011-03-25得票数 3
回答已采纳
由于Flex中的ArrayCollection是有限的，我正在寻找一种类似于LinkedHashSet的数据结构在Java中，LinkedHashSet维护着一个遍历其所有条目的双向链表，它定义了迭代顺序，即元素被插入到集合中的顺序(插入顺序).But关于Flex数据结构的信息很少，所以任何人都可以帮助我，谢谢
浏览 0提问于2010-08-17得票数 1
回答已采纳
1-从文本文件中读取单词时出现空行
示例：
output:
catholicate
chymia
sitosterol
Aries
2-我将单词保存在双向链表中，但没有按照双向链表中的字母顺序对其进行排序。
方法，但我没有把保存方法放在双向链表中：
public static void main(String[] args)throws IOException {
Scanner input;
try{
input = new Scanner(new File(""));
String c;
浏览 0提问于2012-11-04得票数 0
2回答
双向链表
、
您好，我想知道如何将对象从arrayList复制到双向链表中？另外，我的DNode构造函数是：
public DNode(Object element, DNode prev, DNode next) {
this.element = element;
this.next = next;
this.prev = prev;
}
也就是说，当我写这样的代码时，我的程序不能工作：
DNode node = new DNode(pointList.get(0),null, null);
for (int i = 1; i < pointLi
浏览 0提问于2010-11-23得票数 1
回答已采纳
3回答
如何在Java中深度复制双向链表
、、、、
我在我的java程序中尝试制作一个双向链表的深度副本时遇到了相当多的麻烦。
到目前为止我的方法是：
公共类DblLinkQueue实现队列{
public Object clone() {
DblLinkQueue copy = null;
Node currNode, tmp = null;
try {
copy = (DblLinkQueue)super.clone();
} catch (CloneNotSupportedException err) {}
for (currNode = mHead.next; currN
浏览 0提问于2011-10-07得票数 0
回答已采纳
4回答
在HashMap的实现中，链表用于表示存储桶中的元素。每个条目都有一个指向下一个条目的元素。请参阅：但是，在LinkedList类的实现中，每个元素都有一个对其前一个元素和下一个元素的引用，请参见。只是想弄清楚为什么previous在一个链表中很重要，而在另一个链表中却不重要？
浏览 1提问于2013-03-29得票数 0
回答已采纳
2回答
我正在向一个非程序员解释基本的数据结构。我解释了数组或列表是一个集合。例如，数组是数字、名称或事物的集合:一个铅笔盒，里面有许多铅笔。
在解释了列表之后，我试图解释链表，将它们描述为列表连接(链接)的地方。然而，在大多数链表的例子中，我看不到链表的连接。而是将对象或节点链接起来。
我的问题是:为什么它被称为“链表”？为什么不是“链接节点”或“链接对象”？
浏览 12提问于2016-09-08得票数 0
回答已采纳
2回答
链表和构造函数
、、
我发现了一个很大的源代码，它使用了几种类型的链表数据结构。例如，代码中使用的简单链表数据结构是使用链接类型的nextLink节点和初始化对象的构造函数。
public class Link {
public int data1;
public double data2;
public Link nextLink;
//Link constructor
public Link(int d1, double d2) {
data1 = d1;
data2 = d2;
}
}
另一方面，另一段代码使用以下数据
浏览 2提问于2014-03-14得票数 0
1回答
使用列表表示BigInt
、、、
我正在尝试编写自己的BigInt实现，使用列表来跟踪大整数中的所有数字。每个类实现都在一个单独的文件中。
struct node
{
int value;
node *next;
};
class LIST
{
private:
node *head;
public:
. . .
};
class BigInt
{
Private:
LIST numList;
Public:
BigInt addNum(BigInt& b);
. . .
};
如何实现by
浏览 1提问于2014-02-13得票数 0
LinkedHashMap描述说“它维护了一个通过所有条目运行的双向链表”，所以我想知道如何输入最后一个条目或键？我是否可以自信地将.values()转换为LinkedList，以获得该双向链表并使用其中的.getLast()？或者它是其他Java集合的一个实例？
如果可能的话，我想坚持使用java.util。
浏览 0提问于2011-09-03得票数 7
我正在尝试将链表转换为循环双向链表，但在使用链表类中的一组不同方法时遇到了一些问题，例如，我不知道如何更改writeList()方法这就是它现在的样子
public void writeLinkedList() {
Node p, q;
System.out.println("Writing list:");
for (p = listStart, q = null; p != null; q = p, p = p.getNext());
for (p = listStart; p != q; p = p.getNext())
浏览 2提问于2016-11-22得票数 0
1回答
如果我的问题听起来很愚蠢，我很抱歉，因为我对数据结构的理解不是很好。
我一直在读有关算法的文章，基本上理解了它的工作原理。这里提到，dancing的数据结构可视化看起来就像一个包含列和行的表，每个单元格都连接到上面、下面、左边和右边的单元格。我还读到在这个算法中使用了循环双链表。
我想知道的是，如何准确地将双向链表制作成这样的有列和有行的表？
据我所知，大多数双向链表只有2个指针(向上和向下)，这是否意味着我必须制作自己的自定义链表，它有4个指针(向上、向下、向左和向右)？或者还有其他方法？
提前谢谢。
浏览 5提问于2012-07-28得票数 5
回答已采纳
某标准书中给出的事实是，循环双向链表的连接复杂度为O(1)，而单链表和双链表的情况并非如此。有没有人能解释清楚这是为什么以及如何实现的.
浏览 1提问于2016-01-07得票数 1
1回答
堆栈已在Java中使用可调整大小的数组(Vector)实现。然而，据我所知，尽管您可以选择，但对于常见应用程序，队列通常是使用LinkedList实例化的。
我知道，从理论上讲，它们支持所有O(1)最坏情况或摊销的操作。然而，是否有特定的原因使可调整大小的数组更适合堆栈，而链表更适合队列？
换句话说，为什么它们不都使用可调整大小的数组或链表呢？
浏览 42提问于2018-08-17得票数 6
回答已采纳
2回答
我现在正在上Java课，教授告诉我们，理解链接的一个好方法是创建一个双重链表。我已经创建了一个单链表，但我在将其转换为双链表时遇到了问题。因此，我想知道是否有人可以给我任何建议，以确保我的最后一个号码是连接到前一个号码？如果前面的数字和最后的数字连接到null。这是代码的一部分，如果你想要更多的代码，只要问我，我会发布的。
用于添加元素等的代码。这是我试图使尾部连接到最后一个数字的尝试。
public void add(int element){
Node n = new Node();
n.setItem(element);
浏览 0提问于2013-09-13得票数 0
1回答
您好，我收到一条错误消息“我无法对非静态字段进行静态引用” 在下一段代码的粗体行中，我不知道如何修复它，我的实现对于链表是否正确，因为我希望它是一个双向链表 import java.util.Scanner;
import java.util.LinkedList;
import java.lang.Number;
public class chainLadder {
static Scanner s = new Scanner (System.in);
public LinkedList<Object> readData() {
Link
浏览 21提问于2020-06-09得票数 0
1回答
您好，我正在尝试实现选项页面替换
目前，我已经为所有未来的内存访问引用创建了一个链表。
我最初的想法是比较链表中的每个引用，并标记距离，以便它下一次作为属性出现。当实际运行程序时发生页面错误时，我会检查页表中的每一页，并逐出距离最长的页。
然而，我发现我的想法实现起来相当复杂和低效。有没有更简单的方法来实现这个算法？谢谢。
浏览 1提问于2014-11-07得票数 1
6回答
我最近从我的PHP中得到了以下错误：
WARNING: [pool www] child 42475 said into stderr: "*** glibc detected *** php-fpm: pool www: corrupted double-linked list: 0x00000000013fe680 ***"
我对这个问题不是很感兴趣，也不是很感兴趣。但我很有兴趣理解这个错误‘损坏的双向链表’的实际含义，因为我以前没有见过它。我相信我知道什么是双向链表，但是我没能产生一个触发这个错误的程序。
有没有人能给我提供一个简短的代码片段，当我编译和执行glibc时，
浏览 0提问于2013-02-15得票数 49
回答已采纳
6回答
(CLRS)指出，使用双向链表的哈希表能够比使用单链表的哈希表更快地删除项目。谁能告诉我在Hashtable实现中使用双链表而不是单链表删除的好处是什么？
浏览 1提问于2011-07-28得票数 9
回答已采纳
为了实现循环队列，你使用的是单链表、双链表还是数组?什么时候?为什么？
我基本上想说的是
数组与链表固定大小更多内存用于指针是的，我明白
但是，什么时候才能使用双链表在单链表上实现循环队列，反之亦然？
浏览 3提问于2017-01-13得票数 2
2回答
我一直在尝试理解为什么LRU缓存使用双重链表而不是单一链表？
如果按时间复杂度计算，它们在插入、更新和删除时都有相同的时间复杂度。
是不是因为DLL中的两个指针用来方便节点向后或向前移动?？
浏览 0提问于2020-02-17得票数 0
3回答
我在计算双向链表的元素时遇到了一些问题。
以下是节点类：
public class Node {
private Node previous, next;
private Object data;
public Node(Object data) {
this.data = data;
}
public Node() {
}
public Node(Object data, Node previous, Node next) {
this.previous = previous;
this.next = next;
this.
浏览 3提问于2016-04-25得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
