定义

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。

双向链表，每个元素知道其上一个元素和下一个元素。

以下为示例代码：

package com.tfq.arithmetic.linkedlist;

import java.util.Iterator;
import java.util.function.Consumer;

/**
 * @author: fqtang
 * @date: 2024/05/21/9:29
 * @description: 双向链表(带哨兵)
 */
public class DoubleLinkedListSentinel implements Iterable<Integer> {

	static class Node {
		Node prev;//上一个节点指针
		int value;//值
		Node next;//下一个节点指针

		public Node(Node prev, int value, Node next) {
			this.prev = prev;
			this.next = next;
			this.value = value;
		}

	}

	private Node head;//头哨兵
	private Node tail;//尾哨兵

	public DoubleLinkedListSentinel() {
		this.head = new Node(null, 666, null);
		this.tail = new Node(null, 999, null);
		head.next = tail;
		tail.prev = head;
	}

	/**
	 * 返回链表第一种方式
	 *
	 * @return
	 */
	public void loop(Consumer<Integer> consumer) {
		Node p = head.next;
		while(p != null) {
			consumer.accept(p.value);
			p = p.next;
		}
	}

	/**
	 * 返回链表第二种方式
	 *
	 * @return
	 */
	public void loop2(Consumer<Integer> consumer) {
		for(Node p = head.next; p != null; p = p.next) {
			consumer.accept(p.value);
		}
	}

	public void addFirst(int value) {
		insert(0, value);
	}

	public void addLast(int value) {
		Node last = tail.prev;
		Node insertNode = new Node(last, value, tail);
		last.next = insertNode;
		tail.prev = insertNode;
	}

	private Node findLast() {
		return tail.prev;
	}

	public void removeLast() {
		Node remove = tail.prev;
		if(remove == head) {
			throw new IllegalArgumentException(String.format("双向链表为空，不能删除此链表的头部!"));
		}
		Node prev = remove.prev;

		prev.next = tail;
		tail.prev = prev;
	}

	/**
	 * 根据索引查找链表的节点
	 *
	 * @param index
	 * @return
	 */
	private Node findNode(int index) {
		int i = -1;
		for(Node p = head; p != tail; p = p.next, i++) {
			if(i == index) {
				return p;
			}
		}

		return null;//没找到
	}

	public int getValue(int index) {
		Node node = findNode(index - 1);
		if(node == head || node == tail) {
			throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
		}
		return findNode(index - 1).value;
	}

	/**
	 * 向索引位置插值
	 *
	 * @param index 索引
	 * @param value 待插入值
	 */
	public void insert(int index, int value) {
		//找到上一个节点和下一个节点
		Node prev = findNode(index - 1);
		if(prev == null) {
			throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
		}
		Node next = prev.next;
		//创建一个要插入的新节点
		Node insertedNode = new Node(prev, value, next);
		prev.next = insertedNode;
		next.prev = insertedNode;
	}

	/**
	 * 删除第一个节点
	 */
	public void removeFirst() {
		remove(0);
	}

	/**
	 * 根据索引删除指定元素
	 *
	 * @param index 待删除索引
	 */
	public void remove(int index) {
		Node prev = findNode(index - 1);
		if(prev == null) {
			throw new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
		}
		Node removed = prev.next;
		if(removed == tail) {
			throw new IllegalArgumentException(String.format("index [%d] 不合法,已删除尾部 %n", index));
		}
		Node next = removed.next;

		prev.next = next;
		next.prev = prev;
	}

	/**
	 * 返回链表第三种方式
	 *
	 * @return
	 */
	@Override
	public Iterator<Integer> iterator() {

		return new Iterator<Integer>() {
			Node p = head.next;

			@Override
			public boolean hasNext() {
				return p != tail;
			}

			@Override
			public Integer next() {
				int v = p.value;
				p = p.next;
				return v;
			}
		};
	}
}