Java雙向鏈表的操作
更新時間：2022年06月22日 16:16:31 作者：蘿詩粉
這篇文章主要介紹了Java雙向鏈表的操作，雙向鏈表，對于該鏈表中的任意節(jié)點，既可以通過該節(jié)點向前遍歷，也可以通過該節(jié)點向后遍歷，雙向鏈表在實際工程中應(yīng)用非常廣泛，是使用鏈表這個結(jié)構(gòu)的首選
前言
我們之前學(xué)的單鏈表，默認(rèn)只能從鏈表的頭部遍歷到鏈表的尾部，在實際中應(yīng)用太少見，太局限；而雙向鏈表，對于該鏈表中的任意節(jié)點，既可以通過該節(jié)點向前遍歷，也可以通過該節(jié)點向后遍歷，雙向鏈表在實際工程中應(yīng)用非常廣泛，是使用鏈表這個結(jié)構(gòu)的首選。
一、認(rèn)識雙向鏈表
單向鏈表不僅保存了當(dāng)前的結(jié)點值，還保存了下一個結(jié)點的地址
雙向鏈表不僅保存了當(dāng)前節(jié)點的值，還保存了上一個結(jié)點的地址和下一個結(jié)點的地址
定義一個雙向鏈表的結(jié)點類：
結(jié)點中既要保存當(dāng)前節(jié)點的值，還要保存此節(jié)點的前驅(qū)節(jié)點的地址和此節(jié)點的后繼節(jié)點的地址
class DoubleNode{
public DoubleNode next;
DoubleNode prev;
int val;
DoubleNode tail;
public DoubleNode() {}
public DoubleNode(int val) {
this.val = val;
}
public DoubleNode(DoubleNode prev, int val, DoubleNode tail) {
this.prev = prev;
this.val = val;
this.tail = tail;
}
}定義一個雙向鏈表類：
既可以從前向后，也可以從后向前，所以在這個類中，即保存一下頭結(jié)點，也保存一下尾結(jié)點的值
public class DoubleLinkedList {
private int size;
private DoubleNode head;
private DoubleNode tail;
}二、雙向鏈表的增刪改查
1.插入
頭插
在當(dāng)前鏈表的頭部插入一個節(jié)點，讓當(dāng)前鏈表的頭結(jié)點head前驅(qū)指向要插入的節(jié)點node，然后讓node的后繼指向head，然后讓head = node，讓node成為鏈表的頭結(jié)點
代碼如下：
/**
* 頭插
*/
public void addFirst(int val){
DoubleNode node = new DoubleNode(val);
if (head == null){
head = tail = node;
}else{
node.next = head;
head.prev = node;
head = node;
}
size++;
}尾插
和頭插一樣，只不過在鏈表的尾部插入
代碼如下：
public void addLast(int val){
DoubleNode node = new DoubleNode(val);
if (head == null){
head = tail =node;
}else{
tail.next = node;
node.prev = tail;
tail = node;
}
size++;
}在index位置插入
在索引為index的位置插入值為val的節(jié)點：
插入還是要找前驅(qū)節(jié)點，但雙向鏈表找前驅(qū)節(jié)點比單向鏈表找前驅(qū)節(jié)點要靈活很多，單向鏈表只能從頭走到尾，假如此時有100個節(jié)點，要在索引為98的位置插入節(jié)點，那么雙向鏈表就可以從尾結(jié)點開始找，會方便很多
如何判斷從前向后找，還是從后向前找？
- 1.index < size / 2 – >從前向后找，插入位置在前半部分
- 2.index > size / 2 – >從后向前找，插入位置在后半部分
代碼如下：
/**
* 在index位置插入
* @param index
* @param val
*/
public void add(int index,int val){
DoubleNode cur = new DoubleNode(val);
if (index < 0 || index > size){
System.err.println("add index illegal");
return;
}else{
if (index == 0){addFirst(val);}
else if (index == size){addLast(val);}
else{
DoubleNode prev = node(index-1);
DoubleNode next = prev.next;
cur.next = next;
next.prev = cur;
prev.next = cur;
cur.prev = prev;
}
}
size++;
}
/**
* 根據(jù)索引值找到對應(yīng)的結(jié)點
* @param index
* @return
*/
private DoubleNode node(int index){
DoubleNode x = null;
if (index < size/2){
x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
}else{
x = tail;
for (int i = size - 1; i > index ; i--) {
x = x.prev;
}
}
return x;
}2.修改
代碼如下：
/**
* 修改雙向鏈表index位置的結(jié)點值為newVal
*/
public int set(int index,int newVal){
DoubleNode dummyHead = new DoubleNode();
dummyHead.next = head;
DoubleNode prev = dummyHead;
DoubleNode cur = prev.next;
if (index < 0 || index > size - 1){
System.err.println("set index illegal");
}else{
for (int i = 0; i < index; i++) {
prev = prev.next;
cur = cur.next;
}
}
int oldVal = cur.val;
cur.val = newVal;
return oldVal;
}3.查詢
代碼如下：
/**
* 查詢index位置的結(jié)點值
*/
public int get(int index){
DoubleNode dummyHead = new DoubleNode();
dummyHead.next = head;
DoubleNode prev = dummyHead;
DoubleNode cur = prev.next;
if (index < 0 || index > size - 1){
System.err.println("get index illegal");
}else{
for (int i = 0; i < index; i++) {
prev = prev.next;
cur = cur.next;
}
}
return cur.val;
}4.刪除
刪除index位置的節(jié)點
代碼如下：
//刪除鏈表index位置的結(jié)點
public void removeIndex(int index){
if (index < 0 || index > size - 1){
System.err.println("remove index illegal");
return;
}
DoubleNode cur = node(index);
unlink(cur);
}
/**
* 刪除當(dāng)前雙向鏈表的node結(jié)點
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先處理node的前半部分
if (prev == null){
head = successor;
}else{
//前驅(qū)不為空的情況
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}頭刪
調(diào)用刪除任意位置的節(jié)點即可
代碼如下：
//頭刪
public void removeFirst(){
removeIndex(0);
}尾刪
調(diào)用刪除任意位置的節(jié)點即可
代碼如下：
//尾刪
public void removeLast(){
removeIndex(size - 1);
}刪除第一個值為val的節(jié)點
代碼如下：
//刪除第一個值為val的結(jié)點
public void removeValOnce(int val){
if (head == null){
return;
}
for (DoubleNode x = head;x != null;x = x.next){
if (x.val == val){
unlink(x);
break;
}
}
}
/**
* 刪除當(dāng)前雙向鏈表的node結(jié)點
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先處理node的前半部分
if (prev == null){
head = successor;
}else{
//前驅(qū)不為空的情況
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}刪除所有值為val的值
代碼如下：
//刪除鏈表中所有值為val的結(jié)點
public void removeAllVal(int val){
for (DoubleNode x = head;x != null;){
if (x.val == val){
//暫存一下x的下一個結(jié)點
DoubleNode next = x.next;
unlink(x);
x = next;
}else{
//val不是待刪除的元素
x = x.next;
}
}
}
/**
* 刪除當(dāng)前雙向鏈表的node結(jié)點
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先處理node的前半部分
if (prev == null){
head = successor;
}else{
//前驅(qū)不為空的情況
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}總結(jié)
本篇博客帶大家了解了一下什么是雙向鏈表，和單鏈表有什么區(qū)別，已經(jīng)雙向鏈表的一些基本的增刪改查的操作，
到此這篇關(guān)于Java雙向鏈表的操作的文章就介紹到這了,更多相關(guān)Java雙向鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
java兩個數(shù)組合并為一個數(shù)組的幾種方法
這篇文章主要給大家介紹了關(guān)于java兩個數(shù)組合并為一個數(shù)組的幾種方法,最近在寫代碼時遇到了需要合并兩個數(shù)組的需求,文中將每種方法都介紹的非常詳細(xì),需要的朋友可以參考下2023-07-07
Java8以前Java處理日期、日歷和時間的方式一直為社區(qū)所詬病,將 java.util.Date設(shè)定為可變類型,以及SimpleDateFormat的非線程安全使其應(yīng)用非常受限,下面這篇文章主要給大家介紹了關(guān)于Java8中時間處理的相關(guān)資料,需要的朋友可以參考下2022-01-01
這篇文章主要介紹了java實現(xiàn)日期拆分的方法,基于java日期類實現(xiàn)對日期字符串的拆分功能,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
淺談SpringBoot集成Redis實現(xiàn)緩存處理(Spring AOP實現(xiàn))
這篇文章主要介紹了淺談SpringBoot集成Redis實現(xiàn)緩存處理(Spring AOP實現(xiàn))，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-12-12
Java把異常當(dāng)作對象來處理，并定義一個基類java.lang.Throwable作為所有異常的超類，下面通過本文給大家分享JAVA異常體系結(jié)構(gòu)，感興趣的朋友一起看看吧2017-11-11
解決Java?API不能遠(yuǎn)程訪問HBase的問題
這篇文章主要介紹了解決Java?API不能遠(yuǎn)程訪問HBase的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
有時候我們在導(dǎo)入程序之后,系統(tǒng)會給出錯誤提示:Java:程序包xxxx不存在,本文主要介紹了Java程序包不存在的三種解決方法,具有一定的參考價值,感興趣的可以了解一下2024-02-02
SpringBoot?ApplicationContext接口深入分析
ApplicationContext是Spring應(yīng)用程序中的中央接口，由于繼承了多個組件，使得ApplicationContext擁有了許多Spring的核心功能，如獲取bean組件，注冊監(jiān)聽事件，加載資源文件等2022-11-11
本文詳細(xì)講解了ThreadLocal原理介紹及應(yīng)用場景，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12
Java多線程編程之CountDownLatch同步工具使用實例
這篇文章主要介紹了Java多線程編程之CountDownLatch同步工具使用實例,需要的朋友可以參考下2015-05-05