目錄
一、雙向不循環(huán)鏈表的概念
二、鏈表的接口
三、鏈表的方法實(shí)現(xiàn)
（1）display方法
（2）size方法
（3）contains方法
（4）addFirst方法
（5）addLast方法
（6）addIndex方法
（7）remove方法
（8）removeAllKey方法
（9）clear方法
四、最終代碼
一、雙向不循環(huán)鏈表的概念
雙向不循環(huán)鏈表中的節(jié)點(diǎn)有三個(gè)域，一個(gè)是存儲數(shù)據(jù)的val域，一個(gè)是前驅(qū)prev域，還有一個(gè)是下個(gè)節(jié)點(diǎn)next域，和單向不同的就是多了一個(gè)前驅(qū)域。如圖：
定義一個(gè)MyLinkedList類，這個(gè)類包含要模擬實(shí)現(xiàn)的方法，還有一個(gè)內(nèi)部類ListNode，這個(gè)內(nèi)部類就是鏈表的節(jié)點(diǎn)，代碼如下：
public class MyLinkedList implements Ilist{
public ListNode head;//頭結(jié)點(diǎn)
public ListNode last;//尾結(jié)點(diǎn)
static class ListNode {
int val;
ListNode next;
ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
}二、鏈表的接口
代碼如下：
public interface Ilist {
//頭插法
void addFirst(int data);
//尾插法
void addLast(int data);
//任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號下標(biāo)
void addIndex(int index,int data);
//查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中
boolean contains(int key);
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
void remove(int key);
//刪除所有值為key的節(jié)點(diǎn)
void removeAllKey(int key);
//得到單鏈表的長度
int size();
void clear();
void display();
}三、鏈表的方法實(shí)現(xiàn)
（1）display方法
此方法是打印所有鏈表節(jié)點(diǎn)的val值，因此要遍歷一遍鏈表的節(jié)點(diǎn)。代碼如下：
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}（2）size方法
此方法計(jì)算鏈表中有多少個(gè)節(jié)點(diǎn)，所以也要遍歷一遍鏈表，代碼如下：
public int size() {
ListNode cur = this.head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}（3）contains方法
此方法查看是否有key值，有就返回true，沒有就返回false，所以也要遍歷一遍鏈表，代碼如下：
public int size() {
ListNode cur = this.head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}（4）addFirst方法
此方法是頭插方法，參數(shù)是鏈表的val域的值，所以調(diào)用此方法時(shí)，要創(chuàng)建一個(gè)節(jié)點(diǎn)，再把這個(gè)節(jié)點(diǎn)進(jìn)行頭插；頭插時(shí)，要修改要插入節(jié)點(diǎn)的next域，指向原來的頭結(jié)點(diǎn)，還有原來頭結(jié)點(diǎn)的prev域，指向要插入的節(jié)點(diǎn)，最后再把頭結(jié)點(diǎn)改為要插入的這個(gè)節(jié)點(diǎn)，如圖：綠色箭頭是修改指向
因?yàn)槭切陆ǖ墓?jié)點(diǎn)，所以這個(gè)節(jié)點(diǎn)的prev和next域都是null
修改完后，如圖：
代碼如下：
public void addFirst(int data) {
ListNode cur = new ListNode(data);
if(this.head == null) {
this.head = cur;
this.last = cur;
} else {
cur.next = this.head;
this.head.prev = cur;
this.head = cur;
}
}執(zhí)行效果如下：
（5）addLast方法
此方法是尾插法，這里的尾插法時(shí)間復(fù)雜度是O(1)，因?yàn)殡p向鏈表有一個(gè)記錄尾結(jié)點(diǎn)的last，所以尾插的時(shí)候直接在尾結(jié)點(diǎn)插入要插入的節(jié)點(diǎn)，修改原來的尾結(jié)點(diǎn)的next域，要插入的節(jié)點(diǎn)prev修改成原來的尾結(jié)點(diǎn)，最后再把尾結(jié)點(diǎn)last修改成插入的節(jié)點(diǎn)，代碼如下：
public void addLast(int data) {
ListNode cur = new ListNode(data);
if(last == null) {
head = cur;
last = cur;
} else {
last.next = cur;
cur.prev = last;
last = cur;
}
}
執(zhí)行效果如下：
（6）addIndex方法
此方法是在指定位置插入節(jié)點(diǎn)，第一要檢查要插入位置的index下標(biāo)是否合法，不合法就拋異常，這里定義第一個(gè)節(jié)點(diǎn)下標(biāo)為0，第二個(gè)節(jié)點(diǎn)下標(biāo)為1，依次類推，如果要插入位置的下標(biāo)是0，就是頭插，如果要插入位置的下標(biāo)是鏈表長度（size方法），就是尾插；
要插入的位置在鏈表中間，我們要找出指定位置的前一個(gè)節(jié)點(diǎn)，修改前一個(gè)節(jié)點(diǎn)的next域，修改成要插入的節(jié)點(diǎn)，還有指定位置原來的節(jié)點(diǎn)的prev域也要修改，修改成要插入的節(jié)點(diǎn)。代碼如下：
public void addIndex(int index, int data) {
//檢查下標(biāo)是否合法
if(index < 0 || index > size()) {
throw new IndexException("下標(biāo)不合法");
}
if(index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode cur = new ListNode(data);
ListNode prev = this.head;
int count = 0;
while (count < index - 1) {
prev = prev.next;
count++;
}
ListNode prevNext = prev.next;
prev.next = cur;
cur.prev = prev;
cur.next = prevNext;
prevNext.prev = cur;
}
//自定義異常類
public class IndexException extends RuntimeException{
public IndexException(String e) {
super(e);
}
}
執(zhí)行效果如下：
（7）remove方法
此方法是移除第一個(gè)值為key的鏈表節(jié)點(diǎn)的方法，參數(shù)是就是key；要移除某一個(gè)節(jié)點(diǎn)，就要從頭遍歷一遍鏈表，如果沒找到key值，就直接返回，不做任何操作；
這里要提前處理一些特殊情況，如果頭結(jié)點(diǎn)的val值就是key，就要把head放在head的next域，然后判斷這時(shí)候head是不是空，如果head不是空，head的prev就要修改成空，如果head是空，就要把last設(shè)為空，直接返回。
如果找到了，就要找要刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，這里會分兩種情況，一種是要刪除的節(jié)點(diǎn)后面沒有節(jié)點(diǎn)了（尾結(jié)點(diǎn)），這時(shí)我們把要刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的next域改成null，last改成前一個(gè)節(jié)點(diǎn)；如果要刪除的節(jié)點(diǎn)后面有節(jié)點(diǎn)，就要把前一個(gè)節(jié)點(diǎn)的next域改成要刪除的節(jié)點(diǎn)的next，后一個(gè)的prev域改成前一個(gè)節(jié)點(diǎn)，代碼如下：
public void remove(int key) {
if(head == null) {
return;
}
if(head.val == key) {
head = head.next;
if(head != null) {
head.prev = null;
} else {
last = null;
return;
}
}
ListNode prev = findPrev(key);
if(prev == null) {
//沒有要刪的元素
return;
}
ListNode cur = prev.next;
if(cur.next != null) {
prev.next = cur.next;
cur.next.prev = cur.prev;
} else {
//最后一個(gè)元素
prev.next = cur.next;//null
last = prev;
}
}
//找到要刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
private ListNode findPrev(int key) {
ListNode cur = this.head;
ListNode curNext = cur.next;
while (curNext != null) {
if(curNext.val != key) {
cur = cur.next;
curNext = curNext.next;
} else {
return cur;
}
}
return null;
}執(zhí)行效果如下：
（8）removeAllKey方法
此方法是刪除所有節(jié)點(diǎn)的val值為key的方法，所以，我們要遍歷一遍鏈表，如果head為空的話，就直接返回，不做任何操作；
我們定義prev是頭結(jié)點(diǎn)，cur是頭結(jié)點(diǎn)的next節(jié)點(diǎn)（要刪除的節(jié)點(diǎn)），從頭到尾遍歷的是cur，如果cur的val值不等于key，prev和cur都要往后走一步；如果cur的val值等于key，會分成兩種情況，就是cur后面是有沒有節(jié)點(diǎn)，如果后面有節(jié)點(diǎn)，prev節(jié)點(diǎn)的next域就要改成cur的next，cur的下一個(gè)節(jié)點(diǎn)的prev域要改成prev，然后cur往后走一步；如果cur后面的節(jié)點(diǎn)為空，就直接把prev節(jié)點(diǎn)的next域改成空，把last改成prev，cur還要往后走一步結(jié)束循環(huán)。
最后不要忘了頭結(jié)點(diǎn)還沒有判斷，要判斷頭結(jié)點(diǎn)的val值是否和key相等，如果不相等就不做任何操作，相等就把頭結(jié)點(diǎn)head改成頭結(jié)點(diǎn)的next，此時(shí)的頭結(jié)點(diǎn)的prev改成null，注意，這里修改頭結(jié)點(diǎn)的prev，要頭結(jié)點(diǎn)head不為空，才能執(zhí)行上面的操作，不然會空指針異常。
public void removeAllKey(int key) {
if(head == null) {
return;
}
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if(cur.val == key) {
if(cur.next != null) {
prev.next = cur.next;
cur.next.prev = prev;
} else {
prev.next = cur.next;//null
last = prev;
}
cur = cur.next;
} else {
prev = prev.next;
cur = cur.next;
}
}
if(head.val == key) {
head = head.next;
if(head != null) {
head.prev = null;
}
}
}執(zhí)行效果如下：
（9）clear方法
此方法是把鏈表中的所有節(jié)點(diǎn)中所有域都置為空，所以要遍歷一遍鏈表，把節(jié)點(diǎn)prev和next域改為null，因?yàn)檫@里的val域類型是int，所以不用修改val域，代碼如下：
public void clear() {
ListNode cur = this.head;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = null;
cur.prev = null;
cur = curNext;
}
head = null;
last = null;
}執(zhí)行效果如下：文章來源：http://www.zghlxwxcb.cn/news/detail-770983.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-770983.html
四、最終代碼
public class MyLinkedList implements Ilist{
public ListNode head;//頭結(jié)點(diǎn)
public ListNode last;//尾結(jié)點(diǎn)
static class ListNode {
int val;
ListNode next;
ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
@Override
public void addFirst(int data) {
ListNode cur = new ListNode(data);
if(this.head == null) {
this.head = cur;
this.last = cur;
} else {
cur.next = this.head;
this.head.prev = cur;
this.head = cur;
}
}
@Override
public void addLast(int data) {
ListNode cur = new ListNode(data);
if(last == null) {
head = cur;
last = cur;
} else {
last.next = cur;
cur.prev = last;
last = cur;
}
}
@Override
public void addIndex(int index, int data) {
//檢查下標(biāo)是否合法
if(index < 0 || index > size()) {
throw new IndexException("下標(biāo)不合法");
}
if(index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode cur = new ListNode(data);
ListNode prev = this.head;
int count = 0;
while (count < index - 1) {
prev = prev.next;
count++;
}
ListNode prevNext = prev.next;
prev.next = cur;
cur.prev = prev;
cur.next = prevNext;
prevNext.prev = cur;
}
@Override
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
@Override
public void remove(int key) {
if(head == null) {
return;
}
if(head.val == key) {
head = head.next;
if(head != null) {
head.prev = null;
} else {
last = null;
return;
}
}
ListNode prev = findPrev(key);
if(prev == null) {
//沒有要刪的元素
return;
}
ListNode cur = prev.next;
if(cur.next != null) {
prev.next = cur.next;
cur.next.prev = cur.prev;
} else {
//最后一個(gè)元素
prev.next = cur.next;//null
last = prev;
}
}
private ListNode findPrev(int key) {
ListNode cur = this.head;
ListNode curNext = cur.next;
while (curNext != null) {
if(curNext.val != key) {
cur = cur.next;
curNext = curNext.next;
} else {
return cur;
}
}
return null;
}
@Override
public void removeAllKey(int key) {
if(head == null) {
return;
}
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if(cur.val == key) {
if(cur.next != null) {
prev.next = cur.next;
cur.next.prev = prev;
} else {
prev.next = cur.next;//null
last = prev;
}
cur = cur.next;
} else {
prev = prev.next;
cur = cur.next;
}
}
if(head.val == key) {
head = head.next;
if(head != null) {
head.prev = null;
}
}
}
@Override
public int size() {
ListNode cur = this.head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
@Override
public void clear() {
ListNode cur = this.head;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = null;
cur.prev = null;
cur = curNext;
}
head = null;
last = null;
}
@Override
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
}
//自定義異常類
public class IndexException extends RuntimeException{
public IndexException(String e) {
super(e);
}
}
都看到這了，點(diǎn)個(gè)贊再走吧，謝謝謝謝謝?。?！
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)模擬實(shí)現(xiàn)LinkedList雙向不循環(huán)鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[Collection與數(shù)據(jù)結(jié)構(gòu)] 鏈表與LinkedList (一):鏈表概述與單向無頭非循環(huán)鏈表實(shí)現(xiàn)](https://imgs.yssmx.com/Uploads/2024/04/858484-1.png)
