有没有 vim script 版的链表

[自由建客]

想参考

[lilydjwg]

list 和 dict 都有了，还要链表做什么？真要的话，自己写有什么难的？

[fanhe]

动态类型脚本, list足够了, 你需要好像c语言那种的话, 用字典当类写一个

[自由建客]

我需要一个可快速以存入顺序读出的容器，就像 FIFO 。同时又需要可快速从中间抽取元素的结构，就像链表。
我用这样的递归建构感觉很别扭

代码： 全选

[int, [int, [int, []]]

[fanhe]

你需要个队列吧, 我随便写个, 没有测试, 自己看着办

代码： 全选

let g:Queue = {}
let g:Queue.data = []
function! g:Queue.Add(data)
    call add(self.data, a:data)
endfunction

function! g:Queue.Pop()
    return remove(self.data, 0)
endfunction

[自由建客]

fanhe,
我就是觉得 list 删除元素可能会很慢才想用链表的。

[fanhe]

fanhe,
我就是觉得 list 删除元素可能会很慢才想用链表的。

内置的数据结构会比你自己写的数据结构慢? 开玩笑吧

[lilydjwg]

fanhe,
我就是觉得 list 删除元素可能会很慢才想用链表的。

用 Python 吧。

[Fermat618]

fanhe,
我就是觉得 list 删除元素可能会很慢才想用链表的。

内置的数据结构会比你自己写的数据结构慢? 开玩笑吧

python和C++都有deque类，就是为了为FIFO提供一个合适的数据结构。

对于python的list，在尾部插入或删除，是固定时间复杂度，但在头部插入或删除，
却是线性时间复杂度。这样的数据结构明显不适合做FIFO。合适的FIFO在头部推出和
在尾部推入都应该是固定时间复杂度的。

一般的list为了实现的高效不会做成deque那样的形式的。vim里的list具体情况我不
是很清楚，因为对vim script了解不深。但楼主的担心是很有道理。

[lilydjwg]

一般的list为了实现的高效不会做成deque那样的形式的。vim里的list具体情况我不
是很清楚，因为对vim script了解不深。但楼主的担心是很有道理。

双链，见 src/structs.h:1139 、 src/eval.c:6519 。

[fanhe]

fanhe,
我就是觉得 list 删除元素可能会很慢才想用链表的。

内置的数据结构会比你自己写的数据结构慢? 开玩笑吧

python和C++都有deque类，就是为了为FIFO提供一个合适的数据结构。

对于python的list，在尾部插入或删除，是固定时间复杂度，但在头部插入或删除，
却是线性时间复杂度。这样的数据结构明显不适合做FIFO。合适的FIFO在头部推出和
在尾部推入都应该是固定时间复杂度的。

一般的list为了实现的高效不会做成deque那样的形式的。vim里的list具体情况我不
是很清楚，因为对vim script了解不深。但楼主的担心是很有道理。

用脚本了还在担心这点效率问题啊
这显然是自寻烦恼

[Fermat618]

fanhe,
我就是觉得 list 删除元素可能会很慢才想用链表的。

内置的数据结构会比你自己写的数据结构慢? 开玩笑吧

python和C++都有deque类，就是为了为FIFO提供一个合适的数据结构。

对于python的list，在尾部插入或删除，是固定时间复杂度，但在头部插入或删除，
却是线性时间复杂度。这样的数据结构明显不适合做FIFO。合适的FIFO在头部推出和
在尾部推入都应该是固定时间复杂度的。

一般的list为了实现的高效不会做成deque那样的形式的。vim里的list具体情况我不
是很清楚，因为对vim script了解不深。但楼主的担心是很有道理。

用脚本了还在担心这点效率问题啊
这显然是自寻烦恼

那也要看楼主想干什么了。如果只是少数元素倒没什么，要是有个成千上万个可能就不得不考虑了。要不然写出一个插件来，每个动作都要等2秒以上，我想这个插件除了把Vim搞死也没什么用了。

[fanhe]

fanhe,
我就是觉得 list 删除元素可能会很慢才想用链表的。

内置的数据结构会比你自己写的数据结构慢? 开玩笑吧

python和C++都有deque类，就是为了为FIFO提供一个合适的数据结构。

对于python的list，在尾部插入或删除，是固定时间复杂度，但在头部插入或删除，
却是线性时间复杂度。这样的数据结构明显不适合做FIFO。合适的FIFO在头部推出和
在尾部推入都应该是固定时间复杂度的。

一般的list为了实现的高效不会做成deque那样的形式的。vim里的list具体情况我不
是很清楚，因为对vim script了解不深。但楼主的担心是很有道理。

用脚本了还在担心这点效率问题啊
这显然是自寻烦恼

那也要看楼主想干什么了。如果只是少数元素倒没什么，要是有个成千上万个可能就不得不考虑了。要不然写出一个插件来，每个动作都要等2秒以上，我想这个插件除了把Vim搞死也没什么用了。

如上写个queue 类，接口固定下来
至于实现，随便换都可以，可以用内置的list也可以自己写

[xhy]

用dict,
A = {'val': 123 'next': B}
B = {'val': 456, 'next': C}
............

或者list
A = [123, B]
B = [456, C]
..............

注意next元素的保存，要存"引用"，不能存"值"。

本质上，链表只要存储2个东西(双向的是3个)
(node的值或者索引，下一个node的索引)，一般当前node存值或者引用比较常见，取值是O(1)的，
当然，脚本解析器内部对名字的解析可能不是O(1)的，这是不可控因素，可以不予考虑。

下一node的索引，C语言存地址，python可以存mutable对象，不支持浅copy的语言，可以存值在dict中的key
一般的dict或者名字解析的实现，复杂度往往是O(1)，最坏的实现也不会高于O(logn)，所以几万条数据可以放心

[自由建客]

我要有序表，不能用词典， vim script 没红黑树，既然内置的 list 是链表，那就用它得了