双向链表结点的插入和删除算法_双向链表中节点的插入

双向链表的插入与删除

双向链表的结点定义

#define  ElemType int
//双向链表的存储结构
typedef struct DuLNode
{
    ElemType data;
    DuLNode *prior;
    DuLNode *next;
}DuLNode, *DuLinkList;
1
2
3
4
5
6
7
8

双向链表的结点插入

画图表示，并在上述双向链表中一个已知结点p之后插入一个结点s的四条语句，请标明先后顺序。

对应的代码片段为：

//在第i个结点p之后插入s，数据域是e的结点
void ListInsert_DuL(DuLinkList &L, int i,ElemType e)
{    
    DuLNode *p;
    p = GetElem_DuL(L,i);//在L中确定第i个元素的位置指针p
    //新建一个结点
    DuLNode *s;
    s = new DuLNode;
    s->data = e;
    //插入
    s->prior = p;
    p->next->prior = s;
    s->next = p->next;
    p->next = s;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

双向链表插入算法的注意事项：插入新结点的核心步骤为修改四个指针，要保证在插入的过程中不能断开链表原来的链，否则链表就断链了。

双向链表的结点删除

画图表示，并在上述双向链表中删除一个已知结点p的两条语句，请标明先后顺序。

对应的代码片段为：

//在双向链表中删除第 i个结点
void ListDelete_DuL(DuLinkList &L, int i)
{
    DuLNode *p;
    p = GetELem_DuL(L,i);在L中确定第i个元素的位置指针p
    //重建链
    p->prior->next = p->next;
    p->next->prior = p->prior;
    //删除p结点
    delete p;
}
1
2
3
4
5
6
7
8
9
10
11

双向链表删除算法的注意事项：插入新结点的核心步骤为修改只需要修改两个指针，方法简单，注意释放结点p的空间即可。

作者practical_sharp
第一次写博客，有很多做的不周到地方，不喜勿喷。