标签: linked-list

我开始在学校最后一年开始之前检查数据结构和算法,以确保我掌握一切.一个评论问题说"使用链表或动态数组实现堆栈并解释为什么你做出了最好的选择".

对我来说,使用带有尾指针的列表来实现堆栈似乎更直观,因为它可能需要经常调整大小.对于大量数据来说,列表是更好的选择,因为动态数组重新调整大小是一项昂贵的操作.此外,使用列表,您不需要分配比实际需要更多的空间,因此它更节省空间.

但是,动态数组肯定允许更快地添加数据(除非需要调整大小).但是,我不确定使用数组是否整体更快,或者只是不需要调整大小.

该书的解决方案说"存储非常大的对象,列表是一个更好的实现",但我不明白为什么.

哪种方式最好？应该使用哪些因素来确定哪种实施方式"最佳"？还有,我的逻辑是什么？

所以我知道如何拥有一个链表并使用add方法按条目输入条目.但是,我不想按条目添加条目.有没有办法在列表中声明一个带有初始值的链表？

例如,如果我想在列表中有1.0和2.0,我可以在一行中做些什么吗？就像是:

List<Double> temp1 = new LinkedList<Double>(1,2);

这不完全是一个技术问题,因为我知道C有足够的东西来做我需要的东西(我的意思是,不是'让语言妨碍你'),所以这个问题基本上是'什么方向'采取'问题.

情况是:我目前正在学习高级算法课程,并且为了"成长为程序员",我需要使用纯C来实现实际任务(它运作良好:几乎任何小错误你实际上都是你完全理解你正在做什么来解决它).在实现过程中,我显然遇到了必须从头开始实现"基本"数据结构的问题:实际上不仅是链表,还有堆栈,树等等.

我专注于本主题中的列表,因为它通常是一个结构,我最终在程序中使用了很多,作为"主"结构或作为其他更大的结构的"帮助"结构(例如,一个哈希树,可以解决使用链表冲突).

这要求列表存储许多不同类型的元素.我假设这里作为一个前提,我不想为每种类型重新编码列表.所以,我可以提出这些替代方案:

• 制作一个void指针列表(有点不优雅;更难调试)
• 只有一个列表,但是有一个联合作为'元素类型',包含我将在程序中使用的所有元素类型(更容易调试;如果元素的大小不同,则浪费空间)
• 使用预处理器宏为SGLIB样式重新生成每种类型的代码,"模仿"C++的STL(创造性解决方案;不浪费空间;元素具有返回时实际的显式类型; 列表中的任何更改代码可以真的很戏剧化)
• 你的想法/解决方案

要明确问题:上述哪一个最好？

PS:由于我基本上处于学术背景中,因此我对在行业中使用纯C的人的观点也非常感兴趣.我知道大多数纯C程序员都在嵌入式设备领域,我不认为我面临的这种问题很常见.但是,如果那里的任何人知道它是如何"在现实世界中"完成的,我会对你的意见非常感兴趣.

我需要能够在DB中存储大量订购商品.到目前为止,这是直截了当的:

ID Position OtherFields
 1     45      ...
 2   4736      ...
 3    514      ...
 ...

在查询中,我总是需要获得一些项目(基于OtherFields过滤),但顺序正确.也很容易,在位置上放置一个索引并使用"按位置排序".

现在问题是:项目经常更改其位置,而不仅仅是1或2.如果ID 2将位置从4736更改为2000,我需要更新其位置和旧位置2000和4735之间所有元素的位置,添加1在每一行.并且不仅每个事务更改一个ID而且还有一些ID,并且在短时间内可以有许多事务.

我认为处理更新问题最优雅的方法是使用链接列表而不是位置列,我可以通过将其前任链接到其后继者,然后通过在其之间链接将其插入其他位置,从而将ID 2从其旧位置移除新的前任和继任者.这将是每个职位变更的持续和少量更新,它也是我处理变更的首选方式(在我的案例中是Java).然而,这引起了N + 1问题查询正确的顺序-甚至几元,我不得不通过整个名单在最坏的情况下找出正确的顺序.

所以我的问题是:您建议在必要的更新和查询性能之间取得良好的平衡？

到目前为止,我看到两个有希望的方

1. 是否存在DBMS(理想情况下是OpenSource),它不仅可以处理链接列表,而且还可以处理具有良好性能的链接列表,例如通过使用链接元素的内部索引？

2. 也许只有一个BLOB可以选择存储整个链接列表!这样的链接列表有多大/它在数据库中使用了多少内存,并且当获取时让我们说1.000.000条目？我正在使用Java + Hibernate以防万一.我想在获取BLOB后处理内存中的整个列表应该非常快!

但当然也欢迎其他想法!

我正在Albahari兄弟的Nutshell中阅读C#4.0,我发现了这个:

堆栈在内部实现,其数组根据需要调整大小,与Queue和List一样.(第288页,第4段)

我不禁想知道为什么.LinkedList提供O(1)头尾插入和删除(这应该适用于堆栈或队列).可调整大小的数组有O(1)缓冲插入(如果我没记错的话),但O(n)最坏的情况(我不确定删除).它可能比链表使用更多的空间(对于大型堆栈/队列).

还有更多吗？双链表实现的缺点是什么？

最近,在一次采访中我被问到,hashmap中究竟是什么？无论是数组还是arraylist还是什么？

我很困惑.我知道哈希映射是由数组支持的.那么我可以说bucket是一个容量为16的数组,在开始存储哈希码时,链接列表的起始指针是什么？

我知道hashmap内部是如何工作的,只是想知道数据结构方面究竟是什么样的桶.

假设有两个单链表,它们在某个点相交并成为单个链表.

两个列表的头部或起始指针都是已知的,但交叉节点是未知的.此外,列表中每个列表中的节点数量在它们相交之前是未知的,并且两个列表可能具有不同,即List1在到达交叉点之前可能有n个节点,并且List2可能在到达交点之前有m个节点,其中m和n可以是

• m = n,
• m <n或
• m> n

一种已知或简单的解决方案是将第一列表中的每个节点指针与第二列表中的每个其他节点指针进行比较,匹配节点指针将通过该指针引导我们到交叉节点.但是,在这种情况下,时间复杂度将是O(n ²),这将是很高的.

找到交叉节点的最有效方法是什么？

创建这两个对象有什么区别

Queue<String> test = new LinkedList<String>();

和

List<String> test2 = new LinkedList<String>();

test和之间的实际差异是test2什么？他们俩都是LinkedList？是否存在使用其中一个的性能差异或原因？

我遇到了我的链表类的问题,我已经创建了类的接口和实现文件,但是当我构建它时,会发生以下错误:"无效使用模板名'LinkedList'而没有参数列表".这是我的界面文件:

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

template <typename T>
struct Node{
    T info;
    Node<T> *next;
};

template <typename T>
class LinkedList
{
    Node<T> *start;
    Node<T> *current;
public:
    LinkedList();
    ~LinkedList();
};

#endif // LINKEDLIST_H

这是我的实现代码:

#include "LinkedList.h"

LinkedList::LinkedList()
{
   start = nullptr;
   current = nullptr;
}

LinkedList::~LinkedList()
  {

  }

是否有任何方法可以使用不超过两个指针找到链接列表中的循环开始？ 我不想访问每个节点并标记它并报告第一个节点已经被看到.有没有其他方法可以做到这一点？