Java線性結(jié)構(gòu)中的雙向鏈表實現(xiàn)原理
一. 雙向鏈表簡介
1. 概念
在上一篇文章中，我們在介紹鏈表的種類時，曾經(jīng)提到過雙向鏈表。雙向鏈表相比較于單鏈表，除數(shù)據(jù)域外，還具前和后兩個指向指針。
雙向鏈表中的結(jié)構(gòu)術(shù)語可以解釋為：
- data：鏈表每個結(jié)點中存儲的數(shù)據(jù)域；
- next：鏈表每個結(jié)點中包含的指向下一個結(jié)點地址的指針域；
- prev：鏈表每個結(jié)點中包含的前一個結(jié)點地址的指針域。
2. 編碼定義
根據(jù)上述對雙向鏈表結(jié)點的定義，我們給出雙向鏈表結(jié)點結(jié)構(gòu)的Java定義實現(xiàn)：
class DNode{
Object data;
Node prev;
Node next;
}雙向鏈表是一條真實存在的鏈表，由多個結(jié)點組成。在實際的編程中，通常會標(biāo)記鏈表的兩個特殊結(jié)點，分別為：頭結(jié)點、尾結(jié)點。用另外一個變量size表示鏈表中元素的個數(shù)。
- 頭結(jié)點：鏈表中的第一個結(jié)點
- 尾結(jié)點：鏈表中的最后一個元素
因此有如下鏈表類的定義：
public class DoubleLinkList{
private int size;//大小
private DNode head;//頭結(jié)點
private DNode last;//尾結(jié)點
}在本篇文章接下來的內(nèi)容中，我們將利用該DNode、DoubleLinkList兩個定義來實現(xiàn)雙向鏈表的各項操作。
二. 常見操作
因為雙向鏈表是單鏈表的基礎(chǔ)上擴(kuò)展出來的結(jié)構(gòu)，因此雙向鏈表的很多操作與單鏈表的操作都是相同的，比如：查找元素、更新元素、插入元素、刪除元素。
1. 查找元素
1.1 查找頭結(jié)點
因為DoubleLinkList中已經(jīng)記錄了頭結(jié)點head，因此頭結(jié)點的查找非常簡單，如下：
public Object getHead(){
if(head == null){
return null;
}
return head.data;
}時間復(fù)雜度為O(1)。
1.2 查找尾結(jié)點
與頭結(jié)點同理，查找尾結(jié)點的時間復(fù)雜度同樣為O(1），編碼如下：
public Object getLast(){
if(last == null){
return null;
}
return last.data;
}1.3 查找指定位置結(jié)點
當(dāng)需要查找指定位置的結(jié)點元素時，雙向鏈表比單鏈表的實現(xiàn)方式有所不同，原因是：單鏈表因為是單向的，因此只能從頭結(jié)點向后單向查找；但雙向鏈表前后均可查找，因此在進(jìn)行指定位置查找時，為了提高查找效率，會首先判斷要查找的位置處于鏈表的前半段還是后半段，若前半段則從頭結(jié)點向后查找，若后半段則從尾結(jié)點向前查找，具體編程如下所示：
public Object get(int index){
//排除邊界異常
if(index <0 || index>=size){
return null;
}
//要查找的位置位于鏈表前半段
if(index < (size>>1)){
DNode x = head;
for(int i = 0; i < index; i++){
x = x.next;
}
return x.data;
}else {//要查找的位置位于鏈表后半段
DNode x = last;
for(int i = size - 1; i >= index; i--){
x = x.prev;
}
return x.data;
}
}在上述代碼中，size >> 1 的寫法比較少見，“>>”在計算機(jī)編程中代表移位操作。常見的移位操作有兩種：
>>：向右移位操作，將一個二進(jìn)制位的操作數(shù)按指定移動的位數(shù)向右移動，移出位被丟棄，左邊移出的空位一律補(bǔ)0，或者補(bǔ)符號位。
<<：向左移位操作，將一個二進(jìn)制位的操作數(shù)按指定移動的位數(shù)向左移動，移出位被丟棄，右邊移出的空位一律補(bǔ)0。
通過實際的編程驗證，我們可以知道：執(zhí)行右移1位操作，變量數(shù)據(jù)會縮小為原來的1/2。左移相反。同時，我們可以分析出時間復(fù)雜度為O(n)。
2. 更新元素
更新元素操作需要兩步：
- 找到要更新的元素
- 執(zhí)行更新操作
根據(jù)位置的不同，可以將更新操作分為三種情況：更新頭結(jié)點，更新尾結(jié)點，更新指定位置結(jié)點。
2.1 更新頭結(jié)點
更新頭結(jié)點代碼與查找頭結(jié)點類似，如下：
public boolean updateHead(Object obj){
if(head == null){
return false;
}
head.data = obj;
return true;
}更新頭結(jié)點的時間復(fù)雜度為O(1)。
2.2 更新尾結(jié)點
public boolean updateLast(Object obj){
if(last == null){
return false;
}
last.data = obj;
}更新尾結(jié)點的時間復(fù)雜度同樣是O(1)。
2.3 更新指定位置結(jié)點
public boolean update(int index, Object obj){
if(index < 0 || index >= size){
return false;
}
if(index < (size>>1)){
DNode x = head;
for(int i = 0; i < index; i++){
x = x.next;
}
x.data = obj;
}else {
DNode x = last;
for(int i = size-1; i >= index; i--){
x = last.prev;
}
x.data = obj;
}
return true;
}如上代碼所示，修改指定結(jié)點元素的值采用的算法也是：先判斷要操作的位置在前半段還是后半段，然后再進(jìn)行精準(zhǔn)查找，最后執(zhí)行修改操作。
指定位置修改操作的時間復(fù)雜度為O(n)。
3. 插入元素
分析過了查找元素和更新元素操作的具體情況，我們很清晰的便能分析出插入元素操作的具體情況，其實也分為三種具體情景：頭結(jié)點位置插入，尾結(jié)點位置插入，指定位置插入元素。
3.1 頭結(jié)點位置插入
public boolean addHead(Object data){
DNode h = head;
DNode newNode = new DNode(null,data,h);
head = newNode;
if(h == null);{
last = newNode;
}else {
h.prev = newNode;
}
size++;
return true;
}根據(jù)如上代碼，我們可以看到，在頭結(jié)點位置插入新的元素，只需要將新添加的結(jié)點置為head結(jié)點，同時處理好新結(jié)點和原鏈表中頭結(jié)點的指向關(guān)系即可。很明顯，頭結(jié)點位置插入的時間復(fù)雜度為O(1)。
3.2 尾結(jié)點位置插入
尾結(jié)點插入與頭結(jié)點插入原理相同，只需要替換為尾結(jié)點以及指針的指向。如下所示：
public boolean addLast(Object data){
DNode l = last;
DNode newNode = new DNode(l,data,null);
last = newNode;
if(last == null){
head = last;
}else {
l.next = newNode;
}
size++;
return true;
}時間復(fù)雜度為O(1)。
3.3 指定位置插入
在進(jìn)行指定位置插入時，編程代碼稍多些，原因是需要以下幾步完成：
- 判斷插入的位置是否超范圍
- 若插入的位置在最后，則執(zhí)行在尾結(jié)點的插入邏輯
- 先根據(jù)要插入的位置，查找并獲取到對應(yīng)位置的結(jié)點元素
- 然后執(zhí)行插入邏輯
public boolean add(int index,Object data){
if(index < 0 || index > size){
return false;
}
if(index == size){
addLast(data);
return true;
}else {
//先找到要插入的指定位置的結(jié)點
DNode x = index(index);
//執(zhí)行插入操作
DNode prevNode = x.prev;
DNode newNode = new DNode(prevNode,data,x);
x.prev = newNode;
if(prevNode == null){
head = newNode;
}else {
prevNode.next = newNode;
}
size++;
}
}
//查找index位置上的結(jié)點并返回
public DNode index(int index){
if( index < 0 || index >= size){
return null;
}
if( index < (size>>1)){
DNode x = head;
for(int i = 0; i < index; i++){
x = x.next;
}
return x;
}else {
DNode x = last;
for(int i = size-1; i >= index; i--){
x = x.prev;
}
return x;
}
}根據(jù)上述代碼，我們可以發(fā)現(xiàn)插入指定位置的代碼，需要用到查找指定位置的操作，先查找再插入，因此時間復(fù)雜度同樣為O(n)。
4. 刪除元素
有了前面的分析經(jīng)驗，我們可以非常自然的分析出刪除操作同樣分三種：刪除頭結(jié)點、刪除尾結(jié)點、刪除指定結(jié)點。接下來，一起來看看詳細(xì)的情況：
4.1 刪除頭結(jié)點
public Object removeHead(){
if(head == null){
return null;
}
DNode h = head;
Object data = h.data;
DNode next = h.next;
//將原來頭結(jié)點的數(shù)據(jù)域和指針域均賦值為null置空
h.data = null;
h.next = null;
//將當(dāng)前結(jié)點的next作為新的頭結(jié)點
head = next;
//如果next為null，則說明當(dāng)前鏈表只有一個節(jié)點，刪除該節(jié)點，則鏈表的first、last都為null
if(next == null){
last = null;
}else {
// next要作為新的頭節(jié)點，則其prev屬性為null
next.prev = null;
}
size--;
return data;
}刪除頭結(jié)點只涉及頭結(jié)點的邏輯判斷和操作，因此刪除頭結(jié)點時間復(fù)雜度為O(1)。
4.2 刪除尾結(jié)點
與刪除頭結(jié)點原理相同，操作尾結(jié)點。代碼如下：
public Object removeLast(){
DNode l = last;
if(l == null){
return null;
}
Object data = l.data;
DNode prev = l.prev;
//將當(dāng)前尾節(jié)點的屬性賦值為null，為了GC清理
l.data = null;
l.prev = null;
// 讓當(dāng)前尾節(jié)點的prev作為新的尾節(jié)點，賦值給last屬性
last = prev;
// 如果prev為null，則說明當(dāng)前鏈表只有一個節(jié)點，刪除該節(jié)點，則鏈表的first、last都為null
if(prev == null){
head = null;
}else {
// prev要作為新的尾節(jié)點，則其next屬性為null
prev.next = null;
}
size--;
return data;
}很明顯，刪除尾結(jié)點的時間復(fù)雜度為O(1)。
4.3 刪除指定結(jié)點
刪除指定結(jié)點的編碼實現(xiàn)如下：
public Object remove(int index){
if(index < 0 || index >= size){
return null;
}
//首先通過查找方法，查找到
DNode node = index(index;
//執(zhí)行刪除操作
Object data = node.data;
DNode next = node.next;
DNode prev = node.prev;
// 如果prev是null，則說明刪除的是當(dāng)前頭節(jié)點，則將next作為新的頭節(jié)點，賦值給head
if(prev == null){
head = prev;
}else {
// 如果刪除的不是當(dāng)前頭節(jié)點，則將要刪除節(jié)點的prev與next連接一起，即將prev的next屬性賦值成next
prev.next = next;
// 如果prev不是null，則賦值為null
node.prev = null;
}
// 如果next是null，則說明刪除的是當(dāng)前尾節(jié)點，則將prev作為新的尾節(jié)點，賦值給last
if(next == null){
last = prev;
}else {
// 如果刪除的不是當(dāng)前尾節(jié)點，則將要刪除節(jié)點的prev與next連接一起，即將next的prev賦值成prev
next.prev = prev;
// 如果next不是null，則賦值為null
node.next = null;
}
//將要刪除的結(jié)點的data數(shù)據(jù)域設(shè)置為null
node.data = null;
//鏈表的結(jié)點個數(shù)-1操作
size--;
return data;
}如上代碼所示，刪除指定位置的結(jié)點元素也需要先執(zhí)行index(index)查找算法，至于index的實現(xiàn)，在前文介紹指定位置插入結(jié)點操作時，已經(jīng)進(jìn)行了實現(xiàn)，此處直接進(jìn)行使用。
我們不難分析得到，刪除指定位置的結(jié)點的時間復(fù)雜度是O(n)。
三. 其他操作
作為一種常見的數(shù)據(jù)結(jié)構(gòu)，除了對自身結(jié)點元素的一些操作，還有一些對鏈表狀態(tài)的獲取，比如鏈表的長度，鏈表是否為空等，這里給大家介紹一下雙向鏈表的一些其他操作。
1. 鏈表的大小(元素結(jié)點的個數(shù))
public int size(){
return size;
}2. 判斷鏈表是否為空
public boolean isEmpty(){
return size == 0;
}3. 獲取鏈表元素組成的數(shù)組
public Object[] toArray(){
Object[] result = new Object[size];
int i = 0;
for(DNode node = head; node != null; node = node.next){
resunt[i++] = node.data;
}
return result;
}4. 清空鏈表
public void clear(){
for(DNode node = head; node != null; ){
DNode next = node.next;
node.data = null;
node.next = null;
node.prev = null;
node = next;
}
head = last = null;
size = 0;
}四. 結(jié)語
至此，已經(jīng)連續(xù)用兩篇文章給大家介紹了鏈表的相關(guān)知識。在上一篇文章中，我們主要介紹了鏈表的基礎(chǔ)知識和單鏈表的常規(guī)操作，同時輔以圖示來說明各種操作情況。在本篇文章中，主要是從Java編程角度作為切入點，來進(jìn)一步講解雙向鏈表的一些操作。特別是本篇文章中的大量代碼實踐，需要大家能夠理清邏輯關(guān)系，希望你可以動手練起來哦。
以上就是Java線性結(jié)構(gòu)中的雙向鏈表實現(xiàn)原理的詳細(xì)內(nèi)容，更多關(guān)于Java 雙向鏈表實現(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Spring Boot啟動過程（六）之內(nèi)嵌Tomcat中StandardHost、StandardContext和Sta
這篇文章主要介紹了Spring Boot啟動過程（六）之內(nèi)嵌Tomcat中StandardHost、StandardContext和StandardWrapper的啟動教程詳解,需要的朋友可以參考下2017-04-04
Java線程編程中isAlive()和join()的使用詳解
這篇文章主要介紹了Java線程編程中isAlive()和join()的使用詳解,是Java入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
spring boot實現(xiàn)上傳圖片并在頁面上顯示及遇到的問題小結(jié)
最近在使用spring boot搭建網(wǎng)站的過程之中遇到了有點小問題，最終解決方案是在main目錄下新建了一個webapp文件夾，并且對其路徑進(jìn)行了配置，本文重點給大家介紹spring boot實現(xiàn)上傳圖片并在頁面上顯示功能，需要的朋友參考下吧2017-12-12
在應(yīng)用里經(jīng)常都有用到在后臺跑定時任務(wù)的需求。舉個例子，比如需要在服務(wù)后臺跑一個定時任務(wù)來進(jìn)行垃圾回收2014-04-04
spring bean標(biāo)簽的primary屬性用法講解
這篇文章主要介紹了spring bean標(biāo)簽的primary屬性用法講解，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
Springboot如何通過filter修改Header的值
這篇文章主要介紹了Springboot如何通過filter修改Header的值問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-07-07
這篇文章主要介紹了springboot2.4跨域配置的方法，本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-07-07
詳解Java中的do...while循環(huán)語句的使用方法
這篇文章主要介紹了Java中的do...while循環(huán)語句的使用方法,是Java入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-10-10
這篇文章主要為大家詳細(xì)介紹了java精品項目-瑞吉外賣訂餐系統(tǒng)，此項目過大，分為多章獨立講解，本篇內(nèi)容為員工信息分頁查詢與啟用或禁用員工狀態(tài)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要介紹了Java為什么使用補(bǔ)碼進(jìn)行計算的原因分析，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-08-08