- 带头单链表
- 一、概念
- 二、要点总结
- 三、代码实现
- 1. 类结构
- 2. 带头单链表的遍历
- 3. 插入结点
- 3. 1. 头插法
- 3.2. 指定索引处插入结点
- 3.3 尾插法
- 4. 删除结点
- 4.1. 删除指定索引处的结点
- 4.2 删除所有值为val的结点
带头单链表中默认带有一个虚拟头结点dummyHead，不存储有效元素。
二、要点总结-
链表中仅创建了虚拟头结点的Node对象 private Node dummyHead = new Node();
虚拟头结点的属性值val默认为0（不存储有效元素），next引用默认为null
-
带有虚拟头结点后，头结点也具有了前驱结点，带头单链表中所有的结点都有了前驱结点
所有结点的插入、删除方式均相同，无需再对头结点进行单独处理，无需单独考虑头结点
-
插入、删除操作的核心即寻找前驱结点，带头单链表中第一个前驱结点即为虚拟头结点
-
遍历单链表中的每个元素
-
遍历带头单链表的每个元素：从第一个有效元素开始（越过虚拟头结点） Node x = dummyHead.next;
-
遍历不带头单链表的每个元素：从头结点开始 Node x = head;
-
-
在带头单链表中根据index寻找结点
从虚拟头结点向后走 Node x = dummyHead;
-
寻找index的前驱结点：从虚拟头结点开始向后走 index 步即到达index的前驱结点
for(int i = 0; i < index; i++) —— 循环执行index次
-
寻找index结点：从虚拟头结点开始向后走 (index+1) 步即到达index结点
for(int i = 0; i < index+1; i++) —— 循环执行(index+1)次
-
//结点类
class Node {
int val; //当前结点保存的值
Node next; //下一个结点的地址
public Node(int val) {
this.val = val;
}
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
public Node() {};
}
//带头单链表
public class SingleLinkedListWithDummyHead {
private int size; //链表中有效元素的个数（不包含虚拟头结点），第一个有效元素的索引为0
private Node dummyHead = new Node(); //虚拟头结点
...（增删改查等方法）
}
2. 带头单链表的遍历
【遍历单链表中的每个元素】
遍历带头单链表的每个元素：从第一个有效元素开始（越过虚拟头结点） Node x = dummyHead.next; √
遍历不带头单链表的每个元素：从头结点开始 Node x = head;
public String toString() {
String ret = "";
Node x = dummyHead.next; //从第一个有效元素开始遍历
while (x != null) {
ret += x.val + "->";
x = x.next;
}
ret += "NULL";
return ret;
}
3. 插入结点
3. 1. 头插法
【不带头、带头单链表的头插法区别】
不带头单链表：对于原头结点存在（链表非空）、原头结点不存在（链表为空）的两种情况，头插操作部分不同
带头单链表：无论链表是否为空，原头结点均可视为存在，只是空链表的原头结点为空结点，而非空链表的原头结点为有效结点，两种情况的头插操作完全相同
public void addFirst(int val) {
dummyHead.next = new Node(val, dummyHead.next);
//有效元素增1
size++;
}
3.2. 指定索引处插入结点
在index处插入结点需找到index的前驱结点。
对于带头单链表，所有的结点包括头结点都有前驱结点，故所有结点的插入操作都相同，无需单独考虑头结点。
【在带头单链表中根据index寻找结点】
从虚拟头结点向后走 Node x = dummyHead;
寻找index的前驱结点：从虚拟头结点开始向后走 index 步即到达index的前驱结点
for(int i = 0; i < index; i++) —— 循环执行index次
寻找index结点：从虚拟头结点开始向后走 (index+1) 步即到达index结点
for(int i = 0; i < index+1; i++) —— 循环执行(index+1)次
public void add(int index, int val) {
//【传参涉及index就要判断其合法性】允许(index=0)头插、(index=size)尾插
if(index < 0 || index > size) {
System.err.println("add index illegal!");
return;
}
//从虚拟头结点开始向后寻找index的前驱结点
Node prev = dummyHead;
//走index步即找到prev结点 ==> 循环index次
for(int i = 0; i < index; i++) {
prev = prev.next; //prev向后移动一步
}
prev.next = new Node(val, prev.next);
//有效元素增1
size++;
}
3.3 尾插法
可直接复用指定索引插入结点的方法add(int index, int val)。尾结点有前驱结点，同其他所有结点的插入操作相同。
public void addLast(int val) {
add(size, val);
}
4. 删除结点
4.1. 删除指定索引处的结点
删除index处的结点需先找到index的前驱结点。
对于带头单链表，所有的结点包括头结点都有前驱结点，故所有结点的删除操作都相同，无需单独考虑头结点。
private boolean rangeCheck(int index) {
if(index < 0 || index >= size) { //必须在有效元素的范围内，不允许(index=size)
System.err.println("index illegal!");
return false;
}
return true;
}
public int remove(int index) {
//【传参涉及index就要判断其合法性】
if(!rangeCheck(index)) {
return -1;
}
//从虚拟头结点开始向后寻找index的前驱结点
Node prev = dummyHead;
//向后走index步即找到前驱结点
for(int i = 0; i < index; i++) {
prev = prev.next;
}
//找到index的前驱结点，暂存index结点值用于返回
Node node = prev.next;
int temp = node.val;
//删除index结点
prev.next = node.next; //前驱结点的next指针指向后驱结点
node.next = node = null; //指向后驱结点的next指针置空，将node自身也置空
size--;
return temp;
}
4.2 删除所有值为val的结点
1）考虑链表中出现多个连续相邻的val要删除的情况：
设置循环，每次都只删除一个结点，删除后即检查此结点的后继结点是否还是val，若还是val则继续删除此结点，若不是val则向后移动前驱结点指针prev，寻找下一个要删除的val
2）由于带头单链表的所有结点（包括头结点）都有前驱结点，故无需单独考虑头结点
public void removeByValueAll(int val) {
//寻找val结点的前驱结点
Node prev = dummyHead; //虚拟头结点是链表中的第一个前驱结点
while (prev.next != null) { //后方还有结点
if (prev.next.val == val) { //循环删除所有值为val的结点
//删除结点
Node node = prev.next;
prev.next = node.next;
node.next = node = null;
size--;
} else { //prev.next不是待删除结点
prev = prev.next; //移动prev指针
}
}
}
