? ? 顺序表ArrayList的底层是数组，将数据存储在一段连续的空间上。这样，当需要在顺序表的任意位置进行插入和删除的时候，需要把部分的元素整体移动。这样做时间复杂度是O(n)，比较慢。所以顺序表不合适做任意元素的插入和删除比较频繁的场景。引进一种链表结构来解决这个问题。
一、链表的概念和结构
? ? 链表是一种存储结构上不连续的存储结构。数据是依次通过引用来进行链接和访问的，就像一列火车这就是一种链式结构。
链表的结构，在逻辑上是连续的，但是在物理存储上是不连续的。
? ? 对于单链表，它的结构分成了两个域，一个是数值域，用来存储数值，一个是next域，也是引用域，用来存储下一个节点的地址。要找到下一个节点，就需要next来进行访问。
? ? 链表的结构分为单向或双向链表，带头或不带头链表，循环或不循环链表。下面的链表是一种不带头结点的非循环单向链表。主要要知道无头单链表和无头双链表。
二、单链表实现
public class MySingleList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
//打印链表
public void display();
//清除链表
public void clear();
}单链表的实现先从简单的循环开始，到后面在进行单链表的插入和删除操作。
1、定义单链表成员变量
? ? 单链表需要数值域来保存数值，它的类型是int。又需要next域来保存下一个节点的地址，它的类型是一个引用。在定义一个ListNode类来定义这些成员变量。
class ListNode {
//数值域
public int val;
//保存下一个节点地址
public ListNode next;
//初始化val
public ListNode(int val) {
this.val = val;
}
}? ? 同时，为了找到这个单链表的头，要定义一个head，类型是ListNode。刚开始没有链表，不需要赋值。
public class MySingleList {
//单链表的头节点
public ListNode head;
}2、打印链表display()
? ? 假设有这样一个单链表，通过这个图，链表的下一个节点是保存在上一个节点的next域中的。要通过引用来访问下一个节点。
? ? 如何打印链表呢？我们定义好了一个head，通过它的访问来打印链表。head.val就是这个链表的值，head.next就能够访问到下一个链表节点。
public void display() {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}? ? head节点保存第一个节点的信息，所有的操作都是从这个节点开始的。在这里改变了head，在其他的地方在要从head开始就不是第一个节点了。所以要使用一个临时变量cur，让cur代替head来进行操作。
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}3、 查找关键字key是否在链表中contains()
这个很简单，循环遍历链表，在判断每一个节点的值和要查找的值相等不相等就可以了。
public boolean contains(int key) {
//头节点可以判断是否为空,也可以不用判断
if (this.head == null) {
return false;
}
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}4、得到单链表长度size()
public int size() {
ListNode cur = this.head;
int count = 0;
while (cur != null) {
++count;
cur = cur.next;
}
return count;
}?下面，进行单链表的增删操作
5、头插法addFirst()
? ? 头插法就是在head节点前面在插一个节点。插入了节点后，这个节点就是一个新的头节点，要让head节点移到刚刚插入的头节点。
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
}? ? 特殊的情况是如果这个链表没有一个节点，头插法插入的节点就成了是第一次插入的节点。这个时候就直接让这个新插入的节点成为node。全部代码如下。
public void addFirst(int data) {
ListNode node = new ListNode(data);
//第一次插入
if (this.head == null) {
this.head = node;
} else {
//不是第一次插入
node.next = this.head;
this.head = node;
}
}6、尾插法addLast()
尾插法就是在链表的末尾插入一个节点。
? ? 尾插要先遍历链表，找到链表的结尾，不能动head，所以在定义一个cur来寻找尾。找到后，尾结点的next域要指向新插入的节点的地址。
public void addLast(int data) {
ListNode node = new ListNode(data);
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}? ? 特殊的，当尾插入的节点为第一次插入的时候，直接让head等于新插入的节点。尾插法全部代码如下。
public void addLast(int data) {
ListNode node = new ListNode(data);
if (this.head == null) {
head = node;
} else {
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}7、指定位置的插入addIndex()方法
? ? 虽然单链表没有下标，但是我们指定位置插入。如图所示。按照数组的下标形式，把第一个节点下标设置为0下标。当然，你也可以从1开始。下面的代码都是基于节点从0开始的代码。
? ? 指定位置插入要在合法的范围里面进行插入。所以要对这个范围进行判断。如果这个范围是超出了链表的范围，就要提示下标非法。先在addIndex方法里面写一个方法来判断要插入的范围是不是越界的。
private void checkIndexAdd(int index) {
if (index < 0 ||index > size()) {
throw new MySingleListIndexOutOfException("越界");
}
}
public void addIndex(int index, int data) {
//1,index进行合法判断 [0, size()]
checkIndexAdd(index);
}? ? 判断完成之后，就要进行插入。返回上面的图，要在2下标插入，就要找到2下标节点的前一个0x22。找到了之后让新插入的节点的next域指向原来的2下标的节点0x33，然后让0x22的next域指向新插入的节点就可以了。
? ? 如何找到2下标的前一个？慢慢找规律，发现，要在下标是2处插入，就要让cur走一步，要在下标是1处插入，就要让cur不要走...cur每一次走的都是要插入下标-1次。
新建立一个节点后，寻找插入位置的在addIndex中在写一个方法来实现这一步。
private ListNode findIndexSubOne(int index) {
ListNode cur = this.head;
while (index - 1 != 0) {
cur = cur.next;
--index;
}
return cur;
}? ? 特殊的，第一个下标和最后一个下标对应得是我们的头插法和尾插法，所以直接调用就可以了。下面是全部的代码。
private void checkIndexAdd(int index) {
if (index < 0 ||index > size()) {
throw new MySingleListIndexOutOfException("越界");
}
}
private ListNode findIndexSubOne(int index) {
ListNode cur = this.head;
while (index - 1 != 0) {
cur = cur.next;
--index;
}
return cur;
}
public void addIndex(int index, int data) {
//1,index进行合法判断 [0, size()]
checkIndexAdd(index);
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode node = new ListNode(data);
ListNode cur = findIndexSubOne(data);
node.next = cur.next;
cur.next = node;
}8、删除第一次出现为key的值remove()
? ? 删除第一次出现的值，需要先找到这个值的节点B的前一个节点A，然后让A指向B的下一个节点C就可以了。
如果只用一个临时节点cur来完成，那么，cur需要判断cur.next.val的值是不是要删除的值。
? ? 特殊的，如果这个链表是空链表，那么就不需要删除。如果要删除的值在头节点或尾结点。如果是头节点，那么让head指向下一个就可以了。尾结点的话要注意不要让cur或cur.next指向null，会引起空指针异常。
public void remove(int key) {
//头节点删除
if (this.head == null) {
return;
}
if (this.head.val == key) {
this.head = this.head.next;
}
//中间节点
ListNode cur = this.head;
while (cur.next != null) {
if (cur.next.val == key) {
ListNode del = cur.next;
cur.next = del.next;
return;
}
cur = cur.next;
}
}9、删除所有为key的值removeAllKey()
? ? 和上一个不一样的是，这个方法要求删除所有的为key的值的节点。remove方法中，删除第一次出现的值后，让cur移动了。在这个方法中，不需要移动cur。因为删除后自然cur就指向了下一个节点，如果下一个节点还是cur，直接删除，在让cur继续重复。
//删除所有值为key的节点
public void removeAllKey(int key) {
if (this.head == null) {
return;
}
while (this.head != null && this.head.val == key) {
this.head = this.head.next;
}
ListNode cur = this.head;
while(cur != null && cur.next != null) {
if(cur.next.val == key) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
}10、全部代码
/**
* @author: Naion
* @create: 2022-04-27 23:04
* @Description:
**/
public class MySingleList {
static class ListNode {
private int val;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
}
private ListNode head;
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
}
public void addLast(int data) {
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
return;
}
ListNode cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
public void checkIndexAdd(int pos) {
if (pos < 0 || pos > size()) {
throw new RuntimeException("越界！");
}
}
public ListNode findSubscript(int index) {
ListNode cur = this.head;
while (index - 1 > 0) {
cur = cur.next;
--index;
}
return cur;
}
public void addIndex(int index, int data) {
checkIndexAdd(index);
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
}
ListNode cur = findSubscript(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
public void remove(int key) {
if (this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = this.head;
while (cur != null && cur.next != null) {
if (cur.next.val == key) {
cur.next = cur.next.next;
}
cur = cur.next;
}
}
//删除所有值为key的节点
public void removeAllKey(int key) {
if (this.head == null) {
return;
}
while (this.head != null && this.head.val == key) {
this.head = this.head.next;
}
ListNode cur = this.head;
while(cur != null && cur.next != null) {
if(cur.next.val == key) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
}
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
++count;
cur = cur.next;
}
return count;
}
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
}
public void clear() {
this.head = null;
}
}
