Java實現(xiàn)無頭雙向鏈表操作
更新時間：2022年01月20日 16:26:37 作者：Sasura_321
這篇文章主要為大家詳細(xì)介紹了Java實現(xiàn)無頭雙向鏈表的基本操作，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
本文實例為大家分享了Java實現(xiàn)無頭雙向鏈表的具體代碼，供大家參考，具體內(nèi)容如下
無頭雙向鏈表的結(jié)構(gòu)：
代碼分析
節(jié)點結(jié)構(gòu)
class Node {
? ? private int data;
? ? private Node next;
? ? private Node prev;
? ? public Node(int data) {
? ? ? ? this.data = data;
? ? ? ? this.prev = null;
? ? ? ? this.next = null;
? ? }
}
?? ?private Node head; ?// 頭節(jié)點
?? ?private Node last; ?// 尾節(jié)點
?? ?public DoubleLinked() {
? ? this.head = null;
? ? this.last = null;
}1. 頭插法
/**
* 1.頭插法
* @param data
*/
public void addFirst(int data) {
? ? Node node = new Node(data);
? ? if (this.head == null) {
? ? ? ? this.head = node;
? ? ? ? this.last = node;
? ? } else {
? ? ? ? node.next = this.head;
? ? ? ? this.head.prev = node;
? ? ? ? this.head = node;
? ? }
}先判斷鏈表是否為空，若為空，則直接插入，頭節(jié)點和尾節(jié)點都直接指向新插入的元素；
若鏈表不為空，則把要插入節(jié)點的 next 指向鏈表頭節(jié)點，頭節(jié)點的 prev 指向新插入的節(jié)點，最后更新頭節(jié)點為新插入節(jié)點，插入過程如下圖所示：
2. 尾插法
/**
* 2.尾插法
* @param data
*/
public void addLast(int data) {
? ? Node node = new Node(data);
? ? if (this.head == null) {
? ? ? ? this.head = node;
? ? ? ? this.last = node;
? ? } else {
? ? ? ? this.last.next = node;
? ? ? ? node.prev = this.last;
? ? ? ? this.last = node;
? ? }
}若鏈表為空，同頭插法；
若鏈表不為空，則把鏈表尾節(jié)點的 next 指向要插入節(jié)點，要插入節(jié)點的 prev 指向鏈表尾節(jié)點，最后更新尾節(jié)點為新插入節(jié)點，插入過程如下圖所示：
3. 查找是否包含關(guān)鍵字 key 在單鏈表中
// 查找
? ? private Node searchIndex(int index) {
? ? ? ? checkIndex(index);
? ? ? ? int count = 0;
? ? ? ? Node cur = this.head;
? ? ? ? while (count != index) {
? ? ? ? ? ? cur = cur.next;
? ? ? ? ? ? count++;
? ? ? ? }
? ? ? ? return cur;
? ? }
? ? // 合法性檢查
? ? private void checkIndex(int index) {
? ? ? ? if (index < 0 || index > getLength()) {
? ? ? ? ? ? throw new IndexOutOfBoundsException("下標(biāo)不合法！");
? ? ? ? }
? ? }
? ? /**
? ? ?* 3.任意位置插入，第一個數(shù)據(jù)節(jié)點為0號下標(biāo)
? ? ?* @param index 插入位置
? ? ?* @param data 插入的值
? ? ?* @return true/false
? ? ?*/
? ? @Override
? ? public boolean addIndex(int index, int data) {
? ? ? ? if (index ==0) {
? ? ? ? ? ? addFirst(data);
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? if (index == getLength()) {
? ? ? ? ? ? addLast(data);
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? // cur 指向index位置的節(jié)點
? ? ? ? Node cur = searchIndex(index);
? ? ? ? Node node = new Node(data);
? ? ? ? node.next = cur;
? ? ? ? cur.prev.next = node;
? ? ? ? node.prev = cur.prev;
? ? ? ? cur.prev = node;
? ? ? ? return true;
? ? }
4. 查找是否包含關(guān)鍵字 key 在單鏈表中
/**
?* 4.查找是否包含關(guān)鍵字 key 在單鏈表中
?* @param key 要查找的關(guān)鍵字
?* @return true/false
?*/
@Override
public boolean contains(int key) {
? ? Node cur = this.head;
? ? while (cur != null) {
? ? ? ? if (cur.data == key) {
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? cur = cur.next;
? ? }
? ? return false;
}5. 刪除第一次出現(xiàn)關(guān)鍵字為 key 的節(jié)點
/**
?* 5.刪除第一次出現(xiàn)關(guān)鍵字為 key 的節(jié)點
?* @param key
?* @return
?*/
@Override
public int remove(int key) {
? ? Node cur = this.head;
? ? int oldData = 0;
? ? while (cur != null) {
? ? ? ? if (cur.data == key) {
? ? ? ? ? ? oldData = cur.data;
? ? ? ? ? ? // 頭節(jié)點
? ? ? ? ? ? if (cur == this.head) {
? ? ? ? ? ? ? ? this.head = this.head.next;
? ? ? ? ? ? ? ? this.head.prev = null;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? // cur.next != null --->不是尾節(jié)點
? ? ? ? ? ? ? ? if (cur.next != null) {
? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev;
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? this.last = cur.prev;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? return oldData;
? ? ? ? }
? ? ? ? cur = cur.next;
? ? }
? ? return -1;
}
6. 刪除所有值為 key 的節(jié)點
/**
?* 6.刪除所有值為 key 的節(jié)點
?* @param key
?*/
@Override
public void removeAllKey(int key) {
? ? Node cur = this.head;
? ? while (cur != null) {
? ? ? ? if (cur.data == key) {
? ? ? ? ? ? // 頭節(jié)點
? ? ? ? ? ? if (cur == this.head) {
? ? ? ? ? ? ? ? this.head = this.head.next;
? ? ? ? ? ? ? ? this.head.prev = null;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? cur.prev.next = cur.next;
? ? ? ? ? ? ? ? // cur.next != null --->不是尾節(jié)點
? ? ? ? ? ? ? ? if (cur.next != null) {
? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev;
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? this.last = cur.prev;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? cur = cur.next;
? ? }
}7. 得到單鏈表的長度
/**
?* 7.得到單鏈表的長度
?* @return
?*/
@Override
public int getLength() {
? ? int count = 0;
? ? Node cur = this.head;
? ? while (cur != null) {
? ? ? ? count++;
? ? ? ? cur = cur.next;
? ? }
? ? return count;
}8. 打印鏈表
/**
?* 8.打印鏈表
?*/
@Override
public void display() {
? ? if (this.head == null) {
? ? ? ? return ;
? ? }
? ? Node cur = this.head;
? ? while (cur != null) {
? ? ? ? System.out.print(cur.data + " ");
? ? ? ? cur = cur.next;
? ? }
? ? System.out.println();
}9. 清空順序表以防內(nèi)存泄漏
/**
?* 9.清空順序表以防內(nèi)存泄漏
?*/
@Override
public void clear() {
? ? while(this.head != null) {
? ? ? ? Node cur = this.head.next;
? ? ? ? this.head.next = null;
? ? ? ? this.head.prev = null;
? ? ? ? this.head = cur;
? ? }
}接口、實現(xiàn)方法、測試
1. 接口
package com.github.doubly;
// 不帶頭節(jié)點單鏈表的實現(xiàn)
public interface IDoubleLinked {
? ? // 1.頭插法
? ? void addFirst(int data);
? ? // 2.尾插法
? ? void addLast(int data);
? ? // 3.任意位置插入，第一個數(shù)據(jù)節(jié)點為0號下標(biāo)
? ? boolean addIndex(int index, int data);
? ? // 4.查找是否包含關(guān)鍵字 key 在單鏈表中
? ? boolean contains(int key);
? ? // 5.刪除第一次出現(xiàn)關(guān)鍵字為 key 的節(jié)點
? ? int remove(int key);
? ? // 6.刪除所有值為 key 的節(jié)點
? ? void removeAllKey(int key);
? ? // 7.得到單鏈表的長度
? ? int getLength();
? ? // 8.打印鏈表
? ? void display();
? ? // 9.清空順序表以防內(nèi)存泄漏
? ? void clear();
}2. 實現(xiàn)方法
package com.github.doubly;
public class DoubleLinked implements IDoubleLinked {
? ? class Node {
? ? ? ? private int data;
? ? ? ? private Node next;
? ? ? ? private Node prev;
? ? ? ? public Node(int data) {
? ? ? ? ? ? this.data = data;
? ? ? ? ? ? this.prev = null;
? ? ? ? ? ? this.next = null;
? ? ? ? }
? ? }
? ? private Node head; ?// 頭節(jié)點
? ? private Node last; ?// 尾節(jié)點
? ? public DoubleLinked() {
? ? ? ? this.head = null;
? ? ? ? this.last = null;
? ? }
? ? /**
? ? ?* 1.頭插法
? ? ?* @param data
? ? ?*/
? ? @Override
? ? public void addFirst(int data) {
? ? ? ? Node node = new Node(data);
? ? ? ? if (this.head == null) {
? ? ? ? ? ? this.head = node;
? ? ? ? ? ? this.last = node;
? ? ? ? } else {
? ? ? ? ? ? node.next = this.head;
? ? ? ? ? ? this.head.prev = node;
? ? ? ? ? ? this.head = node;
? ? ? ? }
? ? }
? ? /**
? ? ?* 2.尾插法
? ? ?* @param data
? ? ?*/
? ? @Override
? ? public void addLast(int data) {
? ? ? ? Node node = new Node(data);
? ? ? ? if (this.head == null) {
? ? ? ? ? ? this.head = node;
? ? ? ? ? ? this.last = node;
? ? ? ? } else {
? ? ? ? ? ? this.last.next = node;
? ? ? ? ? ? node.prev = this.last;
? ? ? ? ? ? this.last = node;
? ? ? ? }
? ? }
? ? // 查找
? ? private Node searchIndex(int index) {
? ? ? ? checkIndex(index);
? ? ? ? int count = 0;
? ? ? ? Node cur = this.head;
? ? ? ? while (count != index) {
? ? ? ? ? ? cur = cur.next;
? ? ? ? ? ? count++;
? ? ? ? }
? ? ? ? return cur;
? ? }
? ? // 合法性檢查
? ? private void checkIndex(int index) {
? ? ? ? if (index < 0 || index > getLength()) {
? ? ? ? ? ? throw new IndexOutOfBoundsException("下標(biāo)不合法！");
? ? ? ? }
? ? }
? ? /**
? ? ?* 3.任意位置插入，第一個數(shù)據(jù)節(jié)點為0號下標(biāo)
? ? ?* @param index 插入位置
? ? ?* @param data 插入的值
? ? ?* @return true/false
? ? ?*/
? ? @Override
? ? public boolean addIndex(int index, int data) {
? ? ? ? if (index ==0) {
? ? ? ? ? ? addFirst(data);
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? if (index == getLength()) {
? ? ? ? ? ? addLast(data);
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? // cur 指向index位置的節(jié)點
? ? ? ? Node cur = searchIndex(index);
? ? ? ? Node node = new Node(data);
? ? ? ? node.next = cur;
? ? ? ? cur.prev.next = node;
? ? ? ? node.prev = cur.prev;
? ? ? ? cur.prev = node;
? ? ? ? return true;
? ? }
? ? /**
? ? ?* 4.查找是否包含關(guān)鍵字 key 在單鏈表中
? ? ?* @param key 要查找的關(guān)鍵字
? ? ?* @return true/false
? ? ?*/
? ? @Override
? ? public boolean contains(int key) {
? ? ? ? Node cur = this.head;
? ? ? ? while (cur != null) {
? ? ? ? ? ? if (cur.data == key) {
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? ? ? cur = cur.next;
? ? ? ? }
? ? ? ? return false;
? ? }
? ? /**
? ? ?* 5.刪除第一次出現(xiàn)關(guān)鍵字為 key 的節(jié)點
? ? ?* @param key
? ? ?* @return
? ? ?*/
? ? @Override
? ? public int remove(int key) {
? ? ? ? Node cur = this.head;
? ? ? ? int oldData = 0;
? ? ? ? while (cur != null) {
? ? ? ? ? ? if (cur.data == key) {
? ? ? ? ? ? ? ? oldData = cur.data;
? ? ? ? ? ? ? ? // 頭節(jié)點
? ? ? ? ? ? ? ? if (cur == this.head) {
? ? ? ? ? ? ? ? ? ? this.head = this.head.next;
? ? ? ? ? ? ? ? ? ? this.head.prev = null;
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? // cur.next != null --->不是尾節(jié)點
? ? ? ? ? ? ? ? ? ? if (cur.next != null) {
? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev;
? ? ? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? ? ? this.last = cur.prev;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return oldData;
? ? ? ? ? ? }
? ? ? ? ? ? cur = cur.next;
? ? ? ? }
? ? ? ? return -1;
? ? }
? ? /**
? ? ?* 6.刪除所有值為 key 的節(jié)點
? ? ?* @param key
? ? ?*/
? ? @Override
? ? public void removeAllKey(int key) {
? ? ? ? Node cur = this.head;
? ? ? ? while (cur != null) {
? ? ? ? ? ? if (cur.data == key) {
? ? ? ? ? ? ? ? // 頭節(jié)點
? ? ? ? ? ? ? ? if (cur == this.head) {
? ? ? ? ? ? ? ? ? ? this.head = this.head.next;
? ? ? ? ? ? ? ? ? ? this.head.prev = null;
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? cur.prev.next = cur.next;
? ? ? ? ? ? ? ? ? ? // cur.next != null --->不是尾節(jié)點
? ? ? ? ? ? ? ? ? ? if (cur.next != null) {
? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev;
? ? ? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? ? ? this.last = cur.prev;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? cur = cur.next;
? ? ? ? }
? ? }
? ? /**
? ? ?* 7.得到單鏈表的長度
? ? ?* @return
? ? ?*/
? ? @Override
? ? public int getLength() {
? ? ? ? int count = 0;
? ? ? ? Node cur = this.head;
? ? ? ? while (cur != null) {
? ? ? ? ? ? count++;
? ? ? ? ? ? cur = cur.next;
? ? ? ? }
? ? ? ? return count;
? ? }
? ? /**
? ? ?* 8.打印鏈表
? ? ?*/
? ? @Override
? ? public void display() {
? ? ? ? if (this.head == null) {
? ? ? ? ? ? return ;
? ? ? ? }
? ? ? ? Node cur = this.head;
? ? ? ? while (cur != null) {
? ? ? ? ? ? System.out.print(cur.data + " ");
? ? ? ? ? ? cur = cur.next;
? ? ? ? }
? ? ? ? System.out.println();
? ? }
? ? /**
? ? ?* 9.清空順序表以防內(nèi)存泄漏
? ? ?*/
? ? @Override
? ? public void clear() {
? ? ? ? while(this.head != null) {
? ? ? ? ? ? Node cur = this.head.next;
? ? ? ? ? ? this.head.next = null;
? ? ? ? ? ? this.head.prev = null;
? ? ? ? ? ? this.head = cur;
? ? ? ? }
? ? }
}3. 測試
package com.github.doubly;
public class TestDemo {
? ? public static void main(String[] args) {
? ? ? ? DoubleLinked doubleLinked = new DoubleLinked();
? ? ? ? doubleLinked.addFirst(10);
? ? ? ? doubleLinked.addFirst(20);
? ? ? ? doubleLinked.addFirst(30);
? ? ? ? doubleLinked.addFirst(40);
? ? ? ? doubleLinked.addFirst(50);
? ? ? ? doubleLinked.display();
? ? ? ? doubleLinked.addIndex(0,100);
? ? ? ? doubleLinked.addIndex(1,200);
? ? ? ? doubleLinked.addIndex(0,300);
? ? ? ? doubleLinked.addLast(40);
? ? ? ? doubleLinked.addLast(50);
? ? ? ? doubleLinked.display();
? ? ? ? doubleLinked.remove(300);
? ? ? ? doubleLinked.display();
? ? ? ? doubleLinked.removeAllKey(50);
? ? ? ? doubleLinked.display();
? ? }
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
泛談Java中的不可變數(shù)據(jù)結(jié)構(gòu)
開發(fā)人員通常認(rèn)為擁有final引用，或者val在Kotlin或Scala中，足以使對象不可變。這篇博客文章深入研究了不可變引用和不可變數(shù)據(jù)結(jié)構(gòu)，下面小編來和大家一起學(xué)習(xí)它2019-05-05
這篇文章主要詳細(xì)介紹了SpringBoot全局異常捕獲處理實現(xiàn)方案,文章通過代碼示例給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2024-02-02
在Java中,FileWriter類用于將字符寫入文件中,它繼承了Writer類,因此可以使用Writer類中的所有方法,下面我們就來深入探討一下FileWriter類的使用方法吧2023-10-10
這篇文章主要為大家詳細(xì)介紹了Java實現(xiàn)考試系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-09-09
SpringMVC日期類型參數(shù)傳遞實現(xiàn)步驟講解
這篇文章主要介紹了SpringMVC日期類型參數(shù)傳遞實現(xiàn)步驟，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2023-02-02
Java并發(fā)(Runnable+Thread)實現(xiàn)硬盤文件搜索功能
這篇文章主要介紹了Java并發(fā)(Runnable+Thread)實現(xiàn)硬盤文件搜索,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-01-01
這篇文章主要給大家介紹了關(guān)于Spring Boot中使用Redis做緩存的相關(guān)資料，文中介紹的非常詳細(xì)，對大家具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起看看吧。2017-06-06
Java遠(yuǎn)程連接Linux服務(wù)器并執(zhí)行命令及上傳文件功能
這篇文章主要介紹了Java遠(yuǎn)程連接Linux服務(wù)器并執(zhí)行命令及上傳文件功能，本文是小編整理的代碼筆記，非常不錯，具有一定的參考借鑒價值,需要的朋友可以參考下2018-05-05
解決SpringBoot啟動過后不能訪問jsp頁面的問題(超詳細(xì))
這篇文章主要介紹了解決SpringBoot啟動過后不能訪問jsp頁面的問題,文中通過示例代碼介紹的非常詳細(xì)，有需要的朋友可以參考一下，希望對你有所幫助。2020-05-05
這篇文章主要介紹了Java算法之桶排序Bucket?Sort詳解,桶排序（Bucket?Sort）又稱箱排序,是一種比較常用的排序算法,其算法原理是將數(shù)組分到有限數(shù)量的桶里,再對每個桶分別排好序,最后一次將每個桶中排好序的數(shù)輸出,需要的朋友可以參考下2023-10-10