Java雙向鏈表的操作
更新時間：2022年06月22日 16:16:31 作者：蘿詩粉
這篇文章主要介紹了Java雙向鏈表的操作，雙向鏈表，對于該鏈表中的任意節(jié)點，既可以通過該節(jié)點向前遍歷，也可以通過該節(jié)點向后遍歷，雙向鏈表在實際工程中應用非常廣泛，是使用鏈表這個結構的首選
前言
我們之前學的單鏈表，默認只能從鏈表的頭部遍歷到鏈表的尾部，在實際中應用太少見，太局限；而雙向鏈表，對于該鏈表中的任意節(jié)點，既可以通過該節(jié)點向前遍歷，也可以通過該節(jié)點向后遍歷，雙向鏈表在實際工程中應用非常廣泛，是使用鏈表這個結構的首選。
一、認識雙向鏈表
單向鏈表不僅保存了當前的結點值，還保存了下一個結點的地址
雙向鏈表不僅保存了當前節(jié)點的值，還保存了上一個結點的地址和下一個結點的地址
定義一個雙向鏈表的結點類：
結點中既要保存當前節(jié)點的值，還要保存此節(jié)點的前驅節(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;
}
}定義一個雙向鏈表類：
既可以從前向后，也可以從后向前，所以在這個類中，即保存一下頭結點，也保存一下尾結點的值
public class DoubleLinkedList {
private int size;
private DoubleNode head;
private DoubleNode tail;
}二、雙向鏈表的增刪改查
1.插入
頭插
在當前鏈表的頭部插入一個節(jié)點，讓當前鏈表的頭結點head前驅指向要插入的節(jié)點node，然后讓node的后繼指向head，然后讓head = node，讓node成為鏈表的頭結點
代碼如下：
/**
* 頭插
*/
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é)點：
插入還是要找前驅節(jié)點，但雙向鏈表找前驅節(jié)點比單向鏈表找前驅節(jié)點要靈活很多，單向鏈表只能從頭走到尾，假如此時有100個節(jié)點，要在索引為98的位置插入節(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++;
}
/**
* 根據索引值找到對應的結點
* @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位置的結點值為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位置的結點值
*/
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位置的結點
public void removeIndex(int index){
if (index < 0 || index > size - 1){
System.err.println("remove index illegal");
return;
}
DoubleNode cur = node(index);
unlink(cur);
}
/**
* 刪除當前雙向鏈表的node結點
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先處理node的前半部分
if (prev == null){
head = successor;
}else{
//前驅不為空的情況
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}頭刪
調用刪除任意位置的節(jié)點即可
代碼如下：
//頭刪
public void removeFirst(){
removeIndex(0);
}尾刪
調用刪除任意位置的節(jié)點即可
代碼如下：
//尾刪
public void removeLast(){
removeIndex(size - 1);
}刪除第一個值為val的節(jié)點
代碼如下：
//刪除第一個值為val的結點
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;
}
}
}
/**
* 刪除當前雙向鏈表的node結點
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先處理node的前半部分
if (prev == null){
head = successor;
}else{
//前驅不為空的情況
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}刪除所有值為val的值
代碼如下：
//刪除鏈表中所有值為val的結點
public void removeAllVal(int val){
for (DoubleNode x = head;x != null;){
if (x.val == val){
//暫存一下x的下一個結點
DoubleNode next = x.next;
unlink(x);
x = next;
}else{
//val不是待刪除的元素
x = x.next;
}
}
}
/**
* 刪除當前雙向鏈表的node結點
* 分治法
* @param node
*/
private void unlink (DoubleNode node){
DoubleNode prev = node.prev;
DoubleNode successor = node.next;
//1.先處理node的前半部分
if (prev == null){
head = successor;
}else{
//前驅不為空的情況
prev.next = successor;
node.prev = null;
}
if (successor == null){
tail = prev;
}else{
successor.prev = prev;
node.next = null;
}
size--;
}總結
本篇博客帶大家了解了一下什么是雙向鏈表，和單鏈表有什么區(qū)別，已經雙向鏈表的一些基本的增刪改查的操作，
到此這篇關于Java雙向鏈表的操作的文章就介紹到這了,更多相關Java雙向鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
在Java編程中,避免數(shù)組越界是十分重要的,本文介紹了兩種常見的判斷數(shù)組是否越界的方法：一是通過數(shù)組的length屬性來判斷索引是否合法；二是通過捕獲ArrayIndexOutOfBoundsException異常來處理越界問題,感興趣的朋友跟隨小編一起看看吧2024-09-09
Java代碼性能測試實戰(zhàn)之ContiPerf安裝使用
這篇文章主要為大家介紹了Java代碼性能測試實戰(zhàn)之ContiPerf安裝使用，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-06-06
Spring中@Autowired與@Resource的區(qū)別詳析
@Autowired與@Resource都可以用來裝配bean,都可以寫在字段上,或寫在setter方法上,下面這篇文章主要給大家介紹了關于Spring中@Autowired與@Resource區(qū)別的相關資料,需要的朋友可以參考下2021-10-10
Java抓包工具fiddler實現(xiàn)請求轉發(fā)
Fiddler是一個http協(xié)議調試代理工具，本文主要介紹了Java抓包工具fiddler實現(xiàn)請求轉發(fā)，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-04-04
這篇文章主要介紹了SpringBoot全局異常處理機制和配置攔截器方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12
這篇文章主要介紹了spring如何通過FactoryBean配置Bean,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-01-01
這篇文章主要介紹了SpringBoot項目@Async方法問題解決方案,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-04-04
這篇文章主要介紹了解決maven加載依賴時遇到的問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-12-12
HttpMessageConverter報文信息轉換器的深入講解
在Spring中內置了大量的HttpMessageConverter,通過請求頭信息中的MIME類型,選擇相應的HttpMessageConverter,這篇文章主要給大家介紹了關于HttpMessageConverter報文信息轉換器的相關資料,需要的朋友可以參考下2022-01-01
今天小編就為大家分享一篇關于利用枚舉法求直方圖中最大矩形面積的方法實例，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-02-02