双向链表结点的插入.doc

《双向链表结点的插入.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、双向链表结点的插入双向链表的插入操作基本上和单链表相同，但是双向链表的指针的调整要比单链表复杂。下面我们仍然采用例子说明的方式来讨论结点的插入问题。1.例子现有一个双向链表如图3-18所示。bdcNULLaNULLhead图3-18双向链表示例此时将结点插入链表有三种情况：（1）插入在双向链表首结点之前新的结点插入在双向链表的首结点之前，需要将新结点的指针next指向首结点，同时原链表的首结点的prior指针需指向新结点。另外 ，head指针指向新结点，即新结点成为双向链表的开始。其过程如下图所示。新结点原首结点dabNULL…NULL…head图3-19双向链表结点插

2、入在首结点之前示例（2）插入在双向链表的尾端新结点若插入在双向链表的尾端，需要将尾结点的指针next指向新结点。同时将新结点的指针prior指向链表的尾结点。其过程如下图所示。dabNULL...NULL…原尾结点新结点head图3-20双向链表结点插入在尾端示例（3）插入在链表的中间新的结点插入在链表的中间，如果我们找到p结点，将结点插入在其后，则需要将新结点的next指针指向p结点的next指针，但不能让链表断裂。再将新结点的prior指针指向p结点，然后将p结点的next指针指向新结点，最后再将下一个结点的prior指针指向新结点。其过程如下图所示。cbadNUL

3、LNULLheadp新结点图3-21双向链表结点插入在中间示例2．算法思想（1）向系统申请一个新结点（new）供用户输入欲插入结点的内容。（2）用户输入一个结点内容（key），表示欲插入在那一个结点之后。（3）依次寻找下一个结点，直到结点内容等于key或结点指针为NULL（即找不到该结点）。如果该结点不存在，则插入在首结点前：new->next=head;head->prior=new;head=new;如果找到该结点，且在双向链表中间：new->next=p->next;new->prior=p;p->next=new;new->next->prior=new;如果找

4、到该结点，且在双向链表的尾端：new->next=p->next;new->prior=p;p->next=new;