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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3025 天前的主题，其中的信息可能已经有所发展或是发生改变。

原帖在这里

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

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

双链表

明路

结点

原帖

14 条回复 • 2016-08-21 19:05:27 +08:00

Em5O7B1JGfjQnBry

2016-08-20 18:55:32 +08:00 via Android

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

Em5O7B1JGfjQnBry

2016-08-20 18:59:56 +08:00 via Android

没看原帖，尴尬。。。

danngo2455

2016-08-20 19:08:33 +08:00

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

aias

2016-08-20 19:56:10 +08:00

我就过来看一下

CRVV

2016-08-20 20:05:45 +08:00

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

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

allanzyne

2016-08-20 20:45:54 +08:00 via Android

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

Mirana

2016-08-20 21:24:09 +08:00

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

这样？

allanzyne

2016-08-20 21:31:16 +08:00

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

yangff

2016-08-20 22:17:39 +08:00

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

calease

2016-08-21 00:35:40 +08:00

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

starqoq

2016-08-21 01:30:53 +08:00

@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

2016-08-21 03:06:55 +08:00

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

zscself

2016-08-21 16:31:18 +08:00

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

allanzyne

2016-08-21 19:05:27 +08:00 via Android

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