1.雙鏈表
雙鏈表是一種數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)包含一個(gè)指向前一個(gè)節(jié)點(diǎn)的指針和一個(gè)指向后一個(gè)節(jié)點(diǎn)的指針。由于鏈表沒有將元素存儲(chǔ)在連續(xù)的空間中，元素存儲(chǔ)在單獨(dú)的節(jié)點(diǎn)中，然后通過引用將節(jié)點(diǎn)連接起來，因此雙鏈表可以任意且快速的插入和刪除元素。
2.雙鏈表的創(chuàng)建
引用接口IList，在把IList接口里面的方法進(jìn)行重寫，實(shí)現(xiàn)雙鏈表的功能。把雙鏈表封裝成一個(gè)類，類中封裝一個(gè)節(jié)點(diǎn)類ListNode，里面的節(jié)點(diǎn)類有當(dāng)前節(jié)點(diǎn)的值val、指向前一個(gè)節(jié)點(diǎn)的ListNode prev和指向后一個(gè)節(jié)點(diǎn)的變量ListNode next。最后在外部類中定義頭節(jié)點(diǎn)、尾節(jié)點(diǎn)，利用外部類的構(gòu)造器中就可以對(duì)頭尾節(jié)點(diǎn)的初始化。
public class MyLinkedList implements IList{
static class ListNode {
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode last;
}
3.雙鏈表的頭插節(jié)點(diǎn)
頭插node節(jié)點(diǎn)，如果鏈表為空，直接把插入的節(jié)點(diǎn)設(shè)為頭尾節(jié)點(diǎn)，不為空把node的下一個(gè)節(jié)點(diǎn)指向head頭節(jié)點(diǎn)，再把head的前節(jié)點(diǎn)指向node，最后把head指向node。
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
}else {
node.next = head;
head.prev = node;
head = node;
}
}
4.雙鏈表尾插
尾插node節(jié)點(diǎn)，如果鏈表為空，直接把插入的節(jié)點(diǎn)設(shè)為頭尾節(jié)點(diǎn)，不為空把last尾節(jié)點(diǎn)的next（即后節(jié)點(diǎn)）指向node，再把node的前節(jié)點(diǎn)prev指向last，最后把尾節(jié)點(diǎn)last指向node。
@Override
public void addLast(int data) {
ListNode node = new ListNode(data);
if (head == null) {
head = node;
last = node;
}else {
last.next = node;
node.prev = last;
last = node;
}
}
5.雙鏈表根據(jù)索引找節(jié)點(diǎn)
定義一個(gè)count變量來計(jì)數(shù)，從頭節(jié)點(diǎn)開始遍歷，當(dāng)計(jì)數(shù)值為索引值退出循環(huán)，返回cur為插入節(jié)點(diǎn)的后節(jié)點(diǎn)。
private ListNode findIndex(int index) {
int count = 0;
ListNode cur = head;
while (count != index) {
count++;
cur = cur.next;
}
return cur;
}
6.雙鏈表根據(jù)索引插入節(jié)點(diǎn)
根據(jù)索引插入可分三種情況：
- 當(dāng)在最前面插入節(jié)點(diǎn)時(shí)為頭插法
- 在最后一個(gè)位置插入則是尾插法
- 中間插入時(shí)遍歷鏈表找到插入節(jié)點(diǎn)為node的下標(biāo)，然后1：把node的后節(jié)點(diǎn)指向cur 即node.next = cur；2：把cur前節(jié)點(diǎn)的后節(jié)點(diǎn)指向node，即cur.prev.next = node；3：把node的前節(jié)點(diǎn)指向cur的前節(jié)點(diǎn)，即node.prev = cur.prev；4：把cur的前節(jié)點(diǎn)指向node，即cur.prev = node。
@Override
public void addIndex(int index, int data) throws IndexException{
if (index < 0 || index > size()) {
throw new IndexException("雙向鏈表插入，index不合法"+index);
}
ListNode node = new ListNode(data);
// 在0位置就是頭插法
if(index == 0) {
addFirst(data);
return;
}
// 在最后一個(gè)位置插入
if (index == size()) {
addLast(data);
return;
}
// 中間
ListNode cur = findIndex(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
}
7.雙鏈表刪除值為key的節(jié)點(diǎn)
遍歷鏈表，若cur.val為key，刪除cur節(jié)點(diǎn)文章來源：http://www.zghlxwxcb.cn/news/detail-794885.html
- 若cur為head頭節(jié)點(diǎn)時(shí)，把head指向head的后節(jié)點(diǎn)，當(dāng)head不為空時(shí)，把head的前節(jié)點(diǎn)直接置為null，只有一個(gè)節(jié)點(diǎn)時(shí)直接把last指向null。
- 當(dāng)cur不等于頭節(jié)點(diǎn)head時(shí)，把cur前節(jié)點(diǎn)的后節(jié)點(diǎn)指向cur的后節(jié)點(diǎn)，即：cur.prev.next = cur.next。若cur的后節(jié)點(diǎn)不為空即刪除中間節(jié)點(diǎn)時(shí)：把cur的后節(jié)點(diǎn)的前節(jié)點(diǎn)指向cur的前節(jié)點(diǎn)，即：cur.next.prev = cur.prev，若cur為尾節(jié)點(diǎn)時(shí)，把last指向last的前節(jié)點(diǎn)，即：last = last.prev。
@Override
public void remove(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
if (cur == head) {
head = head.next;
if (head != null) {
head.prev = null;
}else {
//只有一個(gè)節(jié)點(diǎn) 且是需要?jiǎng)h除的節(jié)點(diǎn)
last = null;
}
}else {
cur.prev.next = cur.next;
//刪除中間節(jié)點(diǎn)
if (cur.next != null) {
//cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}else {
// 刪除尾巴節(jié)點(diǎn)
//cur.next.prev = cur.next;
last = last.prev;
}
}
return;
}
cur = cur.next;
}
}
8.刪除所有值為key的節(jié)點(diǎn)
即上面刪除完第一個(gè)key的節(jié)點(diǎn)之后不跳出循環(huán)，接著刪除。文章來源地址http://www.zghlxwxcb.cn/news/detail-794885.html
@Override
public void removeAllKey(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
if (cur == head) {
head = head.next;
if (head != null) {
head.prev = null;
}else {
//只有一個(gè)節(jié)點(diǎn) 且是需要?jiǎng)h除的節(jié)點(diǎn)
last = null;
}
}else {
cur.prev.next = cur.next;
//刪除中間節(jié)點(diǎn)
if (cur.next != null) {
//cur.prev.next = cur.next;
cur.next.prev = cur.prev;
}else {
// 刪除尾巴節(jié)點(diǎn)
//cur.next.prev = cur.next;
last = last.prev;
}
}
}
cur = cur.next;
}
}
9.雙鏈表是否包含值為key節(jié)點(diǎn)
@Override
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
10.雙鏈表大小
@Override
public int size() {
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
11.清空雙鏈表
@Override
public void clear() {
ListNode cur = head;
while (cur != null) {
ListNode curNext = cur.next;
cur.next = null;
cur.prev = null;
cur = curNext;
}
this.head = null;
this.last = null;
}
12.打印雙鏈表
@Override
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
到了這里，關(guān)于【Java數(shù)據(jù)結(jié)構(gòu) -- 實(shí)現(xiàn)雙鏈表的接口方法】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
