跟大家门交流一下:一、插入操作(insert)(一)基本原理    双链表就好像是手拉手站成一排的人,每个人的右手(next)拉着下一个人,左手(prior)拉着前一个人,每两个人之间有两支手互联.插入操作实际是向队伍中增加人员,他需要拉上左右两边的人,即共三个人要发生关系,由于每两个人之间有两支手互联,所以要发生4次操作.如已知节点q,p,需插入s,（称为原型吧）.----------------------------------    q->next    --->q          p        <---    p->prior --------------------------------- 现在假设需插入节点s,则需进行以下4次操作: ----------------------------------------- (1)(2)完成q与s的握手               (1)    q->next  = s;       (2)    s->prior = q;     q->next    --->q          s        <---    s->prior -----------------------------------------(3)(4)完成s与p的握手               (3)  s->next  = p;       (4)  p->prior = s;     q->next s->next    ---> --->q          s      p   <---  <---    s->prior p->prior------------------------------------------- 对于本文的案例，是原型的变种, 只已知节点p,而不知节点q,但通过双向链表的性质我们可以再初始时(插入前)得到以下关系:        p->prior = q; 所以对于以上的4次操作我们可以作等效替换,即将q 换为 p->prior,则以上4次操作为:       (1)  p->prior->next  = s;       (2)  s->prior = p->prior; file://(1)(2)完成q与s的握手              (3)  s->next  = p;       (4)  p->prior = s;        file://(3)(4)完成s与p的握手        (二)互换问题     由于不知道q节点，因此用p->prior来代替，所以p->prior的值应当在已经不再使用q节点的时候再改变，由原型：  (1)  q->next  = s; (2)  s->prior = q; (3)  s->next  = p; (4)  p->prior = s;(4)改变了p->prior的值，而(1)(2)需使用q,所以(4)应当在(1)(2)后。 二、删除操作(insert)(一)基本原理    删除操作就好像某个人退出队伍，但退出前他需要让他两边的人把手拉上,以保持队伍的连续性,也好像离职前要把工作要交接好,就好像我现在,哈...,如已知q,s,p, 需删除s,由于只需两个人发生关系,所以需进行以下两次操作:        (1)  q->next  = p;       (2)  p->prior = q;     q->next s->next    ---> --->q          s      p   <---  <---    s->prior p->prior   q->next    --->q          p        <---    p->prior 对于本例,是上面原型的变种,只已知s,但由双向链表的性质,我们可以推出以下关系:        q == s->prior;       p == s->next; 因此可做以下替换:        (1)  s->prior->next  = s->next;       (2)  s->next->prior = s->prior; 由于s ,以及prior和next的值在两次操作中并没有被改变,因此(1)(2)的顺序没有关系. 三、一些结论  （1）对于双向链表的插入，只需知道插入位置的一个节点即可完成插入；  （2）对于双向链表的删除，只需知道删除节点即可完成删除。      因此对于双向链表的插入和删除在该情况下，时间度为O(1)。       个人拙见,欢迎大家批评指正.

评论