详细讲解了在 Java 中基于接口 CList 实现带有头尾指针的链表 LinkedList。内容涵盖结点定义、属性初始化、常用方法（size、isEmpty、toArray、toString）、增删改查操作的具体实现逻辑。重点阐述了头插法、尾插法以及涉及头尾指针更新时的特殊处理，包括插入、删除指定位置元素及范围删除等场景的代码示例与注意事项。
与动态数组类似，本实现基于接口 CList<E>。
包含数据域 data 和指针域 next。
public class <E> {
E data;
CNode<E> next;
{
.data = ;
.next = ;
}
{
.data = data;
.next = ;
}
{
.data = data;
.next = next;
}
}
属性：
head（存储数据）rearsize包含 head 和 rear 使得对数据进行头部和尾部的添加和删除操作时，需要特殊处理并更新指针。此处 head 必须实例化，确保后续操作有一个有效的对象基础。
private CNode<E> head = new CNode<>();
private CNode<E> rear;
private int size;
构造方法：
在属性定义中，head 已经初始化。在 CNode<E> 的构造函数中，已将 head.next 和 head.data 初始化为 null，因此直接让 rear = head 即可。
public CLinkedList() {
this.rear = head;
this.size = 0;
}
public CLinkedList(E e) {
CNode<E> newNode = new CNode<>(e);
this.head = newNode;
this.rear = head;
this.size = 1;
}
获取链表长度及判断是否为空。
同动态数组，使用匿名内部类，从外部传入数组 nv，将数据复制到 nv 中，再将 nv 返回。
public E[] toArray(E[] nv, Clone<E> clone) {
CNode<E> current = head;
for (int i = 0; i < size; i++) {
nv[i] = clone.clone(current.data);
current = current.next;
}
return nv;
}
public E[] toArray(int si, int ei, E[] nv, Clone<E> clone) {
if (si <= 0 || ei < si || ei > size) {
throw new IndexOutOfBoundsException("索引越界 size=" + size);
}
CNode<E> current = getNode(si);
for (int i = 0; i < ei - si + 1; i++) {
nv[i] = clone.clone(current.data);
current = current.next;
}
return nv;
}
用 StringBuilder 实现，append() 添加，toString() 返回字符串对象。
public String toString() {
System.out.println("当前链表长度 size = " + size);
if (isEmpty()) {
StringBuilder sb = new StringBuilder("[ ]");
return sb.toString();
} else {
CNode<E> current = head;
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size - 1; i++) {
sb.append(current.data).append(",");
current = current.next;
}
sb.append(current.data).append("]");
return sb.toString();
}
}
add()：尾插法addFirst()：头插法无论是头插法还是尾插法，添加第一个元素都需要特殊处理，判断是否为空链表（用 isEmpty()，size == 0，head.data == null）。
// 尾插法
public void add(E e) {
CNode<E> newNode = new CNode<>(e);
// 如果添加的第一个元素，特殊处理
if (head.data == null) {
head = newNode;
rear = head;
size = 1;
} else {
rear.next = newNode;
rear = newNode;
size++;
}
}
// 头插法
public void addFirst(E e) {
CNode<E> newNode = new CNode<>(e);
// 如果添加的第一个元素，特殊处理
if (head.data == null) {
head = newNode;
rear = head;
size = 1;
} else {
newNode.next = head;
head = newNode;
size++;
}
}
add()。clist 是链表，直接将 rear 节点连接到添加链表的 head 节点上，getNode(1) 得到 head 节点，同 add 方法一样，需要判断原链表是否为空，是否第一次添加元素。get() 方法得到每个元素，再用 add() 添加。
链表也可以用方法 2，但是方法 1 更高效，不用反复调用 getNode()。public void addAll(E[] objects) {
for (E object : objects) {
if (object != null) {
add(object);
}
}
}
public void addAll(CList<E> clist) {
// 如果 clist 是一个链表，不用重复调用 get 方法，直接让两个链表连接起来就行
if (clist instanceof CLinkedList<E> linkedList) {
// 需要判断原链表是否为空，需要特殊处理
if (head.data == null) {
head = linkedList.getNode(1);
rear = linkedList.getNode(clist.size());
size = size + clist.size();
} else {
rear.next = linkedList.getNode(1);
rear = linkedList.getNode(clist.size());
size = size + clist.size();
}
} else {
for (int i = 0; i < size; i++) {
add(clist.get(i + 1));
}
}
}
指定位置插入元素。指定位置插入时，需要考虑插入在链表头部和尾部的特殊情况（涉及 head 和 rear 的更新），所以分为这两个方法都要分为三种情况：插到头部（index = 1）；中间（1 < index < size）；尾部（index = size）。
public void insert(int index, E e) {
CNode<E> newNode = new CNode<>(e);
// 插入位置是第一个位置，特殊处理
if (index == 1) {
newNode.next = head.next;
head = newNode;
size++;
// 插入位置是最后一个位置，特殊处理
} else if (index == size) {
rear.next = newNode;
rear = newNode;
size++;
// 中间位置
} else {
// 获得插入位置的前一个元素
CNode<E> current = getNode(index - 1);
newNode.next = current.next;
current.next = newNode;
size++;
}
}
public void insertAll(int index, E[] es) {
// 将数组 es 转化为一个链表
CLinkedList<E> newLinkedList = new CLinkedList<>();
for (int i = 0; i < es.length; i++) {
newLinkedList.add(es[i]);
}
// 获得新链表的头尾节点
CNode<E> newNodeHead = newLinkedList.getNode(1);
CNode<E> newNodeRear = newLinkedList.getNode(newLinkedList.size());
if (index == 1) {
newNodeRear.next = head;
head = newNodeHead;
} else if (index == size) {
rear.next = newNodeHead;
rear = newNodeRear;
} else {
CNode<E> current = getNode(index - 1);
newNodeRear.next = current.next;
current.next = newNodeHead;
}
size = size + es.length;
}
分四种情况，除了在处理头和尾的特殊情况，同时还要判断删除的元素是否为最后一个元素。如果是最后一个元素，则将 head 和 rear 的 data 和 next 都设置为空指针 null，size 设置为 0，toEmpty() 完成该操作，将链表设置为空链表。
public E remove(int index) {
if (index <= 0 || index > size) {
throw new IndexOutOfBoundsException("索引越界 size=" + size);
}
CNode<E> removeNode = getNode(index);
if (size == 1) {
head.data = null;
head.next = null;
rear = head;
size = 0;
} else if (index == 1) {
head = head.next;
size--;
} else if (index == size) {
CNode<E> current = getNode(index - 1);
rear = current;
size--;
} else {
CNode<E> current = getNode(index - 1);
current.next = removeNode.next;
size--;
}
return removeNode.data;
}
public void toEmpty() {
head.data = null;
head.next = null;
rear = head;
size = 0;
}
toEmpty()。public E[] removeAll(int si, int ei) {
if (si <= 0 || ei < si || ei > size) {
throw new IndexOutOfBoundsException("索引越界 size=" + size);
}
if (si == 1 && ei != size) {
head = getNode(ei).next;
} else if (si != 1 && ei == size) {
rear = getNode(si - 1);
} else if (si == 1 && ei == size) {
toEmpty();
} else {
CNode<E> siNode = getNode(si - 1);
CNode<E> eiNode = getNode(ei + 1);
siNode.next = eiNode;
}
size = size - (ei - si + 1);
return null;
}
current 从 head 节点开始遍历整个链表，对于每一个元素，判断是否删除（用一个 for 循环判断是否存在于数组 objects 中），用 count 来记录需要删除元素的序号，将 count 传入 remove() 中进行删除。这里通过 count 记录删除元素的序号，来通过 remove() 实现删除，免去了头尾的边界特殊处理，这样的好处是不需要再写头尾的特殊处理，缺点是增加了 getNode() 函数的调用次数，时间复杂度高。
对于 for 循环的处理结果，用 flag 标志将结果带出来。如果 flag = 1 代表，该元素需要删除，此处注意不需要 count++，因为删除当前元素，current 向后移动指向的元素序号依然是 count，flag = 0 时，count++。同时注意，无论当前元素是否需要删除，current 都要向后移。public boolean removeAll(E[] objects) {
if (objects == null || objects.length == 0) {
throw new IndexOutOfBoundsException("传入数组为空");
}
CNode<E> current = head;
int count = 1;
while (current != null) {
int flag = 0;
// 记录当前节点是否需要删除
for (int j = 0; j < objects.length; j++) {
if (current.data.equals(objects[j])) {
flag = 1;
break;
}
}
current = current.next;
// 需要删除元素
if (flag == 1) {
remove(count);
} else {
count++;
}
}
return true;
}
用前后指针 prev 和 current 实现删除。当判断到当前元素需要删除时，分为三种情况：头部，中间，尾部，如果不删除则 prev 和 current 向后移动。
public int removeForE(Object e) {
CNode<E> current = head;
CNode<E> prev = null;
while (current != null) {
if (current.data.equals(e)) {
// 第一个节点
if (prev == null) {
head = head.next;
current = current.next;
size--;
// 如果删除的元素是最后一个节点
} else if (current.next == null) {
rear = prev;
rear.next = null;
size--;
break;
// 删除的是中间元素
} else {
prev.next = current.next;
current = current.next;
size--;
}
} else {
prev = current;
current = current.next;
}
}
return 1;
}
public E get(int index) {
CNode<E> current = getNode(index);
return current.data;
}
public CNode<E> getNode(int index) {
if (index <= 0 || index > size) {
throw new IndexOutOfBoundsException("索引越界 size=" + size);
}
// 如果 index = 1，则返回 head 节点
int count = 1;
CNode<E> current = head;
while (count < index && current != null) {
current = current.next;
count++;
}
return current;
}
public boolean getForE(E e) {
CNode<E> current = head;
for (int i = 0; i < size; i++) {
if (current.data.equals(e)) {
return true;
} else {
current = current.next;
}
}
return false;
}
indexForFirst()：逻辑简单，就是用 count 计数。indexForLast()：不能从后往前遍历，这里将链表逆置（头插法 addFirst()），创建一个新的链表，再用 indexForFirst 处理逆置后的链表，返回的 count 就是从后往前计数的结果。public int indexForFirst(Object e) {
CNode<E> current = head;
int count = 1;
while (current != null) {
if (current.data.equals(e)) {
return count;
} else {
current = current.next;
count++;
}
}
return count <= size ? count : -1;
}
public int indexForLast(Object e) {
CLinkedList<E> RLinkedList = new CLinkedList<>();
for (int i = 1; i <= size; i++) {
RLinkedList.addFirst(get(i));
}
int count = RLinkedList.indexForFirst(e);
return count;
}
public E replace(int index, E e) {
CNode<E> newNode = new CNode<>(e);
CNode<E> current = getNode(index);
if (index == 1) {
newNode.next = head.next;
head = newNode;
} else if (index == size) {
CNode<E> prev = getNode(index - 1);
prev.next = newNode;
rear = newNode;
} else {
CNode<E> prev = getNode(index - 1);
newNode.next = current;
prev.next = newNode;
}
return current.data;
}
处理方法类似于 removeForE()。创建一个 current 和 prev，方便对元素修改，替换元素和删除一个元素相似。
public int replaceAll(E oe, E ne) {
CNode<E> current = head;
CNode<E> prev = null;
int count = 0;
while (current != null) {
if (current.data.equals(oe)) {
count++;
CNode<E> newNode = new CNode<>(ne);
if (prev == null) {
newNode.next = head.next;
head = newNode;
prev = head;
current = current.next;
} else if (current.next == null) {
prev.next = newNode;
rear = newNode;
break;
} else {
prev.next = newNode;
newNode.next = current.next;
prev = newNode;
current = current.next;
}
} else {
prev = current;
current = current.next;
}
}
return count;
}
对于数组创建一个链表，再将其插入不同位置。
public E[] replaceAll(int si, E[] objects) {
if (si <= 0 || si > size) {
throw new IndexOutOfBoundsException("索引越界 size=" + size);
}
CLinkedList<E> newLinkedList = new CLinkedList<>();
for (int i = 0; i < objects.length; i++) {
newLinkedList.add(objects[i]);
}
if (si == 1) {
newLinkedList.rear.next = head;
head = newLinkedList.head;
} else if (si == size) {
rear.next = newLinkedList.head;
rear = newLinkedList.rear;
} else {
CNode<E> prev = getNode(si - 1);
CNode<E> current = getNode(si);
prev.next = newLinkedList.head;
newLinkedList.rear.next = current;
}
size = size + objects.length;
return null;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online