本节来学习单链表的实现。在链表的刷题中，单链表占主导地位，很多oj题都在在单链表的背景下进行；而且很多链表的面试题都是以单链表为背景命题。所以，学好单链表的基本操作很重要
目录
一.介绍单链表
1.链表及单链表
2.定义一个链表
二.实现单链表的功能
1.插入数据
2.打印链表
3.删除数据
4.查找某个元素
5.检测链表大小
6.完整的链表
一.介绍单链表
1.链表及单链表
（1）什么是链表
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
例如下面的这种数据结构，由一个个的结点组成。每个结点中存储着数据，又存储着其他结点的地址。
（2）什么是单链表
链表有三个特点：单向和双向、带头和不带头、循环和不循环；三三组合起来，一共8种情况（比如单向不带头不循环链表，就是本节的单向链表）。
单向和双向：单向表示每个结点只存后一个结点的地址；双向表示每个结点存放前后结点的地址。
区别：双向链表可以知道某个结点的前面结点，单向链表只能找到它后面的结点
带头和不带头：带头的链表会有一个固定的头结点（也称为哨兵位），所有操作都在头结点后面操作；不带头的链表则会自己定义一个结点用来表示当前链表的头，该结点也称为头结点，但是该头结点的位置是不停的变化的
区别：带头的链表，头结点的位置是固定不变的
循环和非循环：循环的链表，最后一个结点存放第一个结点的地址，非循环的链表最后一个结点存放的地址为null，也就是不指向任何的结点
区别：循环的链表也可以称为环，链表的遍历不会结束，而非循环会结束
本节介绍的单链表为：单向不带头非循环的链表，如下图的链表
2.定义一个链表
（1）定义一个链表（单独一个类）
public class MyList{
}
（2）将链表的功能包装称接口
public interface IList {
public void addFirst(int data);//头插
public void addLast(int data);//尾插
public void add(int index,int data);//任意位置插入
public boolean contains(int key);//检查key元素是否存在
public void remove(int key);//删除第一个key
public void removeAll(int key);//删除所有key
public int size();//求链表的长度
public void clear();//清空链表
public void show();//打印链表
}
（3）链表实现该接口并重写方法
public class MyList implements IList{
@Override
public void addFirst(int data) {
//头插
}
@Override
public void addLast(int data) {
//尾插
}
@Override
public void add(int index, int data) {
//指定位置插入
}
@Override
public boolean contains(int key) {
//查找key元素
}
@Override
public void remove(int key) {
//删除第一个key
}
@Override
public void removeAll(int key) {
//删除所有key结点
}
@Override
public int size() {
//求链表大小
}
@Override
public void clear() {
//清空链表
}
@Override
public void show() {
}
}
（4）定义链表的结点
我们将结点定义成一个内部类：包括数据域（data）和next域（存放下一个结点的地址）
public class MyList implements IList{
class ListNode {
public int data;//数据域
public ListNode next;
public ListNode(int data) {
this.data = data;
}
}
public ListNode head;//定位头的位置
@Override
public void addFirst(int data) {
//头插
}
@Override
public void addLast(int data) {
//尾插
}
@Override
public void add(int index, int data) {
//指定位置插入
}
@Override
public boolean contains(int key) {
//查找key元素
}
@Override
public void remove(int key) {
//删除第一个key
}
@Override
public void removeAll(int key) {
//删除所有key结点
}
@Override
public int size() {
//求链表大小
}
@Override
public void clear() {
//清空链表
}
@Override
public void show() {
}
}
这样一个链表的基本结构就定义完成，接下来就是实现链表的一些功能即可
二.实现单链表的功能
链表的功能大概有以下几种，插入数据（头插，尾插，随机插入），打印链表的数据，删除链表的数据，查找某个元素和监测链表的大小。
接下来我们慢慢了解
1.插入数据
（1）头插法
下面的是头插法的代码
public void addFirst(int data) {
//头插
ListNode node = new ListNode(data);
node.next = head;//
head = node;
}
第一步：需要创造一个新的结点出来
第二步：连接链表；分为两种情况：第一种是空链表的时候（一个结点都没有的时候），另一种是非空链表的时候。以上的代码都满足
（2）尾插法
尾插法的逻辑稍微复杂一点点，同样需要考虑链表的两种情况；空链表时需要单独讨论，而当链表非空时，则需要找链表的尾巴。
第一步：创造新的结点
ListNode node = new ListNode(data);
第二步：考虑空链表的情况
if(head == null) {
head = node;
return;
}
第三步：找链表的尾巴
这个注意，我们不能移动head，head需要保持不动，不然链表的头将不见。
ListNode cur = head;
while(cur.next!=null) {
cur = cur.next;
}
第四步：将新的结点连接到尾结点后面即可
cur.next = node;
完整的尾插法代码：
public void addLast(int data) {
//尾插
ListNode node = new ListNode(data);
if(head == null) {
head = node;
return;
}
ListNode cur = head;
while(cur.next!=null) {
cur = cur.next;
}
cur.next = node;
}
（3）随机位置插入
public void add(int index, int data)
随机位置插入，需要用户指定插入的位置和值；所以需要讨论以下的情况
第一步：创造新的结点
ListNode node = new ListNode(data);
第二步：检查用户指定插入的位置是否合法
if(index < 0 || index > size()) {
System.out.println("插入位置不合法");
return;
}
第三步：检查链表是否为空
if(head == null) {
head = node;
return;
}
第四步：检查是否为头插法
如果是头插法就直接调用头插法就可以，不需要再浪费时间去写这个代码。尾插法需要单独考虑，和普通插入当成一种即可。
if(index == 0) {
addFirst(data);
return;
}
第五步：找到插入位置的前一个结点
在单链表中，只能找前一个的位置，如果找的是后一个位置，将无法获取前结点的信息
int count = index-1;
ListNode cur = head;
while(count > 0) {
cur = cur.next;
count--;
}
此时的cur指向插入位置的前一个结点
第六步：插入新的结点
插入新的结点都是要求连接后面，再连接前面
node.next = cur.next;
cur.next = node;
完整代码：
public void add(int index, int data) {
//指定位置插入
ListNode node = new ListNode(data);
ListNode cur = head;
//1.检查位置是否合法
if(index < 0 || index > size()) {
System.out.println("插入位置不合法");
return;
}
//2.空链表情况
if(head == null) {
head = node;
return;
}
//3.头插法情况（index = 0）
if(index == 0) {
addFirst(data);
return;
}
//4.找前位置
int count = index-1;
while(count > 0) {
cur = cur.next;
count--;
}
//5.插入数据
node.next = cur.next;
cur.next = node;
}
2.打印链表
打印链表比较简单，就是需要将链表遍历一遍即可，同样的道理，不能动head
public void show() {
//打印
ListNode cur = head;
while(cur!=null) {
System.out.print(cur.data+" ");
cur = cur.next;
}
}
3.删除数据
删除数据分为两种：一种是删除一个key结点；另一种是删除所以的key结点。删除的参数都是根据结点的值来判断
下面我们一起来查看这两种的代码和思路
（1）删除第一个key结点
第一步：判断是否为空链表
如果是空链表的情况，无论如果都无法删除，直接返回就好
if(head == null) {
System.out.println("链表为空，无法删除");
return;
}
第二步：单独考虑头结点是否是目标结点
if(head.data == key) {
head = head.next;
return;
}
第三步：一边遍历链表一边删除结点
这里只需要遍历一遍就可以完成，不需要再找什么前结点；下面的代码是判断下一个结点是否为删除的结点，如果是，直接断开连接就好，不是则继续往下走
ListNode cur = head;
while(cur.next!=null) {
if(cur.next.data==key) {
cur.next = cur.next.next;//删除操作
return;
}else {
cur = cur.next;
}
}
第四步：链表中不存在key结点
System.out.println("没有该结点，删除失败！");
完整代码：
public void remove(int key) {
//删除第一个key
//1.空表
if(head == null) {
System.out.println("链表为空，无法删除");
return;
}
//2.头结点就是目标结点
if(head.data == key) {
head = head.next;
return;
}
//3.正常删除
ListNode cur = head;
while(cur.next!=null) {
if(cur.next.data==key) {
cur.next = cur.next.next;//删除操作
return;
}else {
cur = cur.next;
}
}
//4.找不到
System.out.println("没有该结点，删除失败！");
}
（2）删除所有的key结点
删除所有的结点是在删除一个key结点的前提下改进即可，删除一个key结点时，直接返回了，然后删除所有的key，我们不返回就好。下面分三步
第一步：判断是否为空链表
if(head == null) {
System.out.println("链表为空，无法删除");
return;
}
第二步：删除头结点后面的所有key结点
下面的代码无法删除头结点，所以头结点的情况单独考虑并且放在最后面
ListNode cur = head.next;//需要删除的结点
ListNode prev = head;//删除结点的前一个
//2.删除中间的结点
while(cur != null) {
if(cur.data != key) {
prev = cur;//让prev走到cur的位置
cur = cur.next;//cur往下走
}else {
prev.next = cur.next;
cur = cur.next;
}
}
第三步：删除头结点
if(head.data == key) {
head = head.next;
}
完整代码：
public void removeAll(int key) {
//删除所有key结点
//1.检查空链表情况
if(head == null) {
System.out.println("链表为空，无法删除");
return;
}
ListNode cur = head.next;//需要删除的结点
ListNode prev = head;//删除结点的前一个
//2.删除中间的结点
while(cur != null) {
if(cur.data != key) {
prev = cur;//让prev走到cur的位置
cur = cur.next;//cur往下走
}else {
prev.next = cur.next;
cur = cur.next;
}
}
//3.删除头结点
if(head.data == key) {
head = head.next;
}
}
4.查找某个元素
查找某个元素是否存在时，根据结点的值去查找
如果结点存在，返回true；不存在则返回false
public boolean contains(int key) {
//查找key元素
ListNode cur = head;
while(cur!=null) {
if(cur.data == key) {
return true;
}
cur = cur.next;
}
return false;
}
5.检测链表大小
求链表的结点个数只需要遍历一遍链表即可，每走到一个结点的位置，计数器就家加1，最后返回即可
public int size() {
//求链表大小
ListNode cur = head;
int count = 0;
while(cur!=null) {
count++;
cur = cur.next;
}
return count;
}
6.完整的链表
public class MyList implements IList{
class ListNode {
public int data;//数据域
public ListNode next;
public ListNode(int data) {
this.data = data;
}
}
public ListNode head;//定位头的位置
@Override
public void addFirst(int data) {
//头插
ListNode node = new ListNode(data);
node.next = head;//
head = node;
}
@Override
public void addLast(int data) {
//尾插
ListNode node = new ListNode(data);
if(head == null) {
head = node;
return;
}
ListNode cur = head;
while(cur.next!=null) {
cur = cur.next;
}
cur.next = node;
}
@Override
public void add(int index, int data) {
//指定位置插入
ListNode node = new ListNode(data);
//1.检查位置是否合法
if(index < 0 || index > size()) {
System.out.println("插入位置不合法");
return;
}
//2.空链表情况
if(head == null) {
head = node;
return;
}
//3.头插法情况（index = 0）
if(index == 0) {
addFirst(data);
return;
}
//4.找前位置
int count = index-1;
ListNode cur = head;
while(count > 0) {
cur = cur.next;
count--;
}
//5.插入数据
node.next = cur.next;
cur.next = node;
}
@Override
public boolean contains(int key) {
//查找key元素
ListNode cur = head;
while(cur!=null) {
if(cur.data == key) {
return true;
}
cur = cur.next;
}
return false;
}
@Override
public void remove(int key) {
//删除第一个key
//1.空表
if(head == null) {
System.out.println("链表为空，无法删除");
return;
}
//2.头结点就是目标结点
if(head.data == key) {
head = head.next;
return;
}
//3.正常删除
ListNode cur = head;
while(cur.next!=null) {
if(cur.next.data==key) {
cur.next = cur.next.next;//删除操作
return;
}else {
cur = cur.next;
}
}
//4.找不到
System.out.println("没有该结点，删除失败！");
}
@Override
public void removeAll(int key) {
//删除所有key结点
//1.检查空链表情况
if(head == null) {
System.out.println("链表为空，无法删除");
return;
}
ListNode cur = head.next;//需要删除的结点
ListNode prev = head;//删除结点的前一个
//2.删除中间的结点
while(cur != null) {
if(cur.data != key) {
prev = cur;//让prev走到cur的位置
cur = cur.next;//cur往下走
}else {
prev.next = cur.next;
cur = cur.next;
}
}
//3.删除头结点
if(head.data == key) {
head = head.next;
}
}
@Override
public int size() {
//求链表大小
ListNode cur = head;
int count = 0;
while(cur!=null) {
count++;
cur = cur.next;
}
return count;
}
@Override
public void clear() {
//清空链表
head = null;
}
@Override
public void show() {
//打印
ListNode cur = head;
while(cur!=null) {
System.out.print(cur.data+" ");
cur = cur.next;
}
}
}
接口：
public interface IList {
public void addFirst(int data);//头插
public void addLast(int data);//尾插
public void add(int index,int data);//任意位置插入
public boolean contains(int key);//检查key元素是否存在
public void remove(int key);//删除第一个key
public void removeAll(int key);//删除所有key
public int size();//求链表的长度
public void clear();//清空链表
public void show();//打印链表
}
实例化链表对象：
public static void main(String[] args) {
MyList myList = new MyList();//实例化链表对象
myList.addLast(8);
myList.addLast(1);
myList.addLast(4);
myList.show();
}
本节单链表的实现就到这里了，快去自己模拟实现一下吧！
推荐文章
发表评论