1.什么是单链表
链表里的数据是以节点的方式表示的，每一个结点的组成是由：元素+指针来组成的，元素就是存储数据里的存储单元，指针就是用来连接每一个结点的地址数据。这个以结点的序列来表示线性表被称作为单链表。
单链表是一种链式储存结构。在物理储存单元不连续，非顺序。
- 结点里的数据域是用来存储数据元素的
- 指针是用于指向下一个具有相同结构的结点
- 因为只有一个指针结点，故而被称为单链表
2.单链表的实现
末尾增加元素
void add(T data)
指定下标增加元素
void add(int index,T data)
删除指定下标元素
void delete(int index)
获取指定下标的元素
T get(int index)
修改指定下标的元素
void update(int index,T data)
遍历输出所有元素
void show()
获取链表的长度
int length()
（1）定义数据节点实体
（2）向链表末尾增加元素
（3）指定下标向链表增加元素
（4）删除指定下标元素的数据
（5）修改指定下标的元素
（6）获取指定下表的元素
（7）循环遍历输出
（8）获取当前有效的元素个数
3.单链表测试
（1）整体代码实现
public class SingleLinkedList<T> { /** * 定义头节点 */ public Node<T> head = new Node<>(null); /** * 链表有效元素个数 */ private int length=0; /** * 向单链表中添加一个元素 * @param data */ public void add(T data){ //定义当前数据 Node<T> nodeData = new Node<>(data); //定义辅助指针 Node<T> cur = head; //while 循环不断遍历找到最后一个节点 while (cur.next != null) { //只要有下一个节点，辅助指针就向下移动一位 cur = cur.next; } //while循环之后，cur已经是最后一个节点，将data赋值到cur的下一个节点上 cur.next = nodeData; //整体链表长度++ length++; } /** * 向单链表中添加一个元素 * @param data */ public void add(int index,T data){ //判断index是否合法 if(index <0 || index >length){ System.out.println("index不合法"); return; } //定义当前数据 Node<T> nodeData = new Node<>(data); //定义辅助指针 Node<T> cur = head; //找到当前index的元素 for (int i = 0; i < index; i++) { cur = cur.next; } //将当前节点的next设置成cur的next nodeData.next = cur.next; //将cur.next设置成nodeData（当前节点） cur.next = nodeData; //整体链表长度++ length++; } /** * 遍历输出链表中全部节点 */ public void show(){ //定义辅助指针 Node<T> cur = head; //判断链表中是否存在元素 if (cur.next == null){ System.out.println("当前单向链表中元素为空"); return; } while (cur.next != null){ System.out.print(cur.next.data+" "); cur = cur.next; } System.out.print("\n"); } /** * 修改指定下标的数据 * @param index * @param data */ public void update(int index,T data){ Node<T> cur = head; if(index > length){ System.out.println("当前index查过边界"); return; } //遍历寻找指定index的节点 for (int i = 0; i <= index; i++) { cur = cur.next; } //找到之后将新的data赋值上去 cur.data = data; } /** * 删除指定下标元素 * @param data */ public void delete(int index){ Node<T> cur = head; if(index > length){ System.out.println("当前index超过边界"); return; } //遍历寻找指定index的节点 for (int i = 0; i < index; i++) { cur = cur.next; } //找到之后将新的data赋值上去，将后一个data赋值到当前节点上 cur.data = cur.next.data; //将当前节点的next变成当前节点的next.next相当于将当前元素的next节点删掉 cur.next = cur.next.next; //单链表整体有效元素减一 length--; } /** * 获取指定下标元素的数据 * @param index * @return */ public T get(int index){ //校验参数是否合法 if(index<0 || index>length){ System.out.println("当前index超过边界"); } //定义辅助节点 Node<T> cur = head; //找到对应下标的node for (int i = 0; i <=index; i++) { cur = cur.next; } //返回node.data return cur.data; } /** * 获取单链表的长度 * @return */ public int length(){ return this.length; } /** * 内部节点类 * @param <T> */ class Node<T>{ /** * 定义数据 */ public T data; /** * 定义下一个节点的 */ public Node<T> next; public Node(T data) { this.data = data; } }}
（2）测试代码
public class Main { public static void main(String[] args) { SingleLinkedList<Integer> singleLink = new SingleLinkedList<>(); //增加元素 singleLink.add(1); singleLink.add(2); singleLink.add(3); System.out.print("新增之后："); singleLink.show(); //删除元素 singleLink.delete(0); System.out.print("删除index为0之后："); singleLink.show(); //修改元素 singleLink.update(0,9); System.out.print("修改index为0之后："); singleLink.show(); //获取单链表的长度 int length = singleLink.length(); System.out.println("单链表的长度："+length); //获取指定下标的数据 System.out.println("获取指定下标的数据："+singleLink.get(1)); //指定下标插入数据 singleLink.add(1,6); System.out.print("在index为1位置插入数据之后："); singleLink.show(); }}
4.链表的优缺点
- 优点：
- 链表的内存空间不连续。
- 如果知道要处理节点的前一个位置，则进行插入和删除的复杂度为O(1);
- 如果不知道要处理节点的前一个位置，则进行插入和删除的复杂度为O(N)。
- 头插、头删的效率高，时间复杂度是O(1)。
- 没有空间限制，不会溢出，可以存储很多元素。
- 缺点：
- 链表不支持随机访问，查找元素效率低，需要遍历节点，时间复杂度是O(n)。