缥缈峰

线性表是《数据结构》正文第一部分的内容，是很简单的，也是很重要的基础知识。对于这部分知识大家应该记得滚瓜烂熟。
     线性表的实现分为顺序（数组）和链表，顺序实现过于简单，这里就不费口水了。
     链表实现有三种类型： 1)单向链表 2)循环链表 3)双向链表


链表的实现有几种形式：（主要是两种表示空节点的方式：NULL和DummyNode哑节点)

A)单链表，头节点NULL为空，尾节点NULL为空
初始化：head = NULL;
x节点后插入t节点：if (x == NULL) { head = t; } else { t->next = x->next; x->next = t;}
删除x后的节点：t = x->next; if (t) { x->next = t->next; free(t); }
遍历： t = head; while(t) { ...; t = t->next; }
是否为空：if (head == NULL) {...}


B)单链表，头节点哑节点为空，尾节点NULL为空
初始化：head = malloc(); head->next = NULL; // 浪费一个节点空间
x节点后插入t节点：t->next = x->next; x->next = t; // 少做一次判断
删除x后的节点：（同A）
遍历： （同A）
是否为空：if (head->next == NULL) {...}


C)单链表，头节点哑节点为空，尾节点哑节点为空 (这个很少用)
初始化：head = malloc(); z = malloc(); head->next = z; z->next = z; // 浪费两个节点空间
x节点后插入t节点：（同B）
删除x后的节点：（同B）
遍历： t = head->next; while (t != z) { ...; t = t->next; }
是否为空：if (head->next == z) {...}


D)循环链表
初始化：head = malloc(); head->next = head;
x节点后插入t节点：（同B）
删除x后的节点：（同B）
遍历： t = head; do { ...; t = t->next; } while (t != head);
是否为空：if (head->next == head) {...}


E)双向循环链表
初始化：head = malloc(); head->next = head->prev = head;
x节点后插入t节点：t->next = x->next; t->prev = x; x->next->prev = t; x->next = t;
删除x节点：x->prev->next = x->next; x->next->prev = x->prev; free(x);
遍历：（同D）
是否为空：（同D）



线性表应用：
1)单向链表
合并两个有序单向链表


逆转链表



2)循环链表
Josephus问题



转载请注明出处，谢谢！