实际：位于链表头部的节点 ； 自己定义（也可以不定义该变量）：链表头部的节点自定义为head（first）； 官方定义：若只有指针为头节点 否则为普通节点 ；
实际：位于链表尾部的节点 ； 自己定义（也可以不定义该变量）：链表尾部的节点自定义为tail（last） ； 官方定义：若只有指针为尾节点 否则为普通节点 ；
1：仿写一个LinkedList链表
主要为仿写JDK1.8的LinkedList链表
无头节点 无尾节点 的 双向非循环链表
位置位于链表的头部（自定义为head（first）），如果有数据为普通节点（称为位于头部的节点） 如果只有指针为头节点
位置位于链表的尾部（自定义为tail（last））， 如果有数据为普通节点（称为位于尾部的节点） 如果只有指针为尾节点
头节点与无头节点 尾节点与无尾节点
不管是单向链表 还是 双向链表都可以设置有无头尾节点
单（双）向链表：有头节点 无尾节点
单（双）向链表：无头节点 有尾节点
单（双）向链表：有头节点 有尾节点
单（双）向链表：无头节点 无尾节点
双向链表与单向链表的区别：
双向链表与单向链表只有一个区别 双向链表的节点可以指向前节点 而 单向链表没有
单向链表 由于没有前指针 因此其处于尾部的节点（有数据），
可以进行数据插入 但不能进行倒序遍历 ；
双向链表 由于具有前指针 因此其尾节点（只有指针）或者 处于尾部的节点（有数据），
可以进行数据插入 倒序遍历；
单向链表：通常不自定义位于链表的尾部 tail（last）
双向链表：通常会自定义位于链表的尾部 tail（last）
2：节点
public class NodeDoubly<E> {
E data;
NodeDoubly<E> next;
NodeDoubly<E> prev;
public NodeDoubly(NodeDoubly<E> prev, E data, NodeDoubly<E> next) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
3：无头节点 无尾节点 的 双向非循环链表代码
public class DoublyLinkedList<E> {
//初始化 无头节点（头节点为空）
private NodeDoubly<E> first ;
//初始化 无尾节点（尾节点为空）
private NodeDoubly<E> last ;
//无头结点
//表头部插入
public void insertAsfirst(E value) {
NodeDoubly<E> newNodeDoubly = new NodeDoubly(null,value,null );
insertTofirst(newNodeDoubly);
}
// LinkedList源码阅读
// 首次插入：
// 1：f = null
// 2： 新节点的next 指向 null
// 3：first 等于新节点
// 4：如果 f 为 null ： last 也等于新节点
//
//
// 之后插入：
// 1：f 不为null
// 2：新节点 的next 指向 f 原头节点
// 3：first 等于新节点 （next 指向 f 原头节点）
// 4：如果 f 不为 null ： f 原头节点 的prev 指向新节点
//
// private void linkFirst(E e) {
// final Node<E> f = first;
// final Node<E> newNode = new Node<>(null, e, f);
// first = newNode;
// if (f == null)
// last = newNode;
// else
// f.prev = newNode;
// size++;
// modCount++;
// }
//表头部插入头节点 同时尾节点也头节点
//注意 first 与 last 一开始会指向相同的节点
//假如修改了first 的地址指向 last还是指向原节点
private void insertTofirst(NodeDoubly newNodeDoubly) {
//创建一个节点该节点同时为 头节点与尾节点
if (first == null) {
first = newNodeDoubly;
last = newNodeDoubly;
} else {
//新节点 next 指向 原first
newNodeDoubly.next = first;
//原first pre 指向 新节点
first.prev = newNodeDoubly;
//first变量名的 指针指向 变为新节点
first = newNodeDoubly;
}
}
//在某节点上前 插入新节点
public void insertBefore(NodeDoubly originalNodeDoubly, E value) {
NodeDoubly<E> newNodeDoubly = new NodeDoubly(null,value, null);
insertBefore(originalNodeDoubly, newNodeDoubly);
}
private void insertBefore(NodeDoubly originalNodeDoubly, NodeDoubly<E> newNodeDoubly) {
if (originalNodeDoubly == null) {
return;
}
//判断原有节点是否为头节点
if (first == originalNodeDoubly) {
insertTofirst(newNodeDoubly);
return;
}
//以头节点开始 使用next进行遍历 一直到获取到
// 遍历节点 的下一个节点为需要查找的某节点为止
NodeDoubly<E> indexNodeDoubly = first;
while (indexNodeDoubly != null && indexNodeDoubly.next != originalNodeDoubly) {
indexNodeDoubly = indexNodeDoubly.next;
}
if (indexNodeDoubly == null) {
return;
}
//最后顺序 遍历节点 新节点 某节点
//实现了 新节点插入到原节点之前的功能
newNodeDoubly.next = originalNodeDoubly;
originalNodeDoubly.prev = newNodeDoubly;
indexNodeDoubly.next = newNodeDoubly;
newNodeDoubly.prev = indexNodeDoubly;
}
//顺序插入
//链表尾部插入
public void insertAsLast(E value) {
NodeDoubly<E> newNodeDoubly = new NodeDoubly(null,value,null );
//创建一个节点该节点同时为 头节点与尾节点
if (last == null) {
first = newNodeDoubly;
last = newNodeDoubly;
} else {
//新节点 next 指向 原last
newNodeDoubly.prev = last;
//原last next 指向 新节点
last.next = newNodeDoubly;
//last变量名的 指针指向 变为新节点
last = newNodeDoubly;
}
}
public void deleteByNode(NodeDoubly originalNodeDoubly) {
if (originalNodeDoubly == null || first == null && last == null) {
return;
}
if (originalNodeDoubly == first) {
if(first == last){
last = null;
}
first = first.next;
first.prev = null;
return;
}
if (originalNodeDoubly == last) {
if(first == last){
first = null;
}
last = last.prev;
last.next = null;
return;
}
NodeDoubly<E> indexNodeDoubly = first;
//以头节点开始 使用next进行遍历 一直获取到
// 遍历节点 的下一个节点为原节点为止
while (indexNodeDoubly != null && indexNodeDoubly.next != originalNodeDoubly) {
indexNodeDoubly = indexNodeDoubly.next;
}
if (indexNodeDoubly == null) {
return;
}
//获取到 遍历节点 某节点
//最后 遍历节点 直接指向 遍历节点的下个节点（原节点）的下一个节点
// 遍历节点的下个节点（原节点）的下一个节点 的前节点 指向新节点
//实现了 被删除的某节点就会被跳过
indexNodeDoubly.next = indexNodeDoubly.next.next;
indexNodeDoubly.next.prev = indexNodeDoubly;
}
//根据value删除节点
public void deleteByValue(E value){
NodeDoubly<E> indexNodeDoubly = first;
//外部接口调用 第一次为从 头节点进行遍历
deleteByValueRepetition(value, indexNodeDoubly);
}
//通过递归 根据value 删除所有拥有该value的节点
public void deleteByValueRepetition(E value, NodeDoubly<E> indexNodeDoubly) {
if (first == null && last == null) {
return;
}
NodeDoubly<E> beforeIndexNodeDoubly = null;
// 以头节点开始 使用next进行遍历 一直到获取到为止
// 遍历节点 的 data 为所需要查找的data为止
// 该遍历节点是需要删除的 因此还需要查找出前一个节点
while (indexNodeDoubly != null && indexNodeDoubly.data != value) {
beforeIndexNodeDoubly = indexNodeDoubly;
indexNodeDoubly = indexNodeDoubly.next;
}
if (indexNodeDoubly == null) {
return;
}
//查找到data的节点为 头节点
if (beforeIndexNodeDoubly == null) {
if(first == last){
first = null;
last = null;
}else {
first = first.next;
first.prev = null;
}
} else {
beforeIndexNodeDoubly.next = beforeIndexNodeDoubly.next.next;
beforeIndexNodeDoubly.next.prev = beforeIndexNodeDoubly;
}
//对于向媒体的value 可以进行递归删除
deleteByValueRepetition(value, beforeIndexNodeDoubly);
}
//查找节点的data
public NodeDoubly<E> findByValueFirst(E value) {
NodeDoubly<E> indexNodeDoubly = first;
while (indexNodeDoubly != null && indexNodeDoubly.data != value) {
indexNodeDoubly = indexNodeDoubly.next;
}
return indexNodeDoubly;
}
//查找节点的data
public NodeDoubly<E> findByValueLast(E value) {
NodeDoubly<E> indexNodeDoubly = last;
while (indexNodeDoubly != null && indexNodeDoubly.data != value) {
indexNodeDoubly = indexNodeDoubly.prev;
}
return indexNodeDoubly;
}
//打印所有数据
public void findAll() {
NodeDoubly<E> p = first;
while (p != null) {
System.out.print(p.data + " ");
p = p.next;
}
System.out.println();
}
}
4：测试代码
private static void DoublyLinkedListTest() {
DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
doublyLinkedList.insertAsfirst(5);
doublyLinkedList.insertAsfirst(7);
doublyLinkedList.insertAsfirst(9);
//不同于单向链表从头部开始遍历 然后插入 双向链表可以直接从尾部进行插入
doublyLinkedList.insertAsLast(10);
doublyLinkedList.findAll();
System.out.println("==============================================");
//双向链表从头部开始遍历查找
// NodeDoubly nodeDoublyTemp = doublyLinkedList.findByValueFirst(5);
//双向链表从尾部开始遍历查找
NodeDoubly nodeDoublyTemp = doublyLinkedList.findByValueLast(5);
doublyLinkedList.insertBefore(nodeDoublyTemp,2);
doublyLinkedList.insertBefore(nodeDoublyTemp,3);
doublyLinkedList.insertBefore(nodeDoublyTemp,4);
doublyLinkedList.insertBefore(nodeDoublyTemp,4);
doublyLinkedList.insertBefore(nodeDoublyTemp,4);
doublyLinkedList.insertBefore(nodeDoublyTemp,4);
doublyLinkedList.findAll();
System.out.println("==============================================");
doublyLinkedList.deleteByNode(nodeDoublyTemp);
doublyLinkedList.findAll();
System.out.println("==============================================");
doublyLinkedList.deleteByValue(4);
doublyLinkedList.findAll();
System.out.println("==============================================");
NodeDoubly nodeDoublyTemp9 = doublyLinkedList.findByValueLast(9);
doublyLinkedList.deleteByNode(nodeDoublyTemp9);
NodeDoubly nodeDoublyTemp7 = doublyLinkedList.findByValueFirst(7);
doublyLinkedList.deleteByNode(nodeDoublyTemp7);
doublyLinkedList.findAll();
System.out.println("==============================================");
}
项目连接
请配合项目代码食用效果更佳：
项目地址：
https://github.com/hesuijin/hesuijin-algo
Git下载地址：
https://github.com.cnpmjs.org/hesuijin/hesuijin-algo.git
linkedCollection包
网友评论