单链表的插入:
在第i个元素ai后面插入一个节点——
指针暂存变量为p,值为链表的a1。
- 找到ai和ai+1
while循环,循环计数j,条件是aj存在,并且jnext ,拿到下一个节点的指针,j++。
直到p指向ai。
- 创建插入节点x。注意点,用sizeof创建node,然后强制转化为LinkList形式,保险。
- 关键点:x节点—— x->next = p->next ,x要指向原本p指向的ai+1;p的下一个指向则是x,p->next = x。 这里的顺序不可转变,除非先把p->next的值暂存。
- 概念边界细化:!p || j>i ,return Error。
时间复杂度为O(n),在while循环那里,其他地方为O(1)。
单链表的删除:
删除第i个元素ai——
指针暂存变量为p,值为链表的a1。
- 找到ai-1和ai+1
while循环,循环计数j,条件是aj存在,并且j
直到p指向ai-1。
- ai-1 的next 指向 改为 ai+1,返回ai的值,删除ai
暂存ai:q = p->next
p->next = q->next
*e = q->data
free(q)
- 概念边界细化: !p->next || j> i-1
时间复杂度同上。
与顺序存储的事件复杂度来比较,插入删除操作:
插入删除,定位查找到ai的复杂度为O(n),但是,顺序存储里,每次查找完,后续还要移动n-i个元素的位置,事件复杂度为O(n),而单链表查找完后的复杂度为O(1)。