数据结构之单链表基本运算的实现[11]

p= R –>next; /*保存R 的头结点指针*/

R>next=R>next>next; /*头尾连接*/

free(R>next); /*释放第二个表的头结点*/

R>next=p; /*组成循环链表*/

这一过程可见图

图

双向链表

以上讨论的单链表其结点只含有一个指向其后继结点的指针域next因此若已知某结点的指针为p其后继结点的指针则为p>next 若要找其前驱则只能从该链表的头指针开始顺着各结点的next域进行也就是说查找后继的时间性能是O()查找前驱的时间性能是O(n)如果要克服单链表的缺点希望查找前驱的时间性能达到O()则只能付出空间的代价每个结点再加一个指向前驱的指针域结点的结构为如图所示用这种带前驱和后继指针结点组成的链表称为双向链表

图 带头结点的双向循环链表

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []