线性表之静态链接，循环链表，双向链表

单链接的整表创建

 经常写swift写的没有写分号的习惯了~如果有看到的人见谅哈

• 头插法
  *L = (LinkList)malloc(sizeof(Node)) (*L)->next = NULL for(int i = 0;i<n;i++){ p = (LinkList)malloc(sizeof(Node)) p->next = rand()%100 +1 p ->next = (*L)->next; (*L)->next = p }
• 尾插法(外部一个指针记录当前最后一个元素的位置。不断更新最后一个元素)
  r = *L for(int i =0 ;i<n;i++){ p = (Node*)malloc(sizeof(Node)) p->data = 1 p ->next = r r = p } r->next = NULL

单链表的整表删除

• 声明 p,q,
• 将第一个节点赋值给p
• 循环 q记录p—>next,释放p,p =q
  最后使头节点的指针域为NULL

静态链表

在删除和删除操作的时候只需要修改游标，不需要移动元素，从而改进了顺序存储结构中插入和删除需要移动大量元素的缺点

缺点：

• 没有解决连续分配带来的表长难以确定的问题
• 失去了顺序存储结构 随机存取的特性

静态链表是为了 没有指针的高级语言设计的一种实现单链接能力的方法

循环链表

单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成了一个环。这种头尾相连的结构称为循环链表。

两个循环链表 合并成一个循环链表

//记录rearA的next的指向
p = rearA->next;

//rearA的末尾指向rearB的第一个结点。不是头结点

rearA->next = rearB->next->next;

q = rearB->next;

rearB->next = p ;

free(q);

双向链表

双向链表 是在单链表的每个结点中，再设置一个指向其前驱结点的指针域

单向链表可以存在循环链表。那么双向链表也可以存在循环链表。

双向链表的插入操作

• 改变插入元素的前驱和后继
• 改变后继的前驱
• 改变前驱的后继

s->prefix = p;

s->next = p->next;

p->next->prefix = s;

p->next = s

双向循环链表的删除操作

• p->prefix->next = p->next
• p->next->prefix = p->prefix

总结

双向链表对于单链表而言要复杂，因为多了prefix指针，对于插入和删除时候要格外小心。