目录
什么是单链表？
带头结点的单链表
不带头结点的单链表
模拟实现不带头结点的单链表
定义结点类
初始化
头插法创建单链表
尾插法创建单链表
打印单链表
单链表的查找
获取单链表的长度
按位置寻找前驱结点
单链表的插入
修改指定位置的值
按值寻找前驱结点
删除第一次出现的key值
删除所有的key值
清空单链表
完整代码
单链表是一种链式存取的数据结构，用一组任意的存储单元存放线性表中的数据元素。链表中的数据是以结点表示的，每个结点由元素和指针组成。
在Java中我们可以将单链表定义成一个类，将单链表的基本操作定义为类中的方法，而每个结点即为类的实例化对象，每个对象中都有“元素值”和“下一个结点地址”两个属性，通过“下一个结点地址”这个属性来实现链表的链接.
单链表分为带头结点的单链表和不带头结点的单链表.
单链表虽然不能像顺序表那样实现随机存取，但单链表可以实现在任意位置插入或删除，不需要像顺序表那样需要移动大量元素才能完成，且单链表的地址是随机的，不一定是一段连续的空间.
带头结点的单链表结构如上，每个结点的上半部分是元素值，下半部分是下一个结点的地址.
因为该链表带头结点，头结点元素值部分不存储数据，下一个结点的地址存储链表的第一个元素，在进行访问时，head.next为单链表的第一个元素.
不带头结点的单链表的结构如上所示，此时head即为单链表的第一个结点.
class Node{
public int value;//存储结点的值
public Node next;//用来存储下一个结点的地址
public Node(int value) {
this.value = value;
}
}public class SingleLinkedList {
public Node head;//定义单链表的第一个结点，编译器自动初始化为null
public int usedSize;//用来记录单链表的长度
}假设单链表目前有四个元素，要在首位置插入一个结点，首先初始化一个结点node，其地址为0x123，需要令node.next = head如下图所示：
经过调整后的单链表为
具体代码如下：
public void addFirst(int data){
Node node = new Node(data);
if(this.head == null){
this.head = node;
} else {
node.next = this.head;
this.head = node;
}
this.usedSize++;
}尾插法插入的原理其实与头插法类似，只是尾插法需要先找到链表中的最后一个结点，之后直接将新建结点放到链表最后面即可.首先Node cur = head，让其遍历单链表，找到最后一个结点，之后直接cur.next = node即完成了单链表的尾插法.
//尾插法
public void addLast(int data){
Node node = new Node(data);
if(this.head == null){
this.head = node;
} else {
Node cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = node;
}
this.usedSize++;
}利用while语句遍历一遍单链表即可.
//打印单链表
public void myToString(){
Node cur = this.head;
while(cur != null){
System.out.print(cur.value + " ");
cur = cur.next;
}
System.out.println();
}利用while语句遍历单链表，如果找到返回true，否则返回else.
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
Node cur = this.head;
while(cur != null){
if(cur.value == key){
return true;
}
cur = cur.next;
}
return false;
}可以通过两种方法得到：
①直接输出usedSize；
//得到单链表的长度
public int length(){
return this.usedSize;
}
②利用while语句遍历单链表
//得到单链表的长度
public int length(){
Node cur = this.head;
int length = 0;
while(cur != null){
length++;
cur = cur.next;
}
return length;
}
//寻找待插入位置的前驱结点
public Node getIndex(int pos){
Node cur = this.head;
int index = 0;
while(index != pos-1){
cur = cur.next;
index++;
}
return cur;
}在进行插入操作时，首先需要判断插入位置是否合法，在对特殊位置进行处理：
①如果插入位置为0，则直接利用头插法进行插入；
②如果插入位置为单链表的尾部，直接利用尾插法进行插入；
在进行正常插入时，首先需要找到待插入位置的前驱结点，之后进行插入即可.
例如要插入在第二个位置，则：
//任意位置插入,第一个数据节点为0号下标
public void insert(int pos, int data){
if(pos < 0 || pos > this.usedSize){
throw new RuntimeException("插入位置不合法");
}
if(pos == 0){
addFirst(data);
return;
}
if(pos == this.usedSize){
addLast(data);
return;
}
Node node = new Node(data);
Node prev = getIndex(pos);
node.next = prev.next;
prev.next = node;
this.usedSize++;
}利用while语句遍历找到要修改的位置，找到后利用cur.value修改即可.
//修改指定位置的值
public void modify(int pos, int data){
if(head == null){
throw new RuntimeException("链表为空，无法进行修改");
}
if(pos < 0 || pos > this.usedSize-1){
throw new RuntimeException("操作位置不合法");
}
Node cur = this.head;
int index = 0;
while(index != pos){
cur = cur.next;
index++;
}
cur.value = data;
} //寻找关键字key的前一个结点
private Node getPrev(int key){
Node prev = this.head;
while(prev.next != null) {
if (prev.next.value == key) {
return prev;
}
prev = prev.next;
}
return null;
}当要删除的key值在单链表的第一个位置时，直接head = head.next即可，如果不在第一个位置，首先需要找到该值的前驱结点，之后再进行删除操作即可.
假如待删除的key值为35，则：
//删除第一次出现关键字为key的节点
public void remove(int key){
if(this.head == null){
throw new RuntimeException("链表为空，无法进行操作");
}
if(this.head.value == key){
//如果链表为空或第一个结点为删除的值
this.usedSize--;
this.head = this.head.next;
return;
}
Node prev = getPrev(key);
prev.next = prev.next.next;
this.usedSize--;
}利用循环遍历一遍单链表实现删除所有key值操作
利用定义出 prev和cur，prev存储首结点的地址
假如待删除的key值为28，则利用cur遍历一遍单链表，如果cur.value == key值，则直接利用prev.next = cur.next完成删除操作.
如果cur.value != key，则prev = cur; cur = cur.next; 两个都往后顺移一位，如果遇到cur.value == key这种情况，则进行第一步操作.
等到一次遍历结束后，需要再判断一下第一个结点的value值是否等于key，如果等于，则head = head.next即可.
//删除所有值为key的节点
public void removeAll(int key){
if(this.head == null){
throw new RuntimeException("单链表为空，无法进行删除");
}
Node prev = this.head;
Node cur = prev.next;
while(cur != null){
if(cur.value == key){
prev.next = cur.next;
cur = cur.next;
this.usedSize--;
} else{
prev = cur;
cur = cur.next;
}
}
if(this.head.value == key){
this.head = this.head.next;
this.usedSize--;
}
}直接将head结点置为null即可实现清空操作，当head结点置为null后，之后的结点对象都变成了未被引用的对象，垃圾回收器会自动回收这些未引用的对象.
//清空单链表
public void clear(){
this.head = null;
}class Node{
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}
public class SingleLinkedList {
public Node head;//定义单链表的第一个结点，编译器自动初始化为null
public int usedSize;//用来记录单链表的长度
//头插法
public void addFirst(int data){
Node node = new Node(data);
if(this.head == null){
this.head = node;
} else {
node.next = this.head;
this.head = node;
}
this.usedSize++;
}
//尾插法
public void addLast(int data){
Node node = new Node(data);
if(this.head == null){
this.head = node;
} else {
Node cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = node;
}
this.usedSize++;
}
//打印单链表
public void myToString(){
Node cur = this.head;
while(cur != null){
System.out.print(cur.value + " ");
cur = cur.next;
}
System.out.println();
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
Node cur = this.head;
while(cur != null){
if(cur.value == key){
return true;
}
cur = cur.next;
}
return false;
}
//得到单链表的长度
public int length(){
Node cur = this.head;
int length = 0;
while(cur != null){
length++;
cur = cur.next;
}
return length;
}
//寻找待插入位置的前驱结点
public Node getIndex(int pos){
Node cur = this.head;
int index = 0;
while(index != pos-1){
cur = cur.next;
index++;
}
return cur;
}
//任意位置插入,第一个数据节点为0号下标
public void insert(int pos, int data){
if(pos < 0 || pos > this.usedSize){
throw new RuntimeException("插入位置不合法");
}
if(pos == 0){
addFirst(data);
return;
}
if(pos == this.usedSize){
addLast(data);
return;
}
Node node = new Node(data);
Node prev = getIndex(pos);
node.next = prev.next;
prev.next = node;
this.usedSize++;
}
//修改指定位置的值
public void modify(int pos, int data){
if(head == null){
throw new RuntimeException("链表为空，无法进行修改");
}
if(pos < 0 || pos > this.usedSize-1){
throw new RuntimeException("操作位置不合法");
}
Node cur = this.head;
int index = 0;
while(index != pos){
cur = cur.next;
index++;
}
cur.value = data;
}
//寻找关键字key的前一个结点
private Node getPrev(int key){
Node prev = this.head;
while(prev.next != null) {
if (prev.next.value == key) {
return prev;
}
prev = prev.next;
}
return null;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
if(this.head == null){
throw new RuntimeException("链表为空，无法进行操作");
}
if(this.head.value == key){
//如果链表为空或第一个结点为删除的值
this.usedSize--;
this.head = this.head.next;
return;
}
Node prev = getPrev(key);
prev.next = prev.next.next;
this.usedSize--;
}
//删除所有值为key的节点
public void removeAll(int key){
if(this.head == null){
throw new RuntimeException("单链表为空，无法进行删除");
}
Node prev = this.head;
Node cur = prev.next;
while(cur != null){
if(cur.value == key){
prev.next = cur.next;
cur = cur.next;
this.usedSize--;
} else{
prev = cur;
cur = cur.next;
}
}
if(this.head.value == key){
this.head = this.head.next;
this.usedSize--;
}
}
//清空单链表
public void clear(){
this.head = null;
}
}