我在读关于链表的文章。我发现:从链表中删除所需的元素需要O(n)运行时间，其中n是列表中元素的数量。
但在这个网页中，我发现从链表中删除一个元素是: O(1)。
从链表中删除时，上述大O符号中的哪一个是正确的。
谢谢
浏览 0提问于2016-11-07得票数 3
回答已采纳
我读过关于链表和数组的文章，大多数我读到的是数组在搜索方面更好，链表在插入和删除方面更好，但没有证据。我需要有人告诉我为什么？！
浏览 0提问于2018-10-21得票数 0
8回答
在今天的一次面试中，我被问到这个问题。
除了回答、颠倒列表和向前和向后遍历之外，面试官还不断强调其中有一些“基本”的东西。我放弃了，当然在面试后做了一些研究。在双向链表中插入和删除似乎比单链表更有效。我不太确定如何才能更有效地使用双向链表，因为很明显需要更改更多的引用。有人能解释一下背后的秘密吗？老实说，我做了相当多的研究，但未能理解我的主要问题是，双向链表仍然需要O(n)搜索。
浏览 0提问于2013-03-22得票数 51
回答已采纳
假设我有一个自己创建的链表。它有自己的析构函数，可以释放内存。此链接列表不会重载new或delete。
现在，我正在尝试创建一个由上述链表组成的数组(如果我理解正确的话，可以使用开放散列)。然后，我在这个开放散列类的构造函数中分配必要的内存。在构造函数中调用的new运算符足以为数组正确分配内存，对吧？我不确定，因为我还没有为链表类重载new。
另外，假设我的链表数组名为elements，我可以在析构函数中只写"delete[] elements“吗？这会为数组中的每个元素调用析构函数并正确地释放内存吗？
最后，如果我的两个假设都是正确的(例如，我不需要重载new和delete就可以在我
浏览 3提问于2008-12-25得票数 4
6回答
(CLRS)指出，使用双向链表的哈希表能够比使用单链表的哈希表更快地删除项目。谁能告诉我在Hashtable实现中使用双链表而不是单链表删除的好处是什么？
浏览 1提问于2011-07-28得票数 9
回答已采纳
链表中的头节点是否有任何信息，或者它是否只指向链表的第一个节点？
我们可以定义一个头节点作为链表的起始节点吗？
头节点是否只指向第一个节点？链表由节点组成，每个节点包含一些数据和指向列表中另一个节点的链接。但是第一个节点是包含数据和到第二个节点的链接的节点吗？或者它只包含一个到节点的链接(不包含数据)？我认为链表中的第一个节点既有数据又有到另一个节点的链接，但在一本介绍性书籍中解释说，head是一个节点，但它是一个链接，可以把你带到第一个节点。同时，head是节点类型的一个变量。为什么会这样呢？
浏览 0提问于2012-02-02得票数 2
回答已采纳
3回答
删除链表
、
嘿，我想知道我是不是写了一个C++链表，在这个链表中，我调用了一个析构函数来遍历一个分配的链表，并删除每个找到的节点。然而，我发现，尽管它遍历链表并删除每个匹配项，但它仍然会打印值。虽然只是一些废料的价值。
但是，当我删除linked_list时，它不应该是下次不能打印的吗？我正在使用new和delete创建一个链表，当我删除该列表时
sorted_list::~sorted_list()
{
// Destructor implementation
destroy(this->first);
cout << "Destructor calle
浏览 3提问于2010-11-06得票数 2
回答已采纳
5回答
我想知道你们中是否有人可以给我讲解如何在python中删除链表中的元素，我并不是要代码，而是一个用英语写的伪算法。例如，我有一个链表1 -> 2 -> 2 -> 3 -> 4，我想删除其中一个2，我该怎么做呢？我想遍历链表，检查其中一个节点的数据是否等于它后面的节点的数据，如果是删除它。但我在拆卸部分时遇到了麻烦。谢谢!
浏览 0提问于2015-10-29得票数 2
1回答
在创建链表(单链表)时，我应该涵盖哪些边缘情况？
我已经介绍的一些案例包括：
a)无节点(b)只有一个节点(c)在头/尾添加节点(d)避免遍历列表时的无限循环(e)避免内存泄漏和悬空指针
浏览 1提问于2020-05-16得票数 0
10回答
为什么我们需要一个“循环链表”(单或双)数据结构？
它解决了简单链表(单链表或双链表)明显的什么问题？
浏览 0提问于2010-08-28得票数 54
回答已采纳
22回答
数组与链表
、、、
为什么有人想要在数组上使用链表呢？
毫无疑问，编写链表比使用数组要多一点的工作，人们可能想知道什么可以证明这些额外的工作是合理的。
我认为在链表中插入新元素是微不足道的，但在数组中却是一件很重要的事情。与将数据存储在数组中相比，使用链表存储一组数据是否还有其他优势？
这个问题不是的重复，因为另一个问题是问一个特定的Java类，而这个问题是关于一般数据结构的。
浏览 183提问于2008-10-03得票数 211
回答已采纳
当我们用C++编写一个链表程序时，它将给我们提供我们可以在链表上执行的所有操作，如插入、删除、搜索等。但是一旦我们退出程序，那么创建的列表会发生什么呢？
如果我们把所有的数据写到一个文件中，那么有没有一种方法可以重建我们在退出程序之前创建的相同的链表，这将再次在相同的时间内给我们所有的操作带来复杂性？
浏览 1提问于2018-10-23得票数 0
如何仅释放链表中的单个节点？下面的代码释放了整个链表，但我只想释放链表中的一个节点。
//Here's my code for delete
while(headPtr!=NULL)
{
temp = headPtr;
headPtr = headPtr->next;
if(strcmp(temp->fname, stdfname) ==0 &&
strcmp(temp->sname, stdsname) ==0 )
{
free(temp);
}
}
浏览 0提问于2011-03-05得票数 0
7回答
我试着确认链表插入的运行时间，似乎有两个不同的答案。
为了在链表的末尾插入一个元素，我认为它需要O(n)，因为它必须遍历到链表的末尾才能访问尾部。但是我看到的一些答案是O(1)？他们是否假设所有的链表都实现了一个指向尾部的指针？如果是这样，这是一个可以接受的假设吗？
其次，一些地方还建议在链表的中间插入一个元素是O(1)，这是因为我对此感到困惑，因为遍历到列表的中间以插入它的推理是相同的。
有人能澄清一下吗？谢谢。
浏览 0提问于2009-12-19得票数 8
1回答
我正在为不同数据结构上的操作效率编写一个列表。到目前为止，我得到了以下内容：
我不太确定这里的队列是链表，堆栈是链表。有人能对这个问题有什么见解吗？
浏览 0提问于2012-12-17得票数 0
回答已采纳
我们希望在链表中找到一项，对该项执行某些操作，然后将其删除。
from collections import deque
q = deque([(12, 'apples'), (32, 'oranges'), (42, 'pears'), (12, 'peaches')])
john_smith_id = 42
for customer in q:
id, data = customer
if id == john_smith_id:
myfunction(data) # do somethi
浏览 2提问于2020-10-26得票数 0
如果一个队列是用链表实现的，但是链表只引用了head，那么enqueue的运行时间是多少，去队列的运行时间是多少？
浏览 1提问于2021-05-12得票数 0
回答已采纳
1回答
图形表示-链表的链表
、、、
我知道邻接表是一种常见的数据结构，它使用链表数组来表示图。我正在用C语言为一个简单的搜索引擎实现一个倒排索引，并打算使用邻接表。但是，我发现使用邻接表的一个缺点是，如果您不知道倒排索引中将有多少个单词，则必须假设索引中有任意数量的单词(数组元素)才能创建邻接表。这可能会导致使用过多的内存。这不是一个大问题，但我想知道是否有更好的方法来实现它。
我在想，这个问题的一个解决方案是创建一个链表的链表来表示我的倒排索引。我还没有见过链表的链表图形表示的许多示例，所以我假设它不是常用的或常规的表示。我想知道使用链表的链表来表示图形是否合适？还是坚持使用邻接表更好？任何真知灼见都将不胜感激。
浏览 14提问于2018-07-26得票数 4
回答已采纳
1回答
我有一个值数组和一个索引链表。现在，我只想保留数组中与LL中的索引相对应的那些值。有没有一个标准的算法来做到这一点。如果可能，请举例说明。
因此，假设我有一个数组1,2,5,6,7,9，我有一个链表2->3
因此，我希望将值保持在索引2和3，即keep 5和6。因此，我的函数应该返回5和6
浏览 0提问于2011-10-21得票数 1
根据定义，链表是一个列表，它的每个元素都指向下一个元素(如果我们谈论的是双向链表，也可以是前一个元素) 。
然而，在Java语言中，LinkedList实现了List、Queue、Deque等等。
在LinkedList中找不到提供列表中下一个或上一个对象的方法，最好的方法是获取迭代器和对象。我的问题是，为什么Java将这种数据结构称为LinkedList，而它并不是真正的链表？链表可以在Java中实现，如下所示：
Public class MyLinkedList{
public int value;
public MyLinkedList next;
}
浏览 1提问于2013-02-12得票数 10
回答已采纳
2回答
我们说头链表是由一个叫做头节点的特殊节点组成的链表，它标志着列表的开始，但我不明白这个头节点的真正重要性是什么。请帮帮我?
浏览 0提问于2010-11-17得票数 0
回答已采纳
2回答
链表vs向量
、、
关于链表和向量的问题与效率有关。
我理解链表的插入/删除是恒定的时间，而对向量的相同操作是线性的。但是，考虑到您必须在链表上执行线性搜索才能插入/删除，那么这不是一个线性操作吗？
插入/删除操作本身是恒定的，但是因为您不能在没有遍历链表的情况下插入/删除，所以您最终得到了一个线性操作。搜索+插入/删除=线性。
所以我不明白这怎么会比向量更有优势。对我来说，这是一样的。两者(最终)都需要线性操作才能插入/删除。
这里我漏掉了什么？
浏览 1提问于2017-11-10得票数 2
假设我们已经有指向节点的指针，在列表的特定点插入或删除元素是一个固定时间操作。-来自
在单个链表中的链表遍历总是从头开始。我们必须继续前进，直到满足给定的条件为止。
因此，这将使任何操作在O(n)最坏的情况下，除非我们处理的是头节点。
我们不能直接指向链接列表中的给定指针。那为什么说它是一个固定时间的操作呢？
编辑:即使我们有一个指向节点的指针，我们也只能从头开始，对吗？那么它是如何恒定时间运行的呢？
浏览 12提问于2011-04-20得票数 13
回答已采纳
deleteNodeNoPointer(node) {
node.val = node.next.val;
node.next = node.next.next;
return node;
}
如何将单链表的节点指针传递给该函数
例如，如果first是该类的对象，并且我们有链表
1->2->3->4->5->null；我们必须将3的指针发送到上面的函数..
first.deleteNodeNoPointer(---POINTER--OF--NODE 3--IN--SINGLYLINKEDLIST);
浏览 1提问于2018-10-12得票数 0
假设我有一个由三个元素{1,2,3}组成的数据结构
如果我只想执行以下操作，什么样的数据结构和时间复杂度会给我带来最好的结果？
现在，将最后一个元素放在数据结构的“-Shifting”前面。(现在)最后一个元素
我发现了这个页面：，它说一个双向链表对于某些操作有O(1)？
然而，我每次都需要保持元素的顺序，这样我才能进行移位。如果我有{1,2,3}，我会想要移位，获取3,1,2，然后移除，留下3,1，然后移除，留下1
如果我使用双向链表，复杂度会是O(1)吗？
浏览 0提问于2011-08-14得票数 3
8回答
我不太明白为什么像所说的那样，在单个链表的末尾删除只需要O(1)时间。
单个链表由多个节点组成。节点包含某种类型的数据，以及对下一个节点的引用。链表中最后一个节点的引用为空。
-------------- -------------- --------------
| data | ref | -> | data | ref | -> ... -> | data | ref |
-------------- -------------- --------------
我可以删除O(1)中的最后一个节点。但是在这种情况下，您没
浏览 2提问于2012-12-27得票数 22
回答已采纳
3回答
链表的应用
、、
链表的应用有哪些很好的例子？我知道将队列和堆栈实现为链表是一个好主意，但是有没有一个实用的、直接的例子可以用链表来解决特别利用快速插入时间的问题呢？而不仅仅是基于链表的其他数据结构。
希望得到类似于这个关于优先级队列的问题的答案：
我自己找到了一个:使用哈希表和链表实现的LRU (最近最少使用)缓存。
还有一个具有InnerExeption的Exception类的示例
还有什么？
浏览 2提问于2013-09-14得票数 4
回答已采纳
15回答
我使用了很多列表和数组，但是我还没有遇到过一个场景，在这种场景中，数组列表不能像链表一样容易使用，如果不是更容易的话。我希望有人能给我一些例子，说明链表在什么情况下更好。
浏览 2提问于2008-12-26得票数 223
回答已采纳
1回答
很难调试删除循环链表中的头节点
、、、、
我正在学习数据结构，并练习关于循环链表的问题。所以，我应该写一个函数来删除循环链表的head节点，所以我想出了这个代码-
void del_head(struct node** head, struct node** tail)
{
struct node* new_head = (*head)->next;
free(*head);
*head = new_head;
(*tail)->next = *head;
}
调试后，我发现tail没有更新。
我很难找到问题所在。
感谢您的帮助，谢谢
浏览 8提问于2020-10-09得票数 0
我在读关于java编程中的大O符号的文章。我发现了下表，它显示了不同数据结构的不同大O。
我的问题是：
如果我想删除数组中的一个项，它是O(n^2)吗？(搜索和删除)
如果我想删除堆栈中的项，它是O(n)吗？
哪一个更有效，是单链表还是双链表？
在何种情况下，插入操作是哈希表中的O(1)或O(n)？
如果我想删除二进位搜索树中的一个项，它是O(log(n)*log(n))，而插入是O(log(n))吗？
谢谢。
浏览 8提问于2016-11-21得票数 5
回答已采纳
假设我有一个带有sentinel的单链表。要在O(1)时间内删除最后一个元素，我需要维护最后2个元素的句柄。但是维护最后两个元素的句柄会使add操作变得复杂。
有没有一种方法可以在不保留最后两个元素的句柄的情况下删除O(1)中带有标记的单链表的最后一个元素？我非常感谢任何用java编写的示例代码。
谢谢。
浏览 4提问于2012-07-08得票数 1
回答已采纳
1回答
最近我在学习跳过列表，我了解到它是为了加速链表的查找而设计的。但我想知道为什么不使用一种数据结构，它根据链表的结构添加所有节点的指针数组？对于一个2^n节点列表，如果每一层都有较低层的指针数量的一半，我们将添加2^n-1指针，这几乎与添加每个节点的指针列表的数量相同，同时按索引访问也是O(1)。 一定有一些原因不能实现我的想法，有人能告诉我吗？
浏览 10提问于2020-07-01得票数 1
回答已采纳
我被问到这样的问题，我有自己的说法，但我真的不确定该怎么说利弊？微软向其中一位候选人提出了这个问题。
单链表允许您单向访问。而双向链表具有next和previous双向。
这是一张很好的图片，画出了单色和双色的LinkedLists。
然而，如何以更有序的方式解释这些项目的优缺点？
浏览 8提问于2012-05-23得票数 22
回答已采纳
1回答
我已经为提要场景创建了一个链表结构。在这里，我将我的提要持久化在neo4j中的链表中。这工作得很好。但是，可能需要删除整个产品，所以我正在尝试想出一个cypher，它可以在一个查询中删除产品和提要的相关链表。此查询返回正确的数据
match p = (i:Item {uuid:"d98c299d-239b-40d1-ac2f-01a80ac36db4"})-[:LATEST]-(latestComment), latestComment-[:NEXT*0..]-(olders) return i, latestComment, olders;
基于这些代码行，我尝试使用fore
浏览 0提问于2015-10-13得票数 0
4回答
struct element {
unsigned long int ip;
int type;
int rtt;
struct element * next;
struct element * edge;
};
我有一个链表。我使用malloc创建新节点。我试图使用free (ptr to node)释放内存，但当我再次运行遍历函数时，我可以遍历链表，RTT值以及next和edge指针都是正确的，因为我可以跟随链表。ONly ip值已损坏。为什么会这样呢？
浏览 3提问于2011-03-22得票数 1
回答已采纳
2回答
我一直在尝试理解为什么LRU缓存使用双重链表而不是单一链表？
如果按时间复杂度计算，它们在插入、更新和删除时都有相同的时间复杂度。
是不是因为DLL中的两个指针用来方便节点向后或向前移动?？
浏览 0提问于2020-02-17得票数 0
1回答
我正在尝试为链表编写代码，以便它删除链表中的节点，它可以是链表中除第一个和最后一个节点之外的任何节点。我在下面提出了一些想法。 我不确定如何完成它，我知道在while循环中需要一些对k的引用，以便我们在遍历链表时跳过节点，但是我如何引用这个k呢？我会做一个'for i in range k'，然后在第k次迭代中执行跳过吗？ def delete_middle(l1,k):
if l1.head is None:
return None
current = l1.head
while current:
if curr
浏览 15提问于2021-01-31得票数 0
回答已采纳
假设我有一个由{12,25,46, 27 ,57}组成的链表，我选择k为4。我希望有一种方法来迭代这个链表，并只打印27作为输出。
我还想知道如何以同样的方式删除变量。因此，如果我从列表中选择变量3，我希望链表打印为{12,25,27,57}。
浏览 0提问于2021-03-05得票数 0
6回答
链表问题
、
删除单个链表的第t (t>1)个节点。在生成的链表中，再次删除第t个节点。重复此操作，直到只剩下t-1个节点。
为此，我想出了一个办法:遍历到第t个节点，删除所有的节点到最后，有没有比这更有效的方法呢？有没有人能帮我。谢谢。
浏览 0提问于2010-06-07得票数 0
回答已采纳
目前在多线程环境中，我们使用LinkedList来保存数据。有时，在日志中，当它轮询链表时，我们会得到NoSuchElementException。如果我们从链表转移到ConcurrentLinkedQueue实现，请帮助理解性能影响。
谢谢，Sachin
浏览 0提问于2011-09-06得票数 7
回答已采纳
2回答
我正在编写一个从链表中删除特定节点的函数。该函数适用于大多数情况，但当要删除的节点是头节点或链表中的唯一节点时，该函数不起作用。当这种情况发生时，我尝试将当前设置为等于NULL，但这会产生分段错误，我的逻辑哪里错了？
void deleteNodeAfter(Node *head, Node *delete) {
bool remove = false;
Node *current = head;
Node *delNode = delete;
if (current->songName == delNode->songName){
浏览 1提问于2017-03-31得票数 2
2回答
当我们有动态数组列表时，为什么我们需要一个链表？
我已经学习了静态列表和链表。我有动态数组列表的知识。但是我找不到这两者的确切区别，有人能帮我回答这个问题吗
浏览 1提问于2016-02-15得票数 4
回答已采纳
1回答
因此，我应该按字母顺序对Java中的链表进行排序(节点是字符串)。我不允许使用集合，因此我必须构建自己的链表和排序算法。我已经创建了一个方法，可以在链表中找到最大(或字母表下最远)的单词。现在，我尝试通过获取一个链表进行排序，找到最大的元素并将其插入到新的链表中。然后，它删除最大的，并继续执行相同的操作，直到链表为空。当我运行它时，我得到了一个空白列表，我的代码出了什么问题？
返回最大元素的代码
public Link isLargest(){
Link large = first;
Link temp = null;
Link current = first;
浏览 0提问于2014-06-18得票数 0
4回答
向量是链表的特例吗？
、、、
在谈到STL时，我有几个同学告诉我“向量是链表”。
我还有另一个论点，如果你用迭代器调用erase()方法，它会破坏向量，因为它是一个链表。
他们也倾向于不理解为什么我总是争论向量是连续的，就像任何其他数组一样，并且似乎不理解随机访问意味着什么。向量是严格连续的，就像常规数组一样，还是至多是连续的？(例如，如果整个数组不适合，它将分配几个连续的段)。
浏览 1提问于2011-01-15得票数 19
回答已采纳
3回答
我正在研究使用hash_map的单独链接，这是我需要的，但不是完全的。即使在链中，hash_map也会自动删除重复的值。我不想这样。
假设我有一个大小为4的向量，我想基本上将一个链表附加到该向量的每个索引上。链表也可以有重复的元素。
我对此进行了研究，但找不到适用于此的STL。有没有办法做到这一点？
我想这样做是为了创建一个数据库表。我有一个大小为4的向量，这4个点是表中的列，附加到每个索引的链表是表中的行。希望这是有意义的。
浏览 2提问于2013-03-06得票数 0
在CLRS的教科书“算法导论”中，有这样一段关于pg的内容。258。
如果列表是双链接的，我们可以在O(1)时间内删除元素。(请注意，链式哈希-DELETE将元素x作为输入，而不是它的键k，因此我们不必先搜索x。如果哈希表支持删除，那么它的链接列表应该是双链接的，以便我们可以快速删除一个项。如果列表仅被单独链接，那么要删除元素x，首先必须在列表中找到x，以便更新x的下一个属性。对于单链表，删除和搜索都有相同的渐近运行时间)。
令我困惑的是，这个大圆括号，我不明白它的逻辑。有了双链表，还得找到x才能删除它，这和单链表有什么区别？请帮助我理解它！
浏览 6提问于2011-11-12得票数 29
回答已采纳
1回答
在无锁存链表中插入和删除
、、、
我正在使用一个多线程程序中的共享链表。我不使用闩锁(互斥)，而是依靠CAS操作来确保插入和删除的正确性。所有插入和删除操作都发生在链表(LIFO)的头部。程序没有按预期工作，它随机地导致分段错误并退出。有什么想法吗？这是我的程序的一个简化版本。它在大约1%的时间内会因四个线程而中断。
struct Node {
unsigned long num;
Node* next;
};
Node* head = NULL;
#define NUM_THREADS 4L
#define Rounds 10000L
#define Iterations 100L
#define SumPerR
浏览 1提问于2013-03-13得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
