双向链表、双端(双向)链表、循环(双向)链表示意(简)图：
声明：下面各图中，箭头指向的是整个节点，而不是指向节点中的prior或next。
双向链表：只有一个指针指向最开始的结点。
双端(双向)链表：有两个指针分别指向两端的节点。
循环(双向)链表：指向形成一个闭环。
双端(双向)链表的Java实现(简单示例)：
注：双向链表、双端(双向)链表、循环(双向)链表的实现思路几乎一样，这里以实现双端(双向)链表示例。
/**
* 双端(双向)链表的(简单)实现
*
* @author JustryDeng
* @date 2019/5/21 20:51
*/
public class DoublesidedLinkedlistImpl<T> {
/** 节点的个数 */
private int size;
/**
* 尾节点
* 注:本人新增节点时，从尾巴上新增
* 注:也可以从头上进行新增节点
*/
private Node rear;
/**
* 当前节点
* 即:链表中最前面的节点，可理解为 队列中的头结点
*/
private Node head;
/**
* 成员内部类， 节点
*/
private class Node {
/** 内部类的元素,Object类型 */
private T data;
/** 上一个节点(即:前驱节点)的地址 */
private Node prior;
/** 下一个节点(即:后继节点)的地址 */
private Node next;
private Node(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node getPrior() {
return prior;
}
public void setPrior(Node prior) {
this.prior = prior;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
/**
* 新增节点
*
* @param obj
* 添加的元素
* @return 添加的元素对应的节点
* @date 2019/5/20 20:48
*/
public Node addNode(T obj) {
// obj不能为null
notNullCheck(obj);
// 每次增加的元素，都作为新的尾节点
Node newRear = new Node(obj);
if (size == 0) {
head = newRear;
rear = newRear;
} else {
newRear.prior = rear;
rear.next = newRear;
// 更新尾节点
rear = rear.next;
}
size++;
return newRear;
}
/**
* 删除当前(头)节点
*
* @return 被删除了的(头)节点
* @date 2019/5/20 20:50
*/
public Node deleteHead() {
if(isEmpty()) {
return null;
}
// targetObj存放原来的头节点数据
Node targetNode = head;
if (head.next != null) {
// 断开后继节点对要删除的节点的引用
head.next.prior = null;
}
// 更新头节点
head = head.next;
size--;
return targetNode;
}
/**
* 删除指定元素对应的第一个节点
*
* @return 删除成功与否(若元素不存在，则返回false)
* @date 2019/5/20 20:50
*/
public boolean deleteFirstNode(T obj) {
// obj不能为null
notNullCheck(obj);
// 当head未null时，说明，当前为空链表
if (size == 0) {
return false;
}
// 当前节点
Node current = head;
// 前驱节点
Node previous = head;
// 判断条件，如果当前节点的值和待删除的值不一致，则继续
while (!obj.equals(current.data)) {
// 如果下一个节点不存在(即:当前节点是尾节点)
// 则说明，不存在 元素值为obj的节点，直接返回false
if (current.next == null) {
return false;
} else {
// 更新前驱节点、当前节点
previous = current;
current = current.next;
}
}
// 如果要删除的节点是第一个节点；
if (head.equals(current)) {
if (head.next != null) {
// 断开后继节点对要删除的节点的引用
head.next.prior = null;
}
// 更新头结点
head = current.next;
// 如果要删除的节点是尾节点
} else if ((rear.equals(current))) {
// 前驱节点断开对要删除的节点的应用
previous.next = null;
// 如果要删除的节点不是头结点(是中间的某个节点或尾节点)
} else {
// 将当前节点“抠除”，并将“两端”接上
previous.next = current.next;
current.prior = previous;
}
size--;
return true;
}
/**
* 删除指定元素对应的所有节点
* 注:此方法性能较低，少用或不用
*
*
* @return 删除了的节点数
* @date 2019/5/20 20:50
*/
public int deleteAllNode(T obj) {
int count = 0;
while(deleteFirstNode(obj)){
count++;
}
return count;
}
/**
* 查找元素的(第一个)节点
*
* @param obj
* 待查找的元素对象
* @return 元素的(第一个)节点, 无则返回null
*/
public Node find(T obj) {
// obj不能为null
notNullCheck(obj);
Node currNode = head;
// 临时大小为size
int tempSize = size;
while (tempSize > 0) {
if (obj.equals(currNode.data)) {
return currNode;
} else {
currNode = currNode.next;
}
tempSize--;
}
return null;
}
/**
* 非空检验
*
* @param obj
* 被验证的对象
* @throws NullPointerException 空指针异常(运行时异常)
* @date 2019/5/20 21:00
*/
private void notNullCheck(T obj){
if(obj == null) {
throw new NullPointerException("data must not be null!");
}
}
/**
* 判断链表是否为空
*
* @return 链表是否为空
* @date 2019/5/20 20:49
*/
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder(16);
sb.append("[");
Node currentNode = head;
for (int i = 0; i < size; i++) {
sb.append(currentNode.data);
sb.append(", ");
currentNode = currentNode.next;
}
int length = sb.length();
sb.delete(length - 2, length).append("]");
return sb.toString();
}
public static void main(String[] args) {
DoublesidedLinkedlistImpl<String> uli = new DoublesidedLinkedlistImpl<>();
// 增
uli.addNode("A");
uli.addNode("B");
uli.addNode("C");
uli.addNode("C");
uli.addNode("D");
uli.addNode("C");
uli.addNode("E");
uli.addNode("E");
uli.addNode("F");
uli.addNode("E");
// toString
System.out.println("增加节点后的初始化链表:\t" + uli);
// 找到C元素对应的第一个节点
System.out.println("找到C元素对应的第一个节点:" + uli.find("C")
+ ",该节点的下下个节点的数据内容为:"
+ uli.find("C").getNext().getNext().getData());
// 删除头结点
uli.deleteHead();
// toString
System.out.println("删除头结点后:\t" + uli);
// 删除C元素对应的第一个节点
uli.deleteFirstNode("C");
// toString
System.out.println("删除C元素对应的第一个节点后:\t" +uli);
// 删除E元素对应的所有节点
uli.deleteAllNode("E");
// toString
System.out.println("删除E元素对应的所有节点后:\t" +uli);
}
}
测试一下：
运行(写在实现类里面的)主方法，控制台输出：
由此可见：简单的双端(双向)链表实现完毕！
^_^ 如有不当之处，欢迎指正
^_^ 学习视频
51CTO学院《数据结构与算法》，讲师张晨光