Java實(shí)現(xiàn)雙鏈表的示例代碼
更新時(shí)間：2022年09月26日 09:10:37 作者：熬夜磕代碼丶
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。本文將用Java語(yǔ)言實(shí)現(xiàn)雙鏈表，需要的可以參考一下
一、雙向鏈表是什么
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以很方便地訪(fǎng)問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。
LinkedList底層就是一個(gè)雙向鏈表，我們來(lái)實(shí)現(xiàn)一個(gè)雙向鏈表。
這里多一個(gè)尾指針，方便我們對(duì)尾插操作從O(n)降到O(1).每個(gè)結(jié)點(diǎn)多了前驅(qū)結(jié)點(diǎn)，方便我們對(duì)鏈表進(jìn)行操作。
二、具體方法實(shí)現(xiàn)
定義結(jié)點(diǎn)
class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
下標(biāo)訪(fǎng)問(wèn)異常
public class IndexWrongException extends RuntimeException{
public IndexWrongException() {
}
public IndexWrongException(String message) {
super(message);
}
}
獲取鏈表長(zhǎng)度
class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
打印鏈表
class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
清空鏈表
public void clear(){
if(this.head == null) {
return;
}
ListNode cur = this.head;
while(cur != null) {
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
head = null;
tail = null;
}
頭插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
node.next = this.head;
this.head.prev = node;
this.head = node;
}
尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
tail.next = node;
node.prev = tail;
tail = node;
}
指定位置插入
public void addIndex(int index,int data) throws IndexWrongException{
if(index < 0 || index > size()) {
throw new IndexWrongException("輸入下標(biāo)不合法");
}
ListNode node = new ListNode(data);
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}查找元素
public boolean contains(int key){
if(head == null) {
return false;
}
ListNode cur = this.head;
while(cur != null) {
if(cur.value == key) {
return true;
}
cur = cur.next;
}
return false;
}
刪除第一次出現(xiàn)的關(guān)鍵字
public void remove(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
return;
}
cur = cur.next;
}
}刪除所有值為key的節(jié)點(diǎn)
public void removeAllKey(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
}
cur = cur.next;
}
}三、完整代碼
public class LinkedList {
static class ListNode {
int value;
ListNode next;
ListNode prev;
public ListNode(int value) {
this.value = value;
}
}
ListNode head;
ListNode tail;
//頭插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
node.next = this.head;
this.head.prev = node;
this.head = node;
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
this.head = node;
this.tail = node;
return;
}
tail.next = node;
node.prev = tail;
tail = node;
}
//任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)
public void addIndex(int index,int data) throws IndexWrongException{
if(index < 0 || index > size()) {
throw new IndexWrongException("輸入下標(biāo)不合法");
}
ListNode node = new ListNode(data);
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
//查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中
public boolean contains(int key){
if(head == null) {
return false;
}
ListNode cur = this.head;
while(cur != null) {
if(cur.value == key) {
return true;
}
cur = cur.next;
}
return false;
}
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
public void remove(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
return;
}
cur = cur.next;
}
}
//刪除所有值為key的節(jié)點(diǎn)
public void removeAllKey(int key){
ListNode cur = head;
while(cur != head) {
if(cur.value == key) {
if(cur == head) {
head = head.next;
if(head.next != null) {
head.prev = null;
}else {
tail = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next != null) {
cur.next.prev = cur.prev;
}else {
tail = cur.prev;
tail.next = null;
}
}
}
cur = cur.next;
}
}
//得到單鏈表的長(zhǎng)度
public int size(){
ListNode cur = head;
int count = 0;
while(cur != null) {
cur = cur.next;
count++;
}
return count;
}
public void display(){
ListNode cur = head;
while (cur != null) {
System.out.print(cur.value+" ");
cur = cur.next;
}
System.out.println();
}
public void clear(){
if(this.head == null) {
return;
}
ListNode cur = this.head;
while(cur != null) {
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
head = null;
tail = null;
}
}
到此這篇關(guān)于Java實(shí)現(xiàn)雙鏈表的示例代碼的文章就介紹到這了,更多相關(guān)Java雙鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java中的LinkedHashMap及LRU緩存機(jī)制詳解
這篇文章主要介紹了Java中的LinkedHashMap及LRU緩存機(jī)制詳解,LinkedHashMap繼承自HashMap,它的多種操作都是建立在HashMap操作的基礎(chǔ)上的,同HashMap不同的是,LinkedHashMap維護(hù)了一個(gè)Entry的雙向鏈表,保證了插入的Entry中的順序,需要的朋友可以參考下2023-09-09
Java隊(duì)列數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)
這篇文章主要介紹了Java隊(duì)列數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn),隊(duì)列是一種特殊的線(xiàn)性表,只允許在表的隊(duì)頭進(jìn)行刪除操作，在表的后端進(jìn)行插入操作，隊(duì)列是一個(gè)有序表先進(jìn)先出，想了解更多相關(guān)資料的小伙伴可以參考下面文章的詳細(xì)內(nèi)容2021-12-12
Java8中使用流方式查詢(xún)數(shù)據(jù)庫(kù)的方法
這篇文章主要介紹了Java8中使用流方式查詢(xún)數(shù)據(jù)庫(kù)的相關(guān)資料,需要的朋友可以參考下2016-01-01
java如何用Processing生成馬賽克風(fēng)格的圖像
這篇文章主要介紹了如何用java如何用Processing生成馬賽克風(fēng)格的圖像,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
這篇文章主要介紹了java中的移動(dòng)位運(yùn)算：,>>>文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
詳解JAVA中implement和extends的區(qū)別
這篇文章主要介紹了詳解JAVA中implement和extends的區(qū)別的相關(guān)資料,extends是繼承接口，implement是一個(gè)類(lèi)實(shí)現(xiàn)一個(gè)接口的關(guān)鍵字，需要的朋友可以參考下2017-08-08
java自帶的MessageDigest實(shí)現(xiàn)文本的md5加密算法
這篇文章主要介紹了java自帶的MessageDigest實(shí)現(xiàn)文本的md5加密算法,需要的朋友可以參考下2015-12-12
在多線(xiàn)程環(huán)境下，程序往往會(huì)出現(xiàn)一些線(xiàn)程安全問(wèn)題，為此，Java提供了一些線(xiàn)程的同步機(jī)制來(lái)解決安全問(wèn)題，比如：synchronized鎖和Lock鎖都能解決線(xiàn)程安全問(wèn)題。下面小編就來(lái)詳細(xì)介紹該知識(shí)點(diǎn),需要的朋友可以參考一下2021-09-09
IDEA運(yùn)行Tomcat中文亂碼出現(xiàn)的各種問(wèn)題
這篇文章主要介紹了IDEA運(yùn)行Tomcat中文亂碼的各種問(wèn)題及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-11-11
我們那時(shí)候上機(jī)經(jīng)常玩掃雷,試想如果我當(dāng)年可以用 java 寫(xiě)個(gè)掃雷出來(lái),那場(chǎng)面不用我多說(shuō)了吧,大家讓開(kāi),我要開(kāi)始裝逼了,之前用JavaScript寫(xiě)過(guò)了一個(gè)掃雷,這次我用java再寫(xiě)了一遍,權(quán)當(dāng)是復(fù)習(xí)咯.文中有非常詳細(xì)的代碼示例,需要的朋友可以參考下2021-05-05