Java雙向鍊錶的增刪改查怎麼實現
一、認識雙向鍊錶
單向鍊錶不僅保存了目前的結點值，還保存了下一個結點的位址
定義一個雙向鍊錶的結點類：
結點中既要保存目前節點的值，還要保存此節點的前驅節點的位址和此節點的後繼節點的位址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;
}
程式碼如下：
/**
* 头插
*/
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的位置插入值為val的節點：
插入還是要找前驅節點，但雙向鍊錶找前驅節點比單向鍊錶找前驅節點要靈活很多，單向鍊錶只能從頭走到尾，假如此時有100個節點，要在索引為98的位置插入節點，那麼雙向鍊錶就可以從尾結點開始找，會方便很多#如何判斷從前向後找，還是從後向前找？
- 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;
}
/**
* 修改双向链表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;
}
/**
* 查询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;
}
刪除index位置的節點
#程式碼如下：//删除链表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--;
}
呼叫刪除任意位置的節點即可
程式碼如下：//头删
public void removeFirst(){
removeIndex(0);
}
呼叫刪除任意位置的節點即可
程式碼如下：//尾删
public void removeLast(){
removeIndex(size - 1);
}
//删除第一个值为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的结点
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--;
}
以上是Java雙向鍊錶的增刪改查怎麼實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
Video Face Swap
使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！
熱門文章
熱工具
記事本++7.3.1
好用且免費的程式碼編輯器
SublimeText3漢化版
中文版，非常好用
禪工作室 13.0.1
強大的PHP整合開發環境
Dreamweaver CS6
視覺化網頁開發工具
SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)
突破或從Java 8流返回？
Feb 07, 2025 pm 12:09 PM
Java 8引入了Stream API，提供了一種強大且表達力豐富的處理數據集合的方式。然而，使用Stream時，一個常見問題是：如何從forEach操作中中斷或返回？ 傳統循環允許提前中斷或返回，但Stream的forEach方法並不直接支持這種方式。本文將解釋原因，並探討在Stream處理系統中實現提前終止的替代方法。 延伸閱讀： Java Stream API改進 理解Stream forEach forEach方法是一個終端操作，它對Stream中的每個元素執行一個操作。它的設計意圖是處
PHP：網絡開發的關鍵語言
Apr 13, 2025 am 12:08 AM
PHP是一種廣泛應用於服務器端的腳本語言，特別適合web開發。 1.PHP可以嵌入HTML，處理HTTP請求和響應，支持多種數據庫。 2.PHP用於生成動態網頁內容，處理表單數據，訪問數據庫等，具有強大的社區支持和開源資源。 3.PHP是解釋型語言，執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時，可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7
PHP與Python：了解差異
Apr 11, 2025 am 12:15 AM
PHP和Python各有優勢，選擇應基於項目需求。 1.PHP適合web開發，語法簡單，執行效率高。 2.Python適用於數據科學和機器學習，語法簡潔，庫豐富。
PHP與其他語言：比較
Apr 13, 2025 am 12:19 AM
PHP適合web開發，特別是在快速開發和處理動態內容方面表現出色，但不擅長數據科學和企業級應用。與Python相比，PHP在web開發中更具優勢，但在數據科學領域不如Python；與Java相比，PHP在企業級應用中表現較差，但在web開發中更靈活；與JavaScript相比，PHP在後端開發中更簡潔，但在前端開發中不如JavaScript。
Java程序查找膠囊的體積
Feb 07, 2025 am 11:37 AM
膠囊是一種三維幾何圖形，由一個圓柱體和兩端各一個半球體組成。膠囊的體積可以通過將圓柱體的體積和兩端半球體的體積相加來計算。本教程將討論如何使用不同的方法在Java中計算給定膠囊的體積。 膠囊體積公式 膠囊體積的公式如下： 膠囊體積 = 圓柱體體積 兩個半球體體積 其中， r: 半球體的半徑。 h: 圓柱體的高度（不包括半球體）。 例子 1 輸入 半徑 = 5 單位 高度 = 10 單位 輸出 體積 = 1570.8 立方單位 解釋 使用公式計算體積： 體積 = π × r2 × h (4
PHP與Python：核心功能
Apr 13, 2025 am 12:16 AM
PHP和Python各有優勢，適合不同場景。 1.PHP適用於web開發，提供內置web服務器和豐富函數庫。 2.Python適合數據科學和機器學習，語法簡潔且有強大標準庫。選擇時應根據項目需求決定。
創造未來：零基礎的 Java 編程
Oct 13, 2024 pm 01:32 PM
Java是熱門程式語言，適合初學者和經驗豐富的開發者學習。本教學從基礎概念出發，逐步深入解說進階主題。安裝Java開發工具包後，可透過建立簡單的「Hello,World!」程式來實踐程式設計。理解程式碼後，使用命令提示字元編譯並執行程序，控制台上將輸出「Hello,World!」。學習Java開啟了程式設計之旅，隨著掌握程度加深，可創建更複雜的應用程式。
PHP：許多網站的基礎
Apr 13, 2025 am 12:07 AM
PHP成為許多網站首選技術棧的原因包括其易用性、強大社區支持和廣泛應用。 1)易於學習和使用，適合初學者。 2)擁有龐大的開發者社區，資源豐富。 3)廣泛應用於WordPress、Drupal等平台。 4)與Web服務器緊密集成，簡化開發部署。
