文章目錄
- 一、引子
- 二、雙鏈表
- 1. 概念
- 2. 結構
- 3. 基操的實作
- 三、總結
一、引子
前面已經了解了順序表和單鏈表，而在面試當中這些也是經常被提起的
在繼續接下來的學習前，我們要搞清以下幾個問題：
- 陣列和鏈表的區別
- 順序表和鏈表的區別
- ArrayList 和 LinkedList 的區別
大家發現沒上述問題本質上都是同一個問題：順序表和鏈表的區別
那么怎么回答呢？我們可以從共性開始介紹
-
怎么組織資料的？
- 對于順序表： 底層是一個陣列
- 對于鏈表： 每個資料是由節點組織的（由節點與節點之間的指向組織）
-
增刪查改
- 對于順序表： 不適合插入和洗掉，適合查找和修改
- 對于鏈表： 不適合查找和修改，適合插入和洗掉
-
等等
注意：
- ArrayList 和 LinkedList 這兩個類是 Java 中的集合類，是封裝好的順序表和鏈表
- LinkedList 底層是一個雙向鏈表
既然學了單鏈表，我們也要對雙鏈表進行學習，這肯定也很重要，不然為啥 Java 的 LinkedList 底層是一個雙鏈表呢！
那什么是雙鏈表呢？
二、雙鏈表
1. 概念
在 【資料結構 Java 版】玩轉鏈表（1）單鏈表+鏈表面試題 這章中我們用一圖簡單介紹了雙向鏈表的樣子
與單鏈表不同的是
- 它引入了一個前驅域 prev，解決了單鏈表只能單向訪問的痛點
- 在頭節點 head 的前提下，還可以增加一個尾節點 last，標志尾巴，這樣可以方便尾插法
2. 結構
那么怎么實作一個雙鏈表呢？
首先我們依然要定義一下節點
class NodeD{
public int val;
public NodeD prev;
public NodeD next;
public NodeD(int val){
this.val=val;
}
}
和單鏈表差不多，只是增加了個前驅節點
再對雙鏈表進行定義
public class MyRealLinkedList {
public NodeD head;
public NodeD last;
}
在單鏈表的基礎上多了個尾節點
接下來我們來實作雙向不帶頭非回圈鏈表的一些操作，是我們對其的理解更加深透
3. 基操的實作
-
頭插法
public void addFirst(int data){ NodeD node=new NodeD(data); if(this.head==null){ this.head=node; }else{ node.next=this.head; this.head.prev=node; this.head=node; } } -
尾插法
public void addLast(int data){ NodeD node=new NodeD(data); if(this.head==null){ this.head=node; this.last=node; }else{ this.last.next=node; node.prev=last; this.last=node; } -
任意位置插入，第一個資料節點為0號下標
public void addIndex(int index,int data){ if(index<0 || index >size()){ throw new RuntimeException("index 不合法"); } if(index==0){ addFirst(data); } if (index == size()) { addLast(data); } NodeD node=new NodeD(data); NodeD cur=searchNode(index); node.next=cur; cur.prev.next=node; node.prev=cur.prev; cur.prev=node; } -
搜索下標為 index 的資料節點節點
public NodeD searchNode(int index){ int i=0; NodeD cur=this.head; while(i!=index){ cur=cur.next; i++; } return cur; } -
查找關鍵字 key 是否在單鏈表中
public boolean contains(int key){ if(this.head==null){ return false; } NodeD cur=this.head; while(cur!=null){ if(cur.val==key){ return true; } cur=cur.next; } return false; } -
洗掉第一次出現的關鍵字為 key 的節點
public void remove(int key){ if(this.head==null){ return; } NodeD cur=this.head; while(cur!=null) { if (cur.val == key) { if (cur == this.head) { this.head = this.head.next; if(this.head!=null) { this.head.prev = null; }else{ this.last=null; } }else { cur.prev.next = cur.next; if (cur == this.last) { last = cur.prev; }else { cur.next.prev = cur.prev; } } return; } else { cur = cur.next; } } } -
洗掉所有關鍵字為 key 的節點
public void removeAllKey(int key){ if(this.head==null){ return; } NodeD cur=this.head; while(cur!=null) { if (cur.val == key) { if (cur == this.head) { this.head = this.head.next; if (this.head != null) { this.head.prev = null; } else { this.last = null; } } else { cur.prev.next = cur.next; if (cur == this.last) { last = cur.prev; } else { cur.next.prev = cur.prev; } } } cur = cur.next; } } -
得到雙鏈表的長度
public int size(){ if(this.head==null){ return 0; } NodeD cur=this.head; int count=0; while(cur!=null){ count++; cur=cur.next; } return count; } -
清除雙鏈表
public void clear(){ NodeD cur=this.head; while(cur!=null){ NodeD curNext=cur.next; cur.prev=null; cur.next=null; cur=curNext; } this.head=null; this.last=null; } -
列印雙鏈表
public void display(){ if(this.head==null){ return; } NodeD cur=this.head; while(cur!=null){ System.out.print(cur.val + " "); cur=cur.next; } System.out.println(); }
三、總結
到此為止，鏈表我們已經基本認識了，而接下來我們就是通過刷題和積累，去沉淀自己！希望大家看完這篇文章，可以真正的玩轉鏈表！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298662.html
標籤：其他
上一篇：二叉樹之結點相關操作