實(shí)際：位于鏈表頭部的節(jié)點(diǎn) 隘道； 自己定義（也可以不定義該變量）：鏈表頭部的節(jié)點(diǎn)自定義為head（first）蚕甥； 官方定義：若只有指針為頭節(jié)點(diǎn) 否則為普通節(jié)點(diǎn) 酷含；
實(shí)際：位于鏈表尾部的節(jié)點(diǎn) 成肘； 自己定義（也可以不定義該變量）：鏈表尾部的節(jié)點(diǎn)自定義為tail（last） 燃乍； 官方定義：若只有指針為尾節(jié)點(diǎn) 否則為普通節(jié)點(diǎn) ；
1：仿寫一個LinkedList鏈表
主要為仿寫JDK1.8的LinkedList鏈表
無頭節(jié)點(diǎn) 無尾節(jié)點(diǎn) 的 雙向非循環(huán)鏈表
位置位于鏈表的頭部（自定義為head（first）），如果有數(shù)據(jù)為普通節(jié)點(diǎn)（稱為位于頭部的節(jié)點(diǎn)） 如果只有指針為頭節(jié)點(diǎn)
位置位于鏈表的尾部（自定義為tail（last））， 如果有數(shù)據(jù)為普通節(jié)點(diǎn)（稱為位于尾部的節(jié)點(diǎn)） 如果只有指針為尾節(jié)點(diǎn)
頭節(jié)點(diǎn)與無頭節(jié)點(diǎn) 尾節(jié)點(diǎn)與無尾節(jié)點(diǎn)
不管是單向鏈表 還是 雙向鏈表都可以設(shè)置有無頭尾節(jié)點(diǎn)
單（雙）向鏈表：有頭節(jié)點(diǎn) 無尾節(jié)點(diǎn)
單（雙）向鏈表：無頭節(jié)點(diǎn) 有尾節(jié)點(diǎn)
單（雙）向鏈表：有頭節(jié)點(diǎn) 有尾節(jié)點(diǎn)
單（雙）向鏈表：無頭節(jié)點(diǎn) 無尾節(jié)點(diǎn)
雙向鏈表與單向鏈表的區(qū)別：
雙向鏈表與單向鏈表只有一個區(qū)別 雙向鏈表的節(jié)點(diǎn)可以指向前節(jié)點(diǎn) 而 單向鏈表沒有
單向鏈表 由于沒有前指針 因此其處于尾部的節(jié)點(diǎn)（有數(shù)據(jù)）匀泊，
可以進(jìn)行數(shù)據(jù)插入 但不能進(jìn)行倒序遍歷 ；
雙向鏈表 由于具有前指針 因此其尾節(jié)點(diǎn)（只有指針）或者 處于尾部的節(jié)點(diǎn)（有數(shù)據(jù)）朵你，
可以進(jìn)行數(shù)據(jù)插入 倒序遍歷各聘；
單向鏈表：通常不自定義位于鏈表的尾部 tail（last）
雙向鏈表：通常會自定義位于鏈表的尾部 tail（last）
2：節(jié)點(diǎn)
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：無頭節(jié)點(diǎn) 無尾節(jié)點(diǎn) 的 雙向非循環(huán)鏈表代碼
public class DoublyLinkedList<E> {
//初始化 無頭節(jié)點(diǎn)（頭節(jié)點(diǎn)為空）
private NodeDoubly<E> first ;
//初始化 無尾節(jié)點(diǎn)（尾節(jié)點(diǎn)為空）
private NodeDoubly<E> last ;
//無頭結(jié)點(diǎn)
//表頭部插入
public void insertAsfirst(E value) {
NodeDoubly<E> newNodeDoubly = new NodeDoubly(null,value,null );
insertTofirst(newNodeDoubly);
}
// LinkedList源碼閱讀
// 首次插入：
// 1：f = null
// 2： 新節(jié)點(diǎn)的next 指向 null
// 3：first 等于新節(jié)點(diǎn)
// 4：如果 f 為 null ： last 也等于新節(jié)點(diǎn)
//
//
// 之后插入：
// 1：f 不為null
// 2：新節(jié)點(diǎn) 的next 指向 f 原頭節(jié)點(diǎn)
// 3：first 等于新節(jié)點(diǎn) （next 指向 f 原頭節(jié)點(diǎn)）
// 4：如果 f 不為 null ： f 原頭節(jié)點(diǎn) 的prev 指向新節(jié)點(diǎn)
//
// 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++;
// }
//表頭部插入頭節(jié)點(diǎn) 同時尾節(jié)點(diǎn)也頭節(jié)點(diǎn)
//注意 first 與 last 一開始會指向相同的節(jié)點(diǎn)
//假如修改了first 的地址指向 last還是指向原節(jié)點(diǎn)
private void insertTofirst(NodeDoubly newNodeDoubly) {
//創(chuàng)建一個節(jié)點(diǎn)該節(jié)點(diǎn)同時為 頭節(jié)點(diǎn)與尾節(jié)點(diǎn)
if (first == null) {
first = newNodeDoubly;
last = newNodeDoubly;
} else {
//新節(jié)點(diǎn) next 指向 原first
newNodeDoubly.next = first;
//原first pre 指向 新節(jié)點(diǎn)
first.prev = newNodeDoubly;
//first變量名的 指針指向 變?yōu)樾鹿?jié)點(diǎn)
first = newNodeDoubly;
}
}
//在某節(jié)點(diǎn)上前 插入新節(jié)點(diǎn)
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;
}
//判斷原有節(jié)點(diǎn)是否為頭節(jié)點(diǎn)
if (first == originalNodeDoubly) {
insertTofirst(newNodeDoubly);
return;
}
//以頭節(jié)點(diǎn)開始 使用next進(jìn)行遍歷 一直到獲取到
// 遍歷節(jié)點(diǎn) 的下一個節(jié)點(diǎn)為需要查找的某節(jié)點(diǎn)為止
NodeDoubly<E> indexNodeDoubly = first;
while (indexNodeDoubly != null && indexNodeDoubly.next != originalNodeDoubly) {
indexNodeDoubly = indexNodeDoubly.next;
}
if (indexNodeDoubly == null) {
return;
}
//最后順序 遍歷節(jié)點(diǎn) 新節(jié)點(diǎn) 某節(jié)點(diǎn)
//實(shí)現(xiàn)了 新節(jié)點(diǎn)插入到原節(jié)點(diǎn)之前的功能
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 );
//創(chuàng)建一個節(jié)點(diǎn)該節(jié)點(diǎn)同時為 頭節(jié)點(diǎn)與尾節(jié)點(diǎn)
if (last == null) {
first = newNodeDoubly;
last = newNodeDoubly;
} else {
//新節(jié)點(diǎn) next 指向 原last
newNodeDoubly.prev = last;
//原last next 指向 新節(jié)點(diǎn)
last.next = newNodeDoubly;
//last變量名的 指針指向 變?yōu)樾鹿?jié)點(diǎn)
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;
//以頭節(jié)點(diǎn)開始 使用next進(jìn)行遍歷 一直獲取到
// 遍歷節(jié)點(diǎn) 的下一個節(jié)點(diǎn)為原節(jié)點(diǎn)為止
while (indexNodeDoubly != null && indexNodeDoubly.next != originalNodeDoubly) {
indexNodeDoubly = indexNodeDoubly.next;
}
if (indexNodeDoubly == null) {
return;
}
//獲取到 遍歷節(jié)點(diǎn) 某節(jié)點(diǎn)
//最后 遍歷節(jié)點(diǎn) 直接指向 遍歷節(jié)點(diǎn)的下個節(jié)點(diǎn)（原節(jié)點(diǎn)）的下一個節(jié)點(diǎn)
// 遍歷節(jié)點(diǎn)的下個節(jié)點(diǎn)（原節(jié)點(diǎn)）的下一個節(jié)點(diǎn) 的前節(jié)點(diǎn) 指向新節(jié)點(diǎn)
//實(shí)現(xiàn)了 被刪除的某節(jié)點(diǎn)就會被跳過
indexNodeDoubly.next = indexNodeDoubly.next.next;
indexNodeDoubly.next.prev = indexNodeDoubly;
}
//根據(jù)value刪除節(jié)點(diǎn)
public void deleteByValue(E value){
NodeDoubly<E> indexNodeDoubly = first;
//外部接口調(diào)用 第一次為從 頭節(jié)點(diǎn)進(jìn)行遍歷
deleteByValueRepetition(value, indexNodeDoubly);
}
//通過遞歸 根據(jù)value 刪除所有擁有該value的節(jié)點(diǎn)
public void deleteByValueRepetition(E value, NodeDoubly<E> indexNodeDoubly) {
if (first == null && last == null) {
return;
}
NodeDoubly<E> beforeIndexNodeDoubly = null;
// 以頭節(jié)點(diǎn)開始 使用next進(jìn)行遍歷 一直到獲取到為止
// 遍歷節(jié)點(diǎn) 的 data 為所需要查找的data為止
// 該遍歷節(jié)點(diǎn)是需要刪除的 因此還需要查找出前一個節(jié)點(diǎn)
while (indexNodeDoubly != null && indexNodeDoubly.data != value) {
beforeIndexNodeDoubly = indexNodeDoubly;
indexNodeDoubly = indexNodeDoubly.next;
}
if (indexNodeDoubly == null) {
return;
}
//查找到data的節(jié)點(diǎn)為 頭節(jié)點(diǎn)
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 可以進(jìn)行遞歸刪除
deleteByValueRepetition(value, beforeIndexNodeDoubly);
}
//查找節(jié)點(diǎn)的data
public NodeDoubly<E> findByValueFirst(E value) {
NodeDoubly<E> indexNodeDoubly = first;
while (indexNodeDoubly != null && indexNodeDoubly.data != value) {
indexNodeDoubly = indexNodeDoubly.next;
}
return indexNodeDoubly;
}
//查找節(jié)點(diǎn)的data
public NodeDoubly<E> findByValueLast(E value) {
NodeDoubly<E> indexNodeDoubly = last;
while (indexNodeDoubly != null && indexNodeDoubly.data != value) {
indexNodeDoubly = indexNodeDoubly.prev;
}
return indexNodeDoubly;
}
//打印所有數(shù)據(jù)
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);
//不同于單向鏈表從頭部開始遍歷 然后插入 雙向鏈表可以直接從尾部進(jìn)行插入
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("==============================================");
}
項(xiàng)目連接
請配合項(xiàng)目代碼食用效果更佳：
項(xiàng)目地址：
https://github.com/hesuijin/hesuijin-algo
Git下載地址：
https://github.com.cnpmjs.org/hesuijin/hesuijin-algo.git
linkedCollection包
