文章目錄
目錄
文章目錄
前言
一、什么是雙向鏈表?
雙向鏈表有什么優(yōu)勢?
二、雙向鏈表的設計和實現(xiàn)
1.設計思想
尾增 : 在鏈表的末尾添加新的元素
?頭插 : 在鏈表頭部插入節(jié)點
?刪除 : 根據val的值刪除節(jié)點
?查找 : 根據索引的值查找并返回節(jié)點
總結
前言
大家好,今天給大家講解一下雙向鏈表的設計和實現(xiàn),和單向鏈表不同的是,雙向鏈表中加入了指向前一個節(jié)點的指針。
一、什么是雙向鏈表?
如上圖所示,雙向鏈表中包含了兩個指針,一個指向前驅結點,一個指向后繼節(jié)點,其中頭結點沒有前驅節(jié)點,尾結點沒有后繼節(jié)點
前驅?: 前驅指的是當前節(jié)點的前一個節(jié)點，即在鏈表中位于當前節(jié)點之前的節(jié)點。它可以通過前向指針（previous pointer）來訪問。
后繼?:?后繼指的是當前節(jié)點的后一個節(jié)點，即在鏈表中位于當前節(jié)點之后的節(jié)點。它可以通過后向指針（next pointer）來訪問。
雙向鏈表有什么優(yōu)勢?
相對于單鏈表，雙向鏈表具有以下優(yōu)勢：
-
可以從任意一個節(jié)點開始進行正向或反向遍歷。由于每個節(jié)點都有指向前一個節(jié)點和后一個節(jié)點的指針，因此可以方便地在鏈表中進行前向和后向的遍歷操作。
-
在插入和刪除節(jié)點時，不需要遍歷整個鏈表來找到前一個節(jié)點。在單鏈表中，如果要在某個節(jié)點之后插入或刪除節(jié)點，需要先找到該節(jié)點的前一個節(jié)點，而雙向鏈表可以直接通過指針找到前一個節(jié)點，從而提高了插入和刪除操作的效率。
-
雙向鏈表可以更方便地實現(xiàn)反向查找。在單鏈表中，如果要查找某個節(jié)點的前一個節(jié)點，需要從頭節(jié)點開始遍歷整個鏈表，而雙向鏈表可以通過后向指針直接找到前一個節(jié)點，從而實現(xiàn)了反向查找。
總之，雙向鏈表相對于單鏈表在遍歷、插入和刪除操作上具有更高的效率和靈活性。然而，雙向鏈表的缺點是需要更多的內存空間來存儲額外的指針。
二、雙向鏈表的設計和實現(xiàn)
1.設計思想
前言 : 為了簡單起見,我們在類中只定義最基本的屬性
節(jié)點類: 不管是雙向鏈表還是單向鏈表,都是有節(jié)點所構成,所以說節(jié)點類是必不可少的(值得一提的是,節(jié)點類不一定要定義成外部類,這么一想,好像定義成內部類更加合適,畢竟節(jié)點是鏈表的一部分,大家如果自己實現(xiàn)的話可以使用內部類的方式,由于我寫博客準備的就是外部類的方式,在此就不做修改)
鏈表類: 類中應該需要包含什么信息? 聰明的讀者肯定已經想到了吧,節(jié)點啊! 你們都是聰明人啊,除了節(jié)點之外我們還需要包含一個成員變量Head(鏈表的頭結點),一個構造方法(鏈表寫出來是給別人用的),還有其他的成員方法(自己設計)。
下面給出框架代碼
public class List {
private Node head;// 頭結點
public List() {
}
// 節(jié)點類
class Node {
int val;
Node prev;
Node next;
public Node() {
}
public Node(int val) {
this.val = val;
}
@Override
public String toString() {
return "Node{" +
"no=" + val +
", prev=" + prev +
", next=" + next +
'}';
}
}
2.代碼實現(xiàn)
前言 : 為了簡單起見,我們下面只實現(xiàn)基本方法并且只重點針對性的解析我認為對初學者有難度的代碼部分
和前面的部分代碼相同,有些很簡單的方法直接給出
/*
* 鏈表中元素的個數
* */
public int getSize(){
Node cur = head;
int count = 0;
while(cur != null){
cur = cur.next;
count++;
}
return count;
}
/*
* 判斷鏈表是否為空
* */
public Boolean IsEmpty() {
return head == null;
}
尾增 : 在鏈表的末尾添加新的元素
public void addNode(int val) {
Node node = new Node(val);
if (IsEmpty()) {
// 鏈表為空,該節(jié)點為新頭
head = node;
}
Node cur = head;
while (cur.next != null) {
cur = cur.next;
}
// 此時的cur就表示最后一個節(jié)點
cur.next = node;
node.prev = cur;
}
?頭插 : 在鏈表頭部插入節(jié)點
不知道初學者有沒有感覺到什么難度,個人感覺這些代碼都是很基礎的,所以沒有進行解析
如果有問題的可以在評論區(qū)提出,我再進行修改
public void addFirst(int val){
Node newNode = new Node(val);
if(IsEmpty()){
head = newNode;
}
newNode.next = head;
head.prev = newNode;
head = newNode;
}
?刪除 : 根據val的值刪除節(jié)點
這個和單鏈表比起來就簡單多了,在單鏈表中需要找到值為val的前一個節(jié)點,還需要判斷頭結點為val的情況,大家搞清楚單鏈表中的方法,雙向鏈表中的這個就是弟弟!
// 根據節(jié)點的no值刪除節(jié)點
public void DeleteNode(int no) {
int count = 0;// 記錄被刪除節(jié)點的個數
if(IsEmpty()){
System.out.println("鏈表為空");
return;
}
Node cur = head;// 將head的值賦給變量cur,使其代替head進行循環(huán)遍歷
while(true){
if(cur == null){
System.out.println("共刪除了"+count+"個節(jié)點");
// 鏈表中已經沒有值為no的節(jié)點,跳出循環(huán)
break;
}
if(cur.val == no){
Node prev = cur.prev;// 記錄將要被刪除的節(jié)點的上一個節(jié)點
cur = cur.next;// 用下一個節(jié)點覆蓋當前節(jié)點
cur.prev = prev;
count++;
continue;
}
cur = cur.next;
}
?查找 : 根據索引的值查找并返回節(jié)點
// 根據索引查找節(jié)點
public Node findNode(int index) throws IndexException {
// 索引是否合法,一看到和索引相關的問題就應該要想一下是否需要判斷索引的合法性,此處需要判斷
if(index < 0 || index >= getSize()){
// 自定義異常來表示索引越界這種不合法的行為
throw new IndexException("索引越界");
}
Node cur = head;
while(index > 0){
index--;
cur = cur.next;
}
return cur;
}
?寫到這里不得不感慨一下JAVA中的深情哥-Exception(異常)-上_喜歡吃animal milk的博客-CSDN博客的下篇到現(xiàn)在還沒寫
到這里就結束了,方法在精不在多,自行領悟吧!文章來源：http://www.zghlxwxcb.cn/news/detail-699707.html
總結
這篇博客大家應重點關注鏈表的設計,代碼這個東西面試考的更多的是單鏈表,大家刷題更多的也是單鏈表,雙向鏈表相對于就沒有那么重要了。文章來源地址http://www.zghlxwxcb.cn/news/detail-699707.html
到了這里，關于數據結構 - 雙向鏈表的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
