上次我们讲了顺序表，这次我们来讲链表
一.链表定义
链表是一种常见的数据结构，用于存储一系列元素。与数组不同，链表中的元素（节点）在内存中不必是连续的。每个节点包含数据部分和指向下一个节点的引用（指针）。链表的主要优点是插入和删除操作的时间复杂度为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函数找出相对应的位置
// 返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1
public 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;
}
// 返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1
public 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();
}
}