单向链表的一些基本操作（Java）
上次我们讲了顺序表，这次我们来讲链表
一.链表定义
链表是一种常见的数据结构，用于存储一系列元素。与数组不同，链表中的元素（节点）在内存中不必是连续的。每个节点包含数据部分和指向下一个节点的引用（指针）。链表的主要优点是插入和删除操作的时间复杂度为O(1)，但访问特定元素的时间复杂度为O(n)。
链表分类：
1.单向链表（Singly Linked List）：
a)在单向链表中，每个节点包含一个数据域和一个指向下一个节点的引用（指针）。
这是最简单的链表形式，只能从头节点遍历到尾节点。
b)优点：实现简单；节省空间（每个节点只需要一个额外的指针）。
c)缺点：不能反向遍历；插入和删除操作需要找到前驱节点。
2.双向链表（Doubly Linked List）：
a)双向链表中的每个节点除了包含指向下一个节点的引用外，还有一个指向前一个节点的引用。
b)优点：可以从两个方向遍历链表；插入和删除操作更加方便。
c)缺点：每个节点需要两个额外的指针，因此比单向链表占用更多空间。
3.循环链表（Circular Linked List）：
a)循环链表可以是单向的也可以是双向的，其特点是最后一个节点的“下一个”指针不是指向null，而是回指到链表的第一个节点，形成一个闭环。
b)优点：便于实现循环遍历；没有明确的尾节点，处理起来更方便。
c)缺点：如果不小心处理，可能会陷入无限循环。
今天我们来讲单向链表
二.单向链表
单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。
在一个链表中，头指针的作用就像是一张地图上的起点标示，它帮助我们知道链表的起始位置在哪里。
头指针总是指向链表的第一个节点（即首节点）。通过这个指针，我们可以访问链表中的所有元素。
1.结点的API设计
//结点类class Node<T>{T data; //存储数据Node<T> next;//下一个节点//构造方法public Node(T date, Node<T> next){this.data = date;this.next = next;}}2.单向链表的API设计
初始化单向链表
class Linklist <T>
{//结点类class Node<T>{T data; //存储数据Node<T> next;//下一个节点//构造方法public Node(T date, Node<T> next){this.data = date;this.next = next;}}//创造头结点Node<T> head;//链表长度int size;//构造方法public Linklist(){this.head = new Node(null, null);this.size = 0;}
}1.清空链表
思路分析：想清空链表，就让头结点的引用域为null ,就会与后面的自动断开，再令长度为0
//清空方法public void clear(){head.next = null;size = 0;}2.判断链表是否为空
思路分析：返回查看长度是否为0，是的话返回true，否返回false
//判断链表是否为空public boolean isEmpty(){return size == 0;}3.求链表长度
思路分析：直接返回长度即可
//求链表长度方法public int length (){return size;}4.找到指定位置的元素
思路分析1.先检查位置是否合规
2.创建一个变量来取代头结点的引用
3.通过循环遍历，找到位置所处的结点
4.最后返回结点的数据
public T get( int index){//检查位置是否合规if(index < 0 || index >= size){throw new RuntimeException("输入位置违规");}Node<T> node = head.next;for(int i = 0; i < index; i++){node = node.next;}return node.data;}5.在末尾插入元素
思路分析：
1.创建一个变量代替头结点
2.通过循环找到最后一个结点，根据最后一个结点的引用为null来写循环条件
3.创建新结点，将原来最后一个结点的引用指向新结点
//插入元素（末尾）public void add(T data){//创建一个变量来代替头结点Node newNode = head;//遍历找到最后一个结点的位置，通过最后一个结点的指针值为null，用while来寻找while(newNode.next != null){newNode = newNode.next;}//创建新结点Node newNode1 = new Node(data, null);newNode.next = newNode1;size++;}6.在对应位置插入元素
思路分析：
根据这个简易流程图我们可知：
1.创建一个新的变量表示头结点
2.通过循环遍历找到位置的前一个结点所指向的值
3.创建新结点（也就是值为4所在的这个结点）将新结点指向原来前一个位置结点所指向的值
（在本图中既让4.next =1.next,1.next在等式右边代表所指向下一个结点的值，左边则是变量接受这个值）
4.再将原来位置的前一个结点指向新结点
注意！！！
在执行第三四步代码时，一定要先把新结点指向原来前一个位置结点所指向的值，再把原来前一个结点指向新结点的值
//在指定位置插入元素public void insert(int index, T data){Node neeNode=head;//找到指向i位置的前一个值的结点for(int i = 0; i < index; i++){neeNode = neeNode.next;}//指向i位置的值的结点Node currentNode=neeNode.next;//创建新结点，将新结点指向原来i位置的前一个位置所指向的结点Node newNode2 = new Node(data, currentNode);//将原来位置的前一个结点指向新结点的数据neeNode.next = newNode2;size++;}7.删除指定位置的元素
思路分析：
根据简易流程图我们可知：
1.首先创建一个变量代表头结点
2.用循环找到指向指定位置前一个值的结点
3.找到指向i位置的值的结点
4.找到i位置指向下一个位置的值的结点
5.将i位置下一个位置的值指向i位置前一个的结点
//删除指定位置的元素，并返回被删除的元素public Object remove(int index){Node curr=head;//找到指向i位置前一个位置的值的结点for(int i = 0; i < index; i++){curr = curr.next;}//找到指向i位置的值的结点Node newNode = curr.next;//找到i位置指向下一个位置的值的结点Node nextNode = newNode.next;//将i位置下一个位置的值指向i位置前一个的结点curr.next = nextNode;size--;return newNode.data;}8.找到值对应的位置
思路分析：用一个循环和equal函数找出相对应的位置
// 返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1public int indexOf(T t){//循环遍历找到值所对应的索引Node<T> current = head;int index = -1;while (current != null){if (current.data != null && current.data.equals(t)){return index;}current = current.next;index++;}return -1;}练习题
添加以下学生姓名到顺序表中：“张三”, “李四”, “王五”，“赵六”。
在“李四”后面插入“李四”（注意：需要先找到“李四”的位置）
删除“李四”并从顺序表中移除
查找“李四”在顺序表中的位置（索引）
打印最终顺序表中的所有学生姓名
清空顺序表并验证它确实为空
完成代码
class Linklist <T>
{//结点类class Node<T>{T data; //存储数据Node<T> next;//下一个节点//构造方法public Node(T date, Node<T> next){this.data = date;this.next = next;}}//创造头结点Node<T> head;//链表长度int size;//构造方法public Linklist(){this.head = new Node(null, null);this.size = 0;}
// ------------------------------------------------------------//清空方法public void clear(){head.next = null;size = 0;}//求链表长度方法public int length (){return size;}//判断链表是否为空public boolean isEmpty(){return size == 0;}//找到指定位置的元素public T get( int index){//检查位置是否合规if(index < 0 || index >= size){throw new RuntimeException("输入位置违规");}Node<T> node = head.next;for(int i = 0; i < index; i++){node = node.next;}return node.data;}//插入元素（末尾）public void add(T data){//创建一个变量来代替头结点Node newNode = head;//遍历找到最后一个结点的位置，通过最后一个结点的指针值为null，用while来寻找while(newNode.next != null){newNode = newNode.next;}//创建新结点Node newNode1 = new Node(data, null);newNode.next = newNode1;size++;}//在指定位置插入元素public void insert(int index, T data){Node neeNode=head;//找到指向i位置的前一个值的结点for(int i = 0; i < index; i++){neeNode = neeNode.next;}//指向i位置的值的结点Node currentNode=neeNode.next;//创建新结点，将新结点指向原来i位置的前一个位置所指向的结点Node newNode2 = new Node(data, currentNode);//将原来位置的前一个结点指向新结点的数据neeNode.next = newNode2;size++;}//删除指定位置的元素，并返回被删除的元素public Object remove(int index){Node curr=head;//找到指向i位置前一个位置的值的结点for(int i = 0; i < index; i++){curr = curr.next;}//找到指向i位置的值的结点Node newNode = curr.next;//找到i位置指向下一个位置的值的结点Node nextNode = newNode.next;//将i位置下一个位置的值指向i位置前一个的结点curr.next = nextNode;size--;return newNode.data;}// 返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1public int indexOf(T t){//循环遍历找到值所对应的索引Node<T> current = head;int index = -1;while (current != null){if (current.data != null && current.data.equals(t)){return index;}current = current.next;index++;}return -1;}
}public class StudentMs2{public static void main(String[] args){Linklist<String> ll=new Linklist<>();ll.add("张三");ll.add("李四");ll.add("王五");ll.add("赵六");int i=ll.indexOf("李四");System.out.println("李四的位置："+ i);ll.insert(1,"李四");ll.remove(1);System.out.println("最终的学生名单:");for(int i1=0;i1<ll.length();i1++){System.out.println(ll.get(i1));}ll.clear();System.out.println("清空后的长度 "+ll.length());ll.isEmpty();}}