Java實現(xiàn)無頭雙向鏈表操作
更新時間：2022年01月20日 16:26:37 作者：Sasura_321
這篇文章主要為大家詳細介紹了Java實現(xiàn)無頭雙向鏈表的基本操作，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
本文實例為大家分享了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中final作用于變量、參數(shù)、方法及類該如何處理
Java中的final關(guān)鍵字非常重要,它可以應(yīng)用于類、方法以及變量，下面這篇文章主要給大家介紹了關(guān)于Java中final作用于變量、參數(shù)、方法及類該如何處理的相關(guān)資料，文中通過示例代碼介紹的非常詳細，需要的朋友可以參考下。2017-12-12
這篇文章主要介紹了springboot實現(xiàn)單文件上傳的方法，幫助大家更好的理解和使用springboot框架，感興趣的朋友可以了解下2021-02-02
這篇文章主要介紹了詳解Spring Boot自動裝配的原理，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-09-09
SpringBoot實現(xiàn)devtools實現(xiàn)熱部署過程解析
這篇文章主要介紹了SpringBoot實現(xiàn)devtools實現(xiàn)熱部署過程解析,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-03-03
這篇文章給大家講解的是MyBatis 這門技術(shù)的 CURD （增刪改查） ,非常的詳細與實用,有需要的小伙伴可以參考下2020-02-02
ArrayList和HashMap如何自己實現(xiàn)實例詳解
這篇文章主要介紹了 ArrayList和HashMap如何自己實現(xiàn)的相關(guān)資料,需要的朋友可以參考下2016-12-12
解決tomcat發(fā)布工程后,WEB-INF/classes下文件不編譯的問題
這篇文章主要介紹了解決tomcat發(fā)布工程后,WEB-INF/classes下文件不編譯的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
這篇文章主要介紹了自定義類加載器的父類為何是AppClassLoader說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
Spring Boot Async異步執(zhí)行任務(wù)過程詳解
這篇文章主要介紹了Spring Boot Async異步執(zhí)行任務(wù)過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-08-08
這篇文章主要介紹了Spring boot GC實現(xiàn)過程原理解析,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-08-08