Java中雙向鏈表詳解及實(shí)例
Java中雙向鏈表詳解及實(shí)例
寫(xiě)在前面:
雙向鏈表是一種對(duì)稱結(jié)構(gòu),它克服了單鏈表上指針單向性的缺點(diǎn),其中每一個(gè)節(jié)點(diǎn)即可向前引用,也可向后引用,這樣可以更方便的插入、刪除數(shù)據(jù)元素。
由于雙向鏈表需要同時(shí)維護(hù)兩個(gè)方向的指針,因此添加節(jié)點(diǎn)、刪除節(jié)點(diǎn)時(shí)指針維護(hù)成本更大;但雙向鏈表具有兩個(gè)方向的指針,因此可以向兩個(gè)方向搜索節(jié)點(diǎn),因此雙向鏈表在搜索節(jié)點(diǎn)、刪除指定索引處節(jié)點(diǎn)時(shí)具有較好的性能。
Java語(yǔ)言實(shí)現(xiàn)雙向鏈表:
package com.ietree.basic.datastructure.dublinklist; /** * 雙向鏈表 * * @author Dylan */ public class DuLinkList<T> { // 定義一個(gè)內(nèi)部類Node,Node實(shí)例代表鏈表的節(jié)點(diǎn) private class Node { // 保存節(jié)點(diǎn)的數(shù)據(jù) private T data; // 保存上個(gè)節(jié)點(diǎn)的引用 private Node prev; // 指向下一個(gè)節(jié)點(diǎn)的引用 private Node next; // 無(wú)參構(gòu)造器 public Node() { } // 初始化全部屬性的構(gòu)造器 public Node(T data, Node prev, Node next) { this.data = data; this.prev = prev; this.next = next; } } // 保存該鏈表的頭節(jié)點(diǎn) private Node header; // 保存該鏈表的尾節(jié)點(diǎn) private Node tail; // 保存該鏈表中已包含的節(jié)點(diǎn)數(shù) private int size; // 創(chuàng)建空鏈表 public DuLinkList() { // 空鏈表,header和tail都是null header = null; tail = null; } // 以指定數(shù)據(jù)元素來(lái)創(chuàng)建鏈表,該鏈表只有一個(gè)元素 public DuLinkList(T element) { header = new Node(element, null, null); // 只有一個(gè)節(jié)點(diǎn),header、tail都指向該節(jié)點(diǎn) tail = header; size++; } // 返回鏈表的長(zhǎng)度 public int length() { return size; } // 獲取鏈?zhǔn)骄€性表中索引為index處的元素 public T get(int index) { return getNodeByIndex(index).data; } // 根據(jù)索引index獲取指定位置的節(jié)點(diǎn) public Node getNodeByIndex(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("線性表索引越界"); } if (index <= size / 2) { // 從header節(jié)點(diǎn)開(kāi)始 Node current = header; for (int i = 0; i <= size / 2 && current != null; i++, current = current.next) { if (i == index) { return current; } } } else { // 從tail節(jié)點(diǎn)開(kāi)始搜索 Node current = tail; for (int i = size - 1; i > size / 2 && current != null; i++, current = current.prev) { if (i == index) { return current; } } } return null; } // 查找鏈?zhǔn)骄€性表中指定元素的索引 public int locate(T element) { // 從頭結(jié)點(diǎn)開(kāi)始搜索 Node current = header; for (int i = 0; i < size && current != null; i++, current = current.next) { if (current.data.equals(element)) { return i; } } return -1; } // 向線性鏈表的指定位置插入一個(gè)元素 public void insert(T element, int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("線性表索引越界"); } // 如果還是空鏈表 if (header == null) { add(element); } else { // 當(dāng)index為0時(shí),也就是在鏈表頭處插入 if (index == 0) { addAtHeader(element); } else { // 獲取插入點(diǎn)的前一個(gè)節(jié)點(diǎn) Node prev = getNodeByIndex(index - 1); // 獲取插入點(diǎn)的節(jié)點(diǎn) Node next = prev.next; // 讓新節(jié)點(diǎn)的next引用指向next節(jié)點(diǎn),prev引用指向prev節(jié)點(diǎn) Node newNode = new Node(element, prev, next); // 讓prev的next節(jié)點(diǎn)指向新節(jié)點(diǎn) prev.next = newNode; // 讓prev的下一個(gè)節(jié)點(diǎn)的prev指向新節(jié)點(diǎn) next.prev = newNode; size++; } } } // 采用尾插法為鏈表添加新節(jié)點(diǎn) public void add(T element) { // 如果該鏈表還是空鏈表 if (header == null) { header = new Node(element, null, null); // 只有一個(gè)節(jié)點(diǎn),header、tail都指向該節(jié)點(diǎn) tail = header; } else { // 創(chuàng)建新節(jié)點(diǎn),新節(jié)點(diǎn)的pre指向原tail節(jié)點(diǎn) Node newNode = new Node(element, tail, null); // 讓尾節(jié)點(diǎn)的next指向新增的節(jié)點(diǎn) tail.next = newNode; // 以新節(jié)點(diǎn)作為新的尾節(jié)點(diǎn) tail = newNode; } size++; } // 采用頭插法為鏈表添加新節(jié)點(diǎn) public void addAtHeader(T element) { // 創(chuàng)建新節(jié)點(diǎn),讓新節(jié)點(diǎn)的next指向原來(lái)的header // 并以新節(jié)點(diǎn)作為新的header header = new Node(element, null, header); // 如果插入之前是空鏈表 if (tail == null) { tail = header; } size++; } // 刪除鏈?zhǔn)骄€性表中指定索引處的元素 public T delete(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("線性表索引越界"); } Node del = null; // 如果被刪除的是header節(jié)點(diǎn) if (index == 0) { del = header; header = header.next; // 釋放新的header節(jié)點(diǎn)的prev引用 header.prev = null; } else { // 獲取刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) Node prev = getNodeByIndex(index - 1); // 獲取將要被刪除的節(jié)點(diǎn) del = prev.next; // 讓被刪除節(jié)點(diǎn)的next指向被刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) prev.next = del.next; // 讓被刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的prev指向prev節(jié)點(diǎn) if (del.next != null) { del.next.prev = prev; } // 將被刪除節(jié)點(diǎn)的prev、next引用賦為null del.prev = null; del.next = null; } size--; return del.data; } // 刪除鏈?zhǔn)骄€性表中最后一個(gè)元素 public T remove() { return delete(size - 1); } // 判斷鏈?zhǔn)骄€性表是否為空表 public boolean empty() { return size == 0; } // 清空線性表 public void clear() { // 將底層數(shù)組所有元素賦為null header = null; tail = null; size = 0; } public String toString() { // 鏈表為空鏈表 if (empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = header; current != null; current = current.next) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } } // 倒序toString public String reverseToString() { if (empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = tail; current != null; current = current.prev) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } } }
測(cè)試類:
package com.ietree.basic.datastructure.dublinklist; /** * 測(cè)試類 * * @author Dylan */ public class DuLinkListTest { public static void main(String[] args) { DuLinkList<String> list = new DuLinkList<String>(); list.insert("aaaa", 0); list.add("bbbb"); list.insert("cccc", 0); // 在索引為1處插入一個(gè)新元素 list.insert("dddd", 1); // 輸出順序線性表的元素 System.out.println(list); // 刪除索引為2處的元素 list.delete(2); System.out.println(list); System.out.println(list.reverseToString()); // 獲取cccc字符串在順序線性表中的位置 System.out.println("cccc在順序線性表中的位置:" + list.locate("cccc")); System.out.println("鏈表中索引1處的元素:" + list.get(1)); list.remove(); System.out.println("調(diào)用remove方法后的鏈表:" + list); list.delete(0); System.out.println("調(diào)用delete(0)后的鏈表:" + list); } }
程序輸出:
[cccc, dddd, aaaa, bbbb] [cccc, dddd, bbbb] [bbbb, dddd, cccc] cccc在順序線性表中的位置:0 鏈表中索引1處的元素:dddd 調(diào)用remove方法后的鏈表:[cccc, dddd] 調(diào)用delete(0)后的鏈表:[dddd]
感謝閱讀,希望能幫助到大家,謝謝大家對(duì)本站的支持!
- java數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)雙向鏈表的示例
- Java實(shí)現(xiàn)雙向鏈表(兩個(gè)版本)
- java 實(shí)現(xiàn)雙向鏈表實(shí)例詳解
- Java語(yǔ)言中鏈表和雙向鏈表
- JAVA實(shí)現(xiàn)雙向鏈表的增刪功能的方法
- java中使用雙向鏈表實(shí)現(xiàn)貪吃蛇程序源碼分享
- java實(shí)現(xiàn)單鏈表、雙向鏈表
- Java雙向鏈表按照順序添加節(jié)點(diǎn)的方法實(shí)例
- java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ):單鏈表與雙向鏈表
- 基于Java實(shí)現(xiàn)雙向鏈表
相關(guān)文章
詳解Java使用Jsch與sftp服務(wù)器實(shí)現(xiàn)ssh免密登錄
這篇文章主要介紹了詳解Java使用Jsch與sftp服務(wù)器實(shí)現(xiàn)ssh免密登錄,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-10-10詳解如何使用Spring的@FeignClient注解實(shí)現(xiàn)通信功能
SpringBoot是一個(gè)非常流行的Java框架,它提供了一系列工具來(lái)使這種交互無(wú)縫且高效,在這些工具中,@FeignClient注解因其易用性和強(qiáng)大的功能而脫穎而出, 在這篇文章中,我們將探討如何使用Spring的@FeignClient注解進(jìn)行客戶端-服務(wù)器通信,需要的朋友可以參考下2023-11-11Web容器啟動(dòng)過(guò)程中如何執(zhí)行Java類
這篇文章主要介紹了Web容器啟動(dòng)過(guò)程中如何執(zhí)行Java類,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-10-10java實(shí)現(xiàn)坦克大戰(zhàn)小游戲
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)坦克大戰(zhàn)小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-01-01freemarker?jsp?java內(nèi)存方式實(shí)現(xiàn)分頁(yè)示例
這篇文章主要介紹了freemarker?jsp?java內(nèi)存方式實(shí)現(xiàn)分頁(yè)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-06-06Java日期工具類操作字符串Date和LocalDate互轉(zhuǎn)
這篇文章主要介紹了Java日期工具類操作字符串Date和LocalDate互轉(zhuǎn),文章首先通過(guò)需要先引入坐標(biāo)展開(kāi)主題的相關(guān)內(nèi)容介紹,需要的朋友可以參一下2022-06-06Java基于面向?qū)ο髮?shí)現(xiàn)一個(gè)戰(zhàn)士小游戲
這篇文章主要為大家詳細(xì)介紹了Java如何基于面向?qū)ο髮?shí)現(xiàn)一個(gè)戰(zhàn)士小游戲,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以動(dòng)手嘗試一下2022-07-07