链表

Scroll Down

线性表的定义

线性表:由同类型数据元素构成有序序列的线性结构
1.表中元素个数称为线性表的长度
2.线性表没有元素时,称为空表
3.表的起始位置称为表头,表结束位置称为表尾

线性表的链式存储实现方式(链表)

单链表

单链表中的每个结点不仅包含值,还包含链接到下一个结点的引用字段。通过这种方式,单链表将所有结点按顺序组织起来
下面是链表的表现形式
链表表现形式
访问链表中的元素无法按照索引直接获取,需要遍历循环才能得到最终的索引的位置,所以获取数据的耗时为O(n)

添加和删除链表

链表插入和删除是不需要移动链表中的元素的,只需要修改链的引用就可以了

插入链表

添加操作 - 单链表
如果想在给定的结点 prev 之后添加新值
1.使用给定值初始化新结点 cur;
插入链表1
2.将 cur 的“next”字段链接到 prev 的下一个结点 next;
插入链表2
3.将 prev 中的“next”字段链接到 cur 。
插入链表3
这里切记2和3的顺序不能相反,如果先将prev.next = cur,这样你的cur.next就找不到原来prev.next这个节点了

删除链表

如果想要删除cur这个节点
1.先遍历找到cur这个节点的prev节点和next节点
删除链表1
2.将prev.next = cur.next,就删除了cur这个节点了
删除链表2