n-i

顺序

顺序表,复杂度为O(n) 链表,复杂度为O(1)

如果是直接插入的话,是无法做到的,因为不知道p节点的前序指针, 但是可以通过:现将s节点插入到p节点的后面,然后再交换p节点与s节点的数据的方式来实现"插入" 即: s->next = p->next; p->next = s; s->data <--> p->data

L->next = L->prior = L

带有头结点的双向循环链表L为空标的条件是: L的next 和 prior都为L

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

py->next = px -> next; px->next = py;

L -> next -> next = L && L->next != L L -> next != L,是为了防止出现只有一个头结点的情况

O(1) 在值为x的节点之后插入节点,需要找到值为x的节点,时间复杂度为O(n),然后插入节点,时间复杂度为O(1)

单链表,双链表 根据指针的连接方式,将链表分为:动态链表,静态链表

f->next = p->next; f->prior = p; p->next->prior = f; p->next = f;

指针

节点在物理存储上的相邻关系

4(待插入节点的两个指针也计算在内) , 2(待插入节点的一个指针也计算在内)

从任意节点出发,都能访问到链表的全部元素

L->next->next == L && L->prior->prior == L && L ->next != L

p->next != null

L->next == L && L->prior == L

将链表listb连接在lista的尾部, for循环的作用是将p指向lista的最后一个节点

BEI FHDA

视频讲解连接:https://www.bilibili.com/video/av843754?from=search&seid=16128174079900509637 链表的反转:

p->next->next == L

相邻元素相比较,逆序交换,算法结束时,最大元素调整到链表的末尾 12 7 10 5 9 15

重点在于: 不是将h节点当做循环指针,而是将h->next节点当做循环的指针 h->next节点,p节点,q节点,三个指针实现了反转,最后同样形成了一个带有头结点的链表

q指针的作用就是始终指向pa节点的前序节点,仅仅是为了在遇到常数的时候,删除pa节点用的,因为这个时候,需要调用free(pa),就需要知道前序节点,而对于正常的情况(求导之前不为0),是不需要pa的 题中说了头结点,就一定有头结点,而且头指针一定指向头结点,头结点是没有数据的,本题为循环链表,有头结点,所以第一个数据从头结点的下一个节点开始,且while循环的终止条件为,当pa != 头结点