双链表和循环链表

线性表的链式和线性存储见前两篇文章

一、双链表

1.定义：

在线性表的链式存储结构中，每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域

2.优点：

（1）从任一结点出发可以快速找到其前驱结点和后继结点

（2）从任一结点出发可以访问其他结点

注意：双链表的密度比单链表小

3.双链表结点定义：

typedef struct DNode
{
    ElemType data;

    struct DNode *prior;    //指向前驱的结点

    struct DNode *next;    //指向后继的结点
   
} DLNode,*DLinkedList;

4.插入结点

理解：

(1)s的后继结点指向p的下一个结点(b)的地址

(2)p的下一个结点(b)的前驱指向s

以此类推....

5.删除结点

6.整体建立双链表

(1）头插法

（2）尾插法

（3）插入

（4）删除

二、循环链表

1.循环单链表：

将表中尾结点的指针域改为指向表头结点，整个链表形成一个环。由此表任一结点出发均可找到链表中其他结点。

2.循环双链表：

形成两个环