数据结构--双链表

数据结构–双链表

单链表 VS 双链表
单链表：无法逆向检索，有时候不太方便
双链表：可进可退，存储密度更低一丢丢

双链表的定义

typedef struct DNode
{ElemType data;struct DNode *prior, *next;
}DNode, *DLinkList;

双链表的初始化

bool InitDLinkList(DLinkList &L)
{L = (DNode*)malloc(sizeof(DNode));if (L == NULL)  return false;L->prior = NULL;L->next = NULL;return true;
}

判断双链表是否为空

bool Empty(DLinkList L)
{return L->next == NULL;
}

双链表的插入

在p结点之后插入s结点

特殊处理：p是最后一个结点

bool InsertNextDNode(DNode* p, DNode* s)
{if (p == NULL || s == NULL) return false;s->next = p->next;if (p->next != NULL)p->next->prior = s;s->prior = p;p->next = s;return true;
}

用后插操作实现结点的插入有什么好处？
按位序插入前插操作：
找到前一个结点进行后插操作

双链表的删除

####删除p的后继结点q

特殊处理q是最后一个结点

bool DeleteNextDNode(DNode* p)
{if (p == NULL)  return false;DNode* q = p->next;if (q == NULL)  return false;p->next = q->next;if (q->next != NULL)q->next->prior = p;free(q);return true;
}

销毁双链表

void DestoryList(DLinkList &L)
{while (L->next != NULL)DeleteNextDNode(L);free(L);L = NULL;
}

将指针L置为NULL的意义是，将其指向空地址，表示该指针不再指向任何有效的内存空间。这样做的目的是为了防止出现野指针的问题，即指针指向已被释放的内存空间，避免在后续代码中误用该指针导致程序崩溃或产生不可预料的结果。

双链表的遍历

后向遍历

while (p != NULL)p = p->next;

前向遍历

while (p != NULL)p = p->prior;

前向遍历 (跳过头结点)

while (p->prior != NULL)p = p->prior;

时间复杂度：
双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度 O(n)

知识点回顾与重要考点