雙向鏈表
雙向鏈表的定義
雙向鏈表也叫雙鏈表，與單向鏈表不同的是，每一個(gè)節(jié)點(diǎn)有三個(gè)區(qū)域組成：兩個(gè)指針域，一個(gè)數(shù)據(jù)域
- 前一個(gè)指針域：存儲(chǔ)前驅(qū)節(jié)點(diǎn)的內(nèi)存地址
- 后一個(gè)指針域：存儲(chǔ)后繼節(jié)點(diǎn)的內(nèi)存地址
- 數(shù)據(jù)域：存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù)
以下就是雙向鏈表的最基本單位
節(jié)點(diǎn)的前指針域指向前驅(qū)，后指針域執(zhí)行后繼
完整的雙向鏈表
雙向鏈表的功能
-
增
-
向雙向鏈表的尾節(jié)點(diǎn)之后添加節(jié)點(diǎn)
-
尾節(jié)點(diǎn)的后指針域存儲(chǔ)新添加節(jié)點(diǎn)的內(nèi)存地址
-
新添加節(jié)點(diǎn)的前指針域存儲(chǔ)尾節(jié)點(diǎn)的內(nèi)存地址
注意：此時(shí)尾節(jié)點(diǎn)就是新添加的這個(gè)節(jié)點(diǎn)
-
-
向雙向鏈表的首元節(jié)點(diǎn)之前添加節(jié)點(diǎn)
-
新添加節(jié)點(diǎn)的后指針域存儲(chǔ)首元節(jié)點(diǎn)的內(nèi)存地址
-
首元節(jié)點(diǎn)的前指針域存儲(chǔ)新添加節(jié)點(diǎn)的內(nèi)存地址
注意：此時(shí)首元節(jié)點(diǎn)就是新添加的這個(gè)節(jié)點(diǎn)
-
-
-
刪
-
刪除中間節(jié)點(diǎn)時(shí)修改改節(jié)點(diǎn)的前驅(qū)和后繼的指針方向即可
注意：被刪除的節(jié)點(diǎn)稱之為：野節(jié)點(diǎn)，這并不是真正意義上的刪除，它在內(nèi)存中依舊存在。那么野節(jié)點(diǎn)的最終歸宿是被JVM的GC（垃圾回收器）所回收，也就是釋放該節(jié)點(diǎn)的內(nèi)存空間，這才是真正意義上的刪除
額外知識(shí)：java中的垃圾回收器（Garbage Collector，GC）負(fù)責(zé)管理內(nèi)存的分配和釋放。當(dāng)一個(gè)對(duì)象沒有任何引用指向它時(shí)，它就變得不可達(dá)，而垃圾回收器會(huì)將其標(biāo)記為垃圾對(duì)象，并在適當(dāng)?shù)臅r(shí)候回收該對(duì)象所占用的內(nèi)存空間。這個(gè)過程稱為垃圾回收。
-
-
改
- 挪動(dòng)指針找到要修改的節(jié)點(diǎn)，之后講修改節(jié)點(diǎn)的數(shù)據(jù)域中的數(shù)據(jù)修改掉
-
查
- 挪動(dòng)指針找到要所要查找的數(shù)據(jù)。
特點(diǎn)
- 雙向性：
- 每個(gè)節(jié)點(diǎn)除了存儲(chǔ)自己的數(shù)據(jù)外，還包含兩個(gè)指針域，分別存儲(chǔ)前驅(qū)和后繼的內(nèi)存地址，因此可以在鏈表中向前或向后遍歷。
- 動(dòng)態(tài)性：
- 雙向鏈表可以在運(yùn)行時(shí)動(dòng)態(tài)地添加、刪除和修改節(jié)點(diǎn)，相對(duì)于數(shù)組等靜態(tài)數(shù)據(jù)結(jié)構(gòu)更加靈活。
- 插入和刪除操作高效：
- 由于雙向鏈表中的節(jié)點(diǎn)包含指向前驅(qū)和后繼的的指針，因此插入和刪除操作只需要調(diào)整節(jié)點(diǎn)前后的指針，而不需要像數(shù)組那樣移動(dòng)大量元素。
- 空間利用率較高：
- 相比單向鏈表，雙向鏈表需要額外的指針來表示前一個(gè)節(jié)點(diǎn)，空間利用率略低一些，但在某些情況下方便了一些操作。
- 雙向遍歷能力：
- 雙向鏈表可以從任意節(jié)點(diǎn)開始向前或向后遍歷，這在某些場(chǎng)景中非常有用，例如需要反向迭代鏈表。
雙向鏈表在內(nèi)存開銷上相對(duì)于單向鏈表稍高。
由于有兩個(gè)指針，插入和刪除操作涉及到更多的指針修改，相對(duì)于單向鏈表略微復(fù)雜。
單向鏈表和雙向鏈表的區(qū)別
單向鏈表相對(duì)于雙向鏈表更簡(jiǎn)單且節(jié)省內(nèi)存，適用于對(duì)內(nèi)存占用敏感且只需要單向遍歷的情況。
而雙向鏈表由于具有雙向遍歷的能力，適用于需要頻繁插入、刪除和反向遍歷的場(chǎng)景。文章來源：http://www.zghlxwxcb.cn/news/detail-767431.html
在選擇使用哪種鏈表結(jié)構(gòu)時(shí)，應(yīng)根據(jù)具體需求權(quán)衡其優(yōu)缺點(diǎn)。文章來源地址http://www.zghlxwxcb.cn/news/detail-767431.html
MyList
public interface MyList<E> {
//添加節(jié)點(diǎn)數(shù)據(jù)
void add(E element);
//獲取節(jié)點(diǎn)數(shù)據(jù)
E get (int index);
//獲取鏈表長(zhǎng)度
int size();
//根據(jù)指針移除節(jié)點(diǎn)
E remove(int index);
//從頭添加元素
void addFirst(E element);
//從尾添加元素
void addLast(E element);
}
MyDoubleLinkedList
public class MyDoubleLinkedList<E> implements MyList<E> {
private int size;//記錄元素的個(gè)數(shù)
private Node head ;// 記錄頭節(jié)點(diǎn)
private Node tail;//記錄尾節(jié)點(diǎn)
/**
* 向雙向鏈表中添加元素?cái)?shù)據(jù)
* @param element
*/
@Override
public void add(E element) {
this.linkLast(element);
}
/**
* 將節(jié)點(diǎn)對(duì)象添加到雙向鏈表的尾部
* @param element
*/
private void linkLast(E element){
//獲取尾節(jié)點(diǎn)
Node t = this.tail;
Node<E> node = new Node<>(t,element,null);
//將新節(jié)點(diǎn)定義為尾節(jié)點(diǎn)
this.tail = node;
if (t == null){//當(dāng)t等于空的時(shí)候說明這個(gè)鏈表是個(gè)空鏈表
this.head=node;//將向的元素?cái)?shù)據(jù)賦值到頭節(jié)點(diǎn)
}else{
t.next=node;//否則將新元素賦值到尾節(jié)點(diǎn)之后
}
this.size++;//添加成功長(zhǎng)度自增加一
}
/**
* 根據(jù)指針獲取對(duì)應(yīng)的元素?cái)?shù)據(jù)
* @param index
* @return
*/
@Override
public E get(int index) {
//對(duì)index做合法性校驗(yàn)
this.rangeCheck(index);
Node<E> node = this.getNode(index);
return node.item;
}
/**
* 判斷當(dāng)前index的合法性
*/
private void rangeCheck(int index){
if(!(index >=0 && index < this.size)){
int a = this.size-1;
throw new IndexOutOfBoundsException("您輸入的索引為："+index+"它的指針長(zhǎng)度為："+a);
}
}
/**
* 根據(jù)位置獲取指定的節(jié)點(diǎn)對(duì)象
* @param index
* @return
*/
private Node getNode(int index){
//判斷當(dāng)前輸入的指針距離頭或者尾哪個(gè)節(jié)點(diǎn)近
//如果輸入的指針大，從尾部開始找，
//如果輸入的指針小，從頭部開始找
if (index < (this.size >> 1)){
Node node = this.head;
//遍歷指針
for(int i =0; i < index;i++){
//拿到指針處的下一個(gè)節(jié)點(diǎn)對(duì)象賦值node
node=node.next;
}
return node;
}else {
Node node = this.tail;
//從尾節(jié)點(diǎn)找指針
for (int i = this.size-1; i>index; i--){
node = node.prev;
}
return node;
}
}
/**
* 獲取元素的長(zhǎng)度（個(gè)數(shù)）
* @return
*/
@Override
public int size() {
return this.size;
}
/**
* 根據(jù)指定指針刪除元素
* @param index
* @return
*/
@Override
public E remove(int index) {
//對(duì)index指針進(jìn)行合法性校驗(yàn)
this.rangeCheck(index);
//根據(jù)index進(jìn)行獲取節(jié)點(diǎn)對(duì)象，判斷從頭刪還是從尾部刪除
Node<E> node = this.getNode(index);
//獲取index指針處的節(jié)點(diǎn)元素?cái)?shù)據(jù)
E item = node.item;
//判斷當(dāng)前節(jié)點(diǎn)是否尾頭節(jié)點(diǎn)
if (node.prev == null){
this.head = node.next;
}else {
//完成當(dāng)前節(jié)點(diǎn)的直接前驅(qū)節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)，掛接
node.prev.next = node.next;
}
//當(dāng)前節(jié)點(diǎn)斷掉與它直接前驅(qū)點(diǎn)的連接
node.prev = null;
//當(dāng)前節(jié)點(diǎn)斷掉與他直接后繼節(jié)點(diǎn)的連接
node.next =null;
node.item =null;
//長(zhǎng)度自減一
this.size--;
//返回被刪除的節(jié)點(diǎn)元素?cái)?shù)據(jù)
return item;
}
//從頭開始添加元素
@Override
public void addFirst(E element) {
this.linkFirst(element);
}
//從尾部添加元素
@Override
public void addLast(E element) {
this.linkLast(element);
}
//在鏈表的頭添加元素
private void linkFirst(E element){
//獲取頭節(jié)點(diǎn)對(duì)象
Node head = this.head;
Node node = new Node(null,element,head);
//將新節(jié)點(diǎn)定義為頭節(jié)點(diǎn)
this.head = node;
//判斷當(dāng)前鏈表中是否有節(jié)點(diǎn)，如果沒有該節(jié)則是頭節(jié)點(diǎn)也是尾節(jié)點(diǎn)
if(this.head == null){
this.tail = node;
}else {
this.head.prev = node;
}
this.size++;//記錄鏈表長(zhǎng)度
}
/**
* 創(chuàng)建節(jié)點(diǎn)類
* @param <E>
*/
class Node<E> {
private E item;//記錄元素
private Node<E> next; // 下一個(gè)節(jié)點(diǎn)對(duì)象
private Node<E> prev; // 上一個(gè)節(jié)點(diǎn)對(duì)象
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
測(cè)試
public class MyLinkedMain {
public static void main(String[] args) {
MyDoubleLinkedList linkedList = new MyDoubleLinkedList();
linkedList.add(12);
linkedList.add(13);
linkedList.add(14);
linkedList.add(15);
linkedList.add(16);
System.out.println(linkedList.get(3));//3是指針，從尾部開始找
System.out.println(linkedList.get(4));//4是指針，從尾部開始找
System.out.println(linkedList.get(1));//1是指針，從頭部開始找
System.out.println(linkedList.size());//獲取linkedList長(zhǎng)度
System.out.println("刪除前的指針1處的數(shù)據(jù)"+linkedList.get(1));
System.out.println(linkedList.remove(1));
System.out.println("刪除后的指針1處的數(shù)據(jù)"+linkedList.get(1));
System.out.println("刪除前的指針0處的數(shù)據(jù)"+linkedList.get(4));
System.out.println(linkedList.remove(4));
try {
System.out.println("刪除后的指針0處的數(shù)據(jù)"+linkedList.get(4));
}catch (Exception e) {
e.printStackTrace();
}finally {
System.out.println("刪除后的鏈表長(zhǎng)度"+linkedList.size());//獲取linkedList長(zhǎng)度
}
}
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-鏈表結(jié)構(gòu)-雙向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
