【2022.07.11 星期一】考研日记_删除非空单链表的表尾元素

上午高数，660+880
下午408，①数据结构②操作系统③计组④计网
晚上英政，单词+翻译+网课，没做1000题

知识点积累：
①删除链表的最后一个元素：与表长有关
因为删除尾巴，需要把倒数第二个结点（尾的前驱节点）的指针域设置为NULL，需要从头遍历，直到找到它。花费时间是O（n）
表尾插一个新元素：与表长无关（直接插，不用管前驱）

②带/不带头节点的单链表的判定空表条件
带头节点：头指针head指向头节点，头节点的next指向第一个元素节点
【head -> next = NULL;】
不带头节点：头指针head“直接”指向第一个元素节点
【head == NULL;】

③双链表优点：
单链表访问后继节点O（1），访问前驱节点O（n）。
双链表可以快速找到前驱节点，插入删除都是O（1）。

④双链表：【p后面插s】
s->next = p->next; //s放在p的屁股后面
p->next->prior = s; //回指s
s->prior = p; //s双向指向p
p->next = s; //回指s
【p前面插s】
p->prior->next = s;
s->next = p;
s->prior = p->prior;
p->prior = s;