数据结构与算法---动态链表（1）LinkedList
分类:
文章
•
2025-04-29 19:30:58
- 链表的定义
我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。这两部分信息组成数据元素ai的存储映像，称为结点。
因为链表中的每一个结点只包含一个指针域，所以叫做单链表
- 头结点与头指针
头结点是指链表中的第一个节点，有真实头结点和虚拟头结点之分
真实头结点：其第一个结点用于存储数据
虚拟头结点：其第一个节点不许存储数据
头指针：仅仅是一个引用变量，存储头结点地址的指针而已
尾指针：同头指针 ，不过时链表中最后一个结点的指针而已
- 线性表的链式存储结构（LinkedList)–基于List实现（用动态链表实现的线性表 链表）
链表内中有一个结点的内部类，所以先实现他的内部类
现在来实现链表的内容
空表状态（head = rear)
插入元素—头插法
把头结点的下一跳给新元素的下一跳，将新元素的地址给头结点的下一跳，尾指针往后移
当链表为空时第一个元素进来之后尾指针需要移动，之后就不需要在移动
插入元素—尾插法
将新元素的地址直接给尾指针所指的结点的下一跳，然后尾指针后移
插入元素–头插尾插结合
当链表为空时，第一个元素无论是头插还是尾插其结果都是一样的
插入元素—一般插入
在A元素和B元素之间插入D元素
将A的下一条给D的下一条，然后将D的地址给A的下一条—（相当于以A为头结点的头插法）
删除元素–删头
将头指针下一跳所指的元素删除，将B的地址直接给头指针的下一跳 ，
如果只剩一个元素时，还想继续删除，此时将A的下一条指向第一个元素的下一条，然后移动尾指针
增加元素
1.先判断角标是否合法
2.将元素用结点包含起来
3.先判断是否为空，在判断是那种形式的插入，最终size++。
得到角标处元素
1.判断是否为空
2.判断角标是否合理
3.若都没有问题，则返回index处的数据
修改指定角标处的元素
1.判断是否为空表
2.判断角标是否越界
3.然后循环寻找要修改处的位置，将该位置的数据修改
查找元素
删除元素
1.判断是否为空
2.判断角标是否合法
3.判断是哪一种删处方法
移除元素
先判断是否找到元素，如可以找到则移除，或者提示没有找到
重写
迭代器
