线性表的链式表示——双链表数据结构

1、和单链表比较
单链表无法逆向检索
双链表可进可退
存储结构：

文章图片

typedef struct DNode {//定义双链表节点类型 ElemType data; //数据域 struct DNode *prior, *next; //前驱和后继指针 } DNode, *DLinkList;

2、插入节点
【线性表的链式表示——双链表】在p节点后插入s节点，注意执行的顺序

文章图片

/** * 在p节点之后插入s节点 * @param p * @param s * @return */ bool InsertNextDNode(DNode *p, DNode *s) { if (p == NULL || s == NULL) {//非法参数 return false; } s->next = p->next; if (p->next != NULL) {//如果p节点有后继节点 p->next->prior = s; } s->prior = p; p->next = s; return true; }

3、删除节点
删除p节点后的q节点

文章图片

/** * 删除p的后继节点 * @param p * @return */ bool DeleteNextNode(DNode *p) { if (p == NULL) { return false; } DNode *q = p->next; //找到p的后继节点q if (q == NULL) { return false; } p->next = q->next; if (q->next != NULL) {//q节点不是最后一个节点 q->next->prior = p; } free(q); //释放空间节点 return true; }