一文搞定双链表，让你彻底弄懂线性表的链式实现( 二 ) _双链表

文章插图
尾删除

尾删除和头删除类似，考虑好tail节点情况

如果tail不为null：

tail = tail.pre 。
如果tail不为null，那么tail.next = null 表示删除最后一个，如果tail为null，说明之前head和tail都指向一个唯一节点，这时候需要head = null 。

编号删除

编号删除和编号插入类似，先考虑是否为头尾操作，然后再进行正常操作。

index为0：调用头删
index为size：调用尾删
index在(0,size):

找到待删除节点current 。
前驱节点(current.pre)的next指向后驱节点(current.next) 。
后驱节点的pre指向前驱节点。

文章插图
完整代码根据上面的流程，实现一个不带头结点的双链表，在查找方面，可以根据靠头近还是尾近，选择从头或者尾开始遍历。
代码：

/* * 不带头节点的 */package code.linearStructure;/** * @date 2023.11.02 * @author bigsai * @param <T> */public class DoubleLinkedList<T> {private Node<T> head;private Node<T> tail;private int size;public DoubleLinkedList() {this.head = null;this.tail = null;size = 0;}// 在链表头部添加元素public void addHead(T data) {Node<T> newNode = new Node<>(data);if (head == null) {head = newNode;tail = newNode;} else {newNode.next = head;head.pre = newNode;head = newNode;}size++;}// 在指定位置插入元素public void add(T data, int index) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Index is out of bounds");}if (index == 0) {addHead(data);} else if (index == size) {addTail(data);} else {Node<T> newNode = new Node<>(data);Node<T> preNode = getNode(index-1);//step 1 2 新节点与后驱节点建立联系newNode.next = preNode;preNode.next.pre = newNode;//step 3 4 新节点与前驱节点建立联系preNode.next = newNode;newNode.pre = preNode;size++;}}// 在链表尾部添加元素public void addTail(T data) {Node<T> newNode = new Node<>(data);if (tail == null) {head = newNode;tail = newNode;} else {newNode.pre = tail;tail.next = newNode;tail = newNode;}size++;}// 删除头部元素public void deleteHead() {if (head != null) {head = head.next;if (head != null) {head.pre = null;} else { //此时说明之前head和tail都指向唯一节点，链表删除之后head和tail都应该指向nulltail = null;}size--;}}// 删除指定位置的元素public void delete(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index is out of bounds");}if (index == 0) {deleteHead();} else if (index == size - 1) {deleteTail();} else {Node<T> current = getNode(index);current.pre.next = current.next;current.next.pre = current.pre;size--;}}// 删除尾部元素public void deleteTail() {if (tail != null) {tail = tail.pre;if (tail != null) {tail.next = null;} else {//此时说明之前head和tail都指向唯一节点，链表删除之后head和tail都应该指向nullhead = null;}size--;}}// 获取指定位置的元素public T get(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index is out of bounds");}Node<T> node = getNode(index);return node.data;}// 获取链表的大小public int getSize() {return size;}private Node<T> getNode(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index is out of bounds");}if (index < size / 2) {Node<T> current = head;for (int i = 0; i < index; i++) {current = current.next;}return current;} else {Node<T> current = tail;for (int i = size - 1; i > index; i--) {current = current.pre;}return current;}}private static class Node<T> {T data;Node<T> pre;Node<T> next;public Node(T data) {this.data = https://www.isolves.com/it/sjk/bk/2023-11-08/data;}}}

结语在插入删除的步骤，很多人可能因为繁琐的过程而弄不明白，这个操作的写法可能是多样的，但本质操作都是一致的，要保证能成功表示节点并操作，这个可以画个图一步一步捋一下，看到其他不同版本有差距也是正常的。
还有很多人可能对一堆next.next搞不清楚，那我教你一个技巧，如果在等号右侧，那么它表示一个节点，如果在等号左侧，那么除了最后一个.next其他的表示节点。例如node.next.next.next可以看成(node.next.next).next 。
在做数据结构与算法链表相关题的时候，不同题可能给不同节点去完成插入、删除操作。这种情况操作时候要谨慎先后顺序防止破坏链表结构。