数据结构重学日记（十）双链表

2019-01-11 本文已影响4人南瓜方糖

概念

单链表：单个指针，单向火车。

双链表：双指针，电梯。

双链表在单链表的基础上增加了一个指向前边结点的指针。


typedef struct DNode{
    ElemType data;
    struct DNode * prve, *next;  // 前驱和后继指针
}DNode,* DLinkList;

假设有 $a_1$ 到 $a_4$ 个数据元素组成的双链表，要把 $a_5$ 插入到 $a_2$ 和 $a_3$ 之间，那么设指向 $a_2$ 的指针 p 和指向 $a_5$ 的指针 s ：

s->next = p->next
p->next->prev = s
s->prev = p
p->next = s

还是 $a_1$ 到 $a_4$ 等数据元素组成的双链表，要删除 $a_3$ ，设指向 $a_2$ 的指针 p 和指向 $a_3$ 的指针 q：

p->next - q->next
q->next->prev = p
free(q)

这种做法就是典型的用空间换时间。

因为大部分操作和单链表的操作类似，所以这里就不在花费时间详细操作了。