一、链表简介
链表是有序的列表，在内存中的存储方式如图：
- 链表是以节点的方式来存储，是链式存储；
- 每个节点包含data域，next指针（指向下一个节点）；
- 链表的节点不一定连续存储，是离散的状态；
- 链表分为带头节点的链表和没有头结点的链表，带头结点的逻辑结构示意图如下：
二、单链表的应用实例
2.1 单链表的基础方法的实现
使用带头结点的单向链表实现，完成对水浒英雄的CRUD。
- 普通新增方法
此方法添加英雄时，直接添加到链表尾部。
- 先创建一个head节点，不记录具体信息，作用就是表示单链表的头结点；
- 此后每添加一个节点，就直接添加在链表的最后
- 示意图：
- 按序新增方法
此方法在添加英雄时，根据英雄的排名将英雄添加到指定的位置。
- 首先找到新节点应该添加的位置，通过辅助指针来遍历找到位置；
- 将新节点的next设置为指针指向节点的next节点；
- 将指针指向的节点的next设置新节点；（2、3步骤顺序不能互换）
- 不能添加相同排名的英雄；
- 示意图：
- 修改节点方法
- 先通过遍历找到对应节点；
- 修改数据。
- 删除节点方法
- 找到需要删除的del节点；
- 将del节点的前一个节点的next指向del节点的next节点；
- 示意图：
2.2 单链表的相关面试题
- 求单链表中的有效节点的个数
思路：
遍历单链表，如果有头结点忽略头结点
代码：
/**
* 获取链表的长度
*
* @param head 链表头结点
* @return 长度
*/
int getLength(HeroNode head) {
int length = 0;
while (Objects.nonNull(head.getNext())) {
length++;
head = head.getNext();
}
return length;
}
- 查找单链表中的倒数第k个节点
思路：
- 先求得链表的长度length；
- 用length - k即可算出倒数第k个节点所处位置；
- 从链表头结点遍历length - k次即可。
代码：
/**
* 寻找倒数第k个节点
*
* @param singleLinkedList 链表
* @param k k值
* @return 倒数第k个节点
*/
HeroNode findTheKthFromBottom(SingleLinkedList singleLinkedList, int k) {
int length = getLength(singleLinkedList.head);
int index = length + 1 - k;
HeroNode temp = singleLinkedList.head;
while (Objects.nonNull(singleLinkedList.head.getNext()) && index > 0) {
temp = temp.getNext();
index--;
}
return temp;
}
- 反转链表
- 定义一个新的头结点newHead；
- 遍历原来的链表，每遍历一个节点，就将这个节点放到newHead的next即可；
- 打印时以newHead为头结点打印。
示意图：
代码：
/**
* 反转链表
* 思路：
* 定义一个新的头结点newHead，遍历链表，依次将遍历的节点取出放到newHead的后面即可
*
* @param oldHead 链表的旧头结点
*/
void reverse(HeroNode oldHead) {
// 定义一个新的头结点
HeroNode newHead = new HeroNode(0L, "", "");
// 定义一个临时节点，记录即将遍历的下一个节点
HeroNode next;
// 跳过头节点
HeroNode current = oldHead.getNext();
while (Objects.nonNull(current)) {
// 记录即将遍历的下一个节点
next = current.getNext();
// 将newHead的下一个节点设置为当前节点的next
current.setNext(newHead.getNext());
// 将newHead的next设置为当前节点
newHead.setNext(current);
// 恢复遍历指针
current = next;
}
// 修改链表头结点
head = newHead;
}
- 从尾到头打印单链表
思路：
方式1：将单链表先进行反转操作，然后再遍历打印即可，缺点是会破坏原来的单链表的存储结构；
方式2：可以利用栈数据结构先进后出的特性，从头到尾遍历时将节点依次压入栈中，打印时依次从栈中pop即可。
代码：
/**
* 逆向打印链表
* 思路：
* 1、先反转链表，再打印链表，缺点是会破坏原链表的结构
* 2、利用栈数据结构先进后出的特性来辅助实现
* 这里用栈来实现
*/
void reversePrint() {
Stack<HeroNode> nodeStack = new Stack<>();
HeroNode current = head.getNext();
while (Objects.nonNull(current)) {
nodeStack.push(current);
current = current.getNext();
}
while (!nodeStack.isEmpty()) {
System.out.println(nodeStack.pop());
}
}