内容 来自 王道

有错误请指出，谢谢

双链表

1.定义：

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

2.按值查找 与 按位查找

增加前驱指针不改变查找方式，只是查找的方式增加了

3.双链表的插入操作 –> 画图即可解决

在双链表中的p结点之后插入newnode
个人背诵，请勿相信：从p开始，后前前后
newnode->next=p->next;
p->next->prior=newnode;
newnode->prior=p;
p->next=newnode;


在双链表中的结点之前加入newnode
从p的上一个结点开始： 后前前后
p->prior->next=newnode;
newnode->prior=p->prior;
p->prior=newnode;
newnode->next=p;

4.双链表的删除操作

删除双链表中结点p之后的后继结点q

p->next=q->next;
q->next->prior=p;
free(q);


删除双链表中结点p之前的前驱结点q
**
q->prior->next=p;
p->prior=q->prior;
free(q);

循环链表：

1.循环单链表
单链表与循环单链表的区别： 循环链表的最后一个结点的指针不是NULL,而是指向头结点，从而使整个链表构成一个环

循环单链表中，表尾结点*r的next域指向L,故表中没有指针域为NULL的结点，因此，
循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针

循环单链表不设头指针而设尾指针r,头指针就是r->next,对表头与表尾进行操作都只需要O(1)的时间
若设头指针，则需要O(n)的时间

2.循环双链表
当循环双链表为空表时，头结点的prior域与next域都等于L

静态链表：

1.定义

用数组下标（游标）来代替指针
和顺序表一样，静态链表也要预先分配一块连续的存储空间

#define MaxSize 50
typedef struct{
    ElemType data;
    int next;
}SLinkList [MaxSize];

静态链表以next==-1作为结束的标志
静态链表的插入、删除与动态链表相同，只需要修改指针，而不需要移动元素