写一个“在双链表里在指定结点前插入结点”的函数，传参传什么？

[Adia]

原帖在这里

背景：菜鸟一枚，最近在自学数据结构与算法。

结果碰上这么一个问题，两个答案两个分歧。实在搞不懂，求万大 V 指一条明路。

[svenFeng]

这个要看你链表是怎么实现的咯。
比如你可以传一个指向链表的指针 p 和一个指定结点的排在第几位的整数 n ，然后指针顺下去达到结点插入就可以了。

[svenFeng]

没看原帖，尴尬。。。

[danngo2455]

同意原帖中的"不能是 Node"这个回答
接口的设计要和实现解耦, 换言之, 从调用方的角度看, 只需要知道这是一个 List.
另外, 在指定结点前插入结点其实可以拆分成语义更原子的接口, 一个是 indexOf(item), 返回 item 的下标, 另一个是 insert(index, item), 将元素插入指定下标处.

[aias]

我就过来看一下

[CRVV]

这种问题显然没有唯一的正确答案，两种方法都有优缺点

"不能是 Node" 的理由在 3 楼
"应该是 Node" 的理由是用 Node 的性能更好

[allanzyne]

是 c++的话是肯定传递迭代子的……

[Mirana]

void insert(Node *t,Node* n){
t->prev->next=n;
n->prev=t->prev;
n->next=t;
t->prev=n;
}

这样？

[allanzyne]

对于一个链表，却使用随机访问，而且是双向链表 = =

[yangff]

@manong 的那种做法会有一个很严重的偏差…… 值得注意
比如你现在有两个链表 A ， B
`A.insertBefore(A.find(YYY), B.find(XXX))` （假如说你这个 node 可以被外部访问，也是 @manong 做法 work 的一个基本要求对吧）

[calease]

如果这个链表是直接给人用的那肯定是传 node ，使用者不可能不知道 node 这个类。
如果是用链表的方式实现一个 List ，给人用 List ，那么上层的 list interface 设计里才会用到二楼的回答。

[starqoq]

@Mirana 没有判断 t 是头节点的情况。 t.prev == NULL


我不会 java ，这是 C++的写法。
注意结构体里面的 first ， last 都要是指针，否则无法表示空链表
函数将新节点 n 插入 t 之前，如果 t 为 NULL 表明插入到列表尾部。

链表维护需要小心谨慎，考虑到各种情况，头尾，空链表。注意维护首尾指针。
删除的时候也是一样。

void insert(Node *t,Node* n){
//如果有 size 需要维护
//size++;

n->prev = n->next = NULL;
if (t == NULL) //用 t==NULL 指明插入到列表结尾
{
if (last==NULL) //空链表
first = last = n;
else //插入到尾部
{
last->next = n;
n->prev = last;
last = n;
}
return ;
}

if (t->prev == NULL) // 说明是第一个 也可以用 first == t
{
first = n;
n->next = t;
t->prev = n ;
return ;
}

//一般情况
t->prev->next=n;
n->prev=t->prev;
n->next=t;
t->prev=n;
}

[minami]

其实吧，你这问题根子上是要搞清楚你要“如何定位 node ”，也就是“如何区分两个 node ”，如果你禁止重复的元素，那完全可以传元素值；反过来，你就只能传引用或者其他可以确定 node 的标识符（比如位置，比如 UUID ），这要看你的内部是如何实现的。
ps ：学习就是要多想想，比较各种实现的优劣，这和实际编程不一样，平时是有约定俗成的规范。

[zscself]

我觉得用 Java 写的话，可以写一个 insertBefore(Node node, Node newNode)再写一个 insertBefore(int i, Node newNode)，到时候愿意用哪个用哪个，/抠鼻。严蔚敏那本数据结构是用的后者。

[allanzyne]

typedef NodeValue int;
class Iterator;
class DoubleLinked {
class Node: Iterator;
Iterator insertBefore(Iterator& node, NodeValue v);
}