Java實現(xiàn)鏈表數(shù)據(jù)結(jié)構的方法
更新時間：2022年01月13日 14:20:07 作者：胡安民
這篇文章主要介紹了Java實現(xiàn)鏈表數(shù)據(jù)結(jié)構的相關資料,每一個鏈表都包含多個節(jié)點，節(jié)點又包含兩個部分，一個是數(shù)據(jù)域（儲存節(jié)點含有的信息），一個是引用域（儲存下一個節(jié)點或者上一個節(jié)點的地址），需要的朋友可以參考下
什么是鏈表？
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針連接次序?qū)崿F(xiàn)的。
每一個鏈表都包含多個節(jié)點，節(jié)點又包含兩個部分，一個是數(shù)據(jù)域（儲存節(jié)點含有的信息），一個是引用域（儲存下一個節(jié)點或者上一個節(jié)點的地址）。
鏈表的理解示意圖:
鏈表的特點是什么？
獲取數(shù)據(jù)麻煩，需要遍歷查找，比數(shù)組慢
方便插入、刪除
簡單的鏈表的實現(xiàn)原理
創(chuàng)建一個節(jié)點類，其中節(jié)點類包含兩個部分，第一個是數(shù)據(jù)域（你到時候要往節(jié)點里面儲存的信息），第二個是引用域（相當于指針，單向鏈表有一個指針，指向下一個節(jié)點；雙向鏈表有兩個指針，分別指向下一個和上一個節(jié)點）
創(chuàng)建一個鏈表類，其中鏈表類包含三個屬性：頭結(jié)點、尾節(jié)點和大小，方法包含添加、刪除、插入等等方法。 通用節(jié)點抽象類
package com.lineardatastructure.linked;
/**
* @author huanmin
* @param <T>
*/
/**
* 自定義鏈表接口定義
**/
public abstract class LinkedAbs<T> implements Iterable<T> {
//列表長度
public int size = 0;
//當前節(jié)點
public Node head;
//尾節(jié)點
public Node end;
//節(jié)點
protected class Node {
Node previous = null;//上一個結(jié)點
Node next = null;//下一個結(jié)點
T data;//結(jié)點數(shù)據(jù)
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
public Node(Node next, Node previous) {
this.next = next;
this.previous = previous;
}
public Node(T data, Node next, Node previous) {
this.next = next;
this.previous = previous;
}
public Node(T data) {
this.data = data;
}
}
/**
* 判斷鏈表是否有環(huán)：
* 有環(huán)返回環(huán)的入口節(jié)點,沒有返回null
* 設置快指針和慢指針，慢指針每次走一步，快指針每次走兩步
* 當快指針與慢指針相等時，就說明該鏈表有環(huán),并且這個節(jié)點就是環(huán)的入口
*/
public Node isRinged(){
if(head == null){
return null;
}
Node slow = head;
Node fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
return fast;
}
}
return null;
}
// 獲取鏈表頭元素
public T getFrom() {
return head.data;
}
//獲取鏈表結(jié)尾元素
public T getEnd() {
return end.data;
}
//獲取鏈表中元素個數(shù)
public int getSize() {
return size;
}
/**
* 判斷鏈表中是否為空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 銷毀鏈表
*/
public void stackDestroy() {
head = null;
size = 0;
end=null;
}
//尋找單鏈表的中間結(jié)點：
public abstract T findMiddle();
/**
* 元素反轉(zhuǎn)
*/
public abstract void reserveLink();
/**
* 獲取指定元素
*
* @param index
*/
public abstract T get(int index);
/**
* 向鏈表中添加元素
*
* @param e
*/
public abstract void addFirst(T e);
public abstract void addlast(T e);
public abstract void add(T e);
/**
* 從鏈表中刪除元素
*/
public abstract boolean remove(T obj);
public abstract boolean remove(int index);
public abstract boolean removeFirst();
public abstract boolean removeLast();
}實現(xiàn)單向鏈表
package com.lineardatastructure.linked;
import java.util.Iterator;
/**
* @author huanmin
* @param <T>
*/
// 單向鏈表
public class OneWayLinked<T> extends LinkedAbs<T> {
@Override
public void reserveLink() {
Node curNode = head;//頭結(jié)點
Node preNode = null;//前一個結(jié)點
while(curNode != null){
Node nextNode = curNode.next;//保留下一個結(jié)點
curNode.next = preNode;//指針反轉(zhuǎn)
preNode = curNode;//前結(jié)點后移
curNode = nextNode;//當前結(jié)點后移
}
head = preNode;
}
/**
* 尋找單鏈表的中間結(jié)點：
* 方法一、先求出鏈表的長度，再遍歷1/2鏈表長度，尋找出鏈表的中間結(jié)點
* 方法二、：
* 用兩個指針遍歷鏈表，一個快指針、一個慢指針，
* 快指針每次向前移動2個結(jié)點，慢指針一次向前移動一個結(jié)點，
* 當快指針移動到鏈表的末尾，慢指針所在的位置即為中間結(jié)點所在的位置
*/
@Override
public T findMiddle() {
Node slowPoint = head;
Node quickPoint = head;
//quickPoint.next == null是鏈表結(jié)點個數(shù)為奇數(shù)時，快指針已經(jīng)走到最后了
//quickPoint.next.next == null是鏈表結(jié)點數(shù)為偶數(shù)時，快指針已經(jīng)走到倒數(shù)第二個結(jié)點了
//鏈表結(jié)點個數(shù)為奇數(shù)時,返回的是中間結(jié)點；鏈表結(jié)點個數(shù)為偶數(shù)時，返回的是中間兩個結(jié)點中的前一個
while (quickPoint.next != null && quickPoint.next.next != null) {
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint.data;
}
/**
* 查詢指定下標數(shù)據(jù)
* @param index
* @return
*/
@Override
public T get(int index) {
if(size<0 || index>size){//待查詢結(jié)點不存在
return null;
}
if(index == 0){//查詢頭結(jié)點
return head.data;
}
Node curNode =head;
int i = 0;
while (curNode != null) {
if(i==index){//尋找到待查詢結(jié)點
return curNode.data;
}
//當先結(jié)點和前結(jié)點同時向后移
curNode = curNode.next;
i++;
}
return null;
}
@Override
public void addFirst(T e) {
}
@Override
public void addlast(T e) {
}
/**
* 鏈表添加結(jié)點:
* 找到鏈表的末尾結(jié)點，把新添加的數(shù)據(jù)作為末尾結(jié)點的后續(xù)結(jié)點
*
* @param data
*/
@Override
public void add(T data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
end=head;//添加尾節(jié)點
size++;
return;
}
Node temp = end;
temp.next = newNode;
end=newNode;//修改尾節(jié)點
size++;
}
/**
* 鏈表刪除結(jié)點:
* 把要刪除結(jié)點的前結(jié)點指向要刪除結(jié)點的后結(jié)點，即直接跳過待刪除結(jié)點
* @param obj
* @return
*/
@Override
public boolean remove(T obj) {
if (head.data.equals(obj)) {//刪除頭結(jié)點
head = head.next;
size=0;
return true;
}
Node preNode = head;
Node curNode = preNode.next;
while (curNode != null) {
if (curNode.data.equals(obj)) {//尋找到待刪除結(jié)點
preNode.next = curNode.next;//待刪除結(jié)點的前結(jié)點指向待刪除結(jié)點的后結(jié)點
size--;
return true;
}
//當先結(jié)點和前結(jié)點同時向后移
preNode = preNode.next;
curNode = curNode.next;
}
return false;
}
@Override
public boolean remove(int index) {
if(size<0 || index>size){//待刪除結(jié)點不存在
return false;
}
if(index == 0){//刪除頭結(jié)點
head = head.next;
return true;
}
Node preNode = head;
Node curNode =head.next;
int i =1; //從第2個值開始
while(preNode.next != null){
if(i==index){//尋找到待刪除結(jié)點
preNode.next= curNode.next;//待刪除結(jié)點的前結(jié)點指向待刪除結(jié)點的后結(jié)點
return true;
}
//當先結(jié)點和前結(jié)點同時向后移
preNode=curNode;
curNode = curNode.next;
i++;
}
return false;
}
@Override
public boolean removeFirst() {
return false;
}
@Override
public boolean removeLast() {
return false;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node cursor = head;
T data;
@Override
public boolean hasNext() {
if (cursor != null) {
data = cursor.data;
cursor = cursor.next;
return true;
}
return false;
}
@Override
public T next() {
return data;
}
@Override
public void remove() {
OneWayLinked.this.remove(data);
}
};
}
}單向環(huán)形鏈表
它和單鏈表的區(qū)別在于結(jié)尾點的指針域不是指向null，而是指向頭結(jié)點，形成首尾相連的環(huán)。這種首尾相連的單鏈表稱為單向循環(huán)鏈表。循環(huán)鏈表可以從任意一個結(jié)點出發(fā)，訪問到鏈表中的全部結(jié)點。
單向循環(huán)鏈表的查找、刪除和修改操作與單鏈表一致(這里不在贅述，可參考前面的內(nèi)容)，插入操作和單鏈表有所不同，單向循環(huán)鏈表需要維持環(huán)狀結(jié)構。判斷單鏈表為空的條件是head.next == null，而判斷單向循環(huán)鏈表為空的條件為head.next == head。
package com.lineardatastructure.linked;
import java.util.Iterator;
/**
* @param <T>
* @author huanmin
*/
// 單向循環(huán)鏈表
public class OneLoopWayLinked<T> extends LinkedAbs<T> {
@Override
public void reserveLink() {
Object[] ts = new Object[size];
int i = size - 1;
for (T t : this) {
ts[i] = t;
i--;
}
Node node = head;
node.data = (T) ts[0];
for (int i1 = 1; i1 < ts.length; i1++) {
Node node1 = new Node((T) ts[i1]);
node.next = node1;
node = node1;
end= node1;
}
//調(diào)整位置
end.next=head;
}
/**
* 尋找單鏈表的中間結(jié)點：
* 方法一、先求出鏈表的長度，再遍歷1/2鏈表長度，尋找出鏈表的中間結(jié)點
* 方法二、：
* 用兩個指針遍歷鏈表，一個快指針、一個慢指針，
* 快指針每次向前移動2個結(jié)點，慢指針一次向前移動一個結(jié)點，
* 當快指針移動到鏈表的末尾，慢指針所在的位置即為中間結(jié)點所在的位置
*/
@Override
public T findMiddle() {
Node slowPoint = head;
Node quickPoint = head;
//quickPoint.next == null是鏈表結(jié)點個數(shù)為奇數(shù)時，快指針已經(jīng)走到最后了
//quickPoint.next.next == null是鏈表結(jié)點數(shù)為偶數(shù)時，快指針已經(jīng)走到倒數(shù)第二個結(jié)點了
//鏈表結(jié)點個數(shù)為奇數(shù)時,返回的是中間結(jié)點；鏈表結(jié)點個數(shù)為偶數(shù)時，返回的是中間兩個結(jié)點中的前一個
while (quickPoint.next != head && quickPoint.next.next != head) {
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint.data;
}
/**
* 查詢指定下標數(shù)據(jù)
*
* @param index
* @return
*/
@Override
public T get(int index) {
if (size < 0 || index > size) {//待查詢結(jié)點不存在
return null;
}
if (index == 0) {//查詢頭結(jié)點
return head.data;
}
Node curNode = head.next;
int i = 1;
while (curNode != head) {
if (i == index) {//尋找到待查詢結(jié)點
return curNode.data;
}
//當先結(jié)點和前結(jié)點同時向后移
curNode = curNode.next;
i++;
}
return null;
}
@Override
public void addFirst(T e) {
}
@Override
public void addlast(T e) {
}
/**
* 鏈表添加結(jié)點:
* 找到鏈表的末尾結(jié)點，把新添加的數(shù)據(jù)作為末尾結(jié)點的后續(xù)結(jié)點
*
* @param data
*/
@Override
public void add(T data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
head.next = head; //環(huán)型
end = head;//添加尾節(jié)點
size++;
return;
}
Node temp = end;
//一直遍歷到最后
temp.next = newNode;
newNode.next = head;//環(huán)型
end = newNode;//修改尾節(jié)點
size++;
}
/**
* 鏈表刪除結(jié)點:
* 把要刪除結(jié)點的前結(jié)點指向要刪除結(jié)點的后結(jié)點，即直接跳過待刪除結(jié)點
*
* @param obj
* @return
*/
@Override
public boolean remove(T obj) {
if (head.data.equals(obj)) {//刪除頭結(jié)點
head = head.next;
end.next=head;//調(diào)整環(huán)
size--;
return true;
}
Node preNode = head;
Node curNode = preNode.next;
while (curNode != head) {
if (curNode.data.equals(obj)) {//尋找到待刪除結(jié)點
preNode.next = curNode.next;//待刪除結(jié)點的前結(jié)點指向待刪除結(jié)點的后結(jié)點
size--;
return true;
}
//當先結(jié)點和前結(jié)點同時向后移
preNode = preNode.next;
curNode = curNode.next;
}
return false;
}
@Override
public boolean remove(int index) {
if (size < 0 || index > size) {//待刪除結(jié)點不存在
return false;
}
if (index == 0) {//刪除頭結(jié)點
head = head.next;
end.next=head;//調(diào)整環(huán)
size--;
return true;
}
Node preNode = head;
Node curNode = head.next;
int i = 1; //從第2個值開始
while (preNode.next != head) {
if (i == index) {//尋找到待刪除結(jié)點
preNode.next = curNode.next;//待刪除結(jié)點的前結(jié)點指向待刪除結(jié)點的后結(jié)點
return true;
}
//當先結(jié)點和前結(jié)點同時向后移
preNode = curNode;
curNode = curNode.next;
i++;
}
size--;
return false;
}
@Override
public boolean removeFirst() {
return false;
}
@Override
public boolean removeLast() {
return false;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node cursor = head;
T data;
@Override
public boolean hasNext() {
if (cursor != null&&cursor.next != head) {
data = cursor.data;
cursor = cursor.next;
return true;
}
if (cursor != null) {
data = cursor.data;
cursor = null;
return true;
}
return false;
}
@Override
public T next() {
return data;
}
@Override
public void remove() {
OneLoopWayLinked.this.remove(data);
}
};
}
}實現(xiàn)雙向鏈表
package com.lineardatastructure.linked;
import java.util.Iterator;
/**
* @author huanmin
* @param <T>
*/
public class BothwayLinked<T> extends LinkedAbs<T> {
/**
* 查詢指定下標數(shù)據(jù)
* @param index
* @return
*/
@Override
public T get(int index) {
if (size < 0 || index > size) {//待查詢結(jié)點不存在
return null;
}
if (index == 0) {//查詢頭結(jié)點
return head.data;
}
Node curNode = head;
int i = 0;
while (curNode != null) {
if (i == index) {//尋找到待查詢結(jié)點
return curNode.data;
}
//當先結(jié)點和前結(jié)點同時向后移
curNode = curNode.next;
i++;
}
return null;
}
@Override
public void addFirst(T e) {
Node next = head;
Node previous = new Node(e);
previous.next = next;
next.previous = previous;
head=previous;
size++;
}
@Override
public void addlast(T e) {
Node newNode = new Node(e);
if (head == null) {
head = newNode;
size++;
end=head;//添加尾節(jié)點
return;
}
Node temp = end;
temp.next = newNode;
newNode.previous = temp;
end=newNode;//修改尾節(jié)點
size++;
}
@Override
public void add(T e) {
addlast(e);
}
@Override
public boolean remove(T obj) {
if (removeHead()) {
return true;
}
Node curNode = head;
while (curNode != null) {
//尋找到待刪除結(jié)點
if (curNode.data.equals(obj)) {
//將刪除的節(jié)點后節(jié)點,覆蓋刪除的節(jié)點,然后將父節(jié)點指向被刪除元素的父節(jié)點
Node previous = curNode.previous;
Node next = curNode.next;
if (next == null) {
//刪除的是最后節(jié)點,那么就把他上一個節(jié)點的下一個節(jié)點刪除
previous.next=null;
} else if (previous==null) {
//刪除的是頭節(jié)點的話,那么就不管父節(jié)點了
head=head.next;
head.previous=null;
} else {
next.previous = previous;
previous.next = next;
}
size--;
return true;
}
//當先結(jié)點向后移
curNode = curNode.next;
}
return false;
}
@Override
public boolean remove(int index) {
if (index<0 ||index >= size) {//待刪除結(jié)點不存在
return false;
}
if (removeHead()) {
return true;
}
Node curNode = head;
int i = 0;
while (curNode != null) {
if (i == index) {//尋找到待刪除結(jié)點
//將刪除的節(jié)點后節(jié)點,覆蓋刪除的節(jié)點,然后將父節(jié)點指向被刪除元素的父節(jié)點
Node previous = curNode.previous;
Node next = curNode.next;
if (next == null) {
//刪除的是最后節(jié)點,那么就把他上一個節(jié)點的下一個節(jié)點刪除
previous.next=null;
} else if (previous==null) {
//刪除的是頭節(jié)點的話,那么就不管父節(jié)點了
head=head.next;
head.previous=null;
} else {
next.previous = previous;
previous.next = next;
}
size--;
return true;
}
//當先結(jié)點向后移
curNode = curNode.next;
i++;
}
return false;
}
@Override
public boolean removeFirst() {
if (removeHead()) {
return true;
}
Node node = head.next;
node.previous = null;
head = node;
size--;
return false;
}
@Override
public boolean removeLast() {
if (removeHead()) {
return true;
}
//刪除尾節(jié)點
end.previous.next=null;
size--;
return true;
}
//如果只有一個元素那么就將頭刪除
public boolean removeHead() {
if (head.next==null) {
head=null;
return true ;
}
return false;
}
@Override
public void reserveLink() {
Object[] ts = new Object[size];
int i = size - 1;
for (T t : this) {
ts[i] = t;
i--;
}
Node node = head;
node.data = (T) ts[0];
for (int i1 = 1; i1 < ts.length; i1++) {
Node node1 = new Node((T) ts[i1]);
node.next = node1;
node1.previous = node;
node = node1;
}
}
/**
* 尋找單鏈表的中間結(jié)點：
* 方法一、先求出鏈表的長度，再遍歷1/2鏈表長度，尋找出鏈表的中間結(jié)點
* 方法二、：
* 用兩個指針遍歷鏈表，一個快指針、一個慢指針，
* 快指針每次向前移動2個結(jié)點，慢指針一次向前移動一個結(jié)點，
* 當快指針移動到鏈表的末尾，慢指針所在的位置即為中間結(jié)點所在的位置
*/
@Override
public T findMiddle() {
Node slowPoint = head;
Node quickPoint = head;
//quickPoint.next == null是鏈表結(jié)點個數(shù)為奇數(shù)時，快指針已經(jīng)走到最后了
//quickPoint.next.next == null是鏈表結(jié)點數(shù)為偶數(shù)時，快指針已經(jīng)走到倒數(shù)第二個結(jié)點了
//鏈表結(jié)點個數(shù)為奇數(shù)時,返回的是中間結(jié)點；鏈表結(jié)點個數(shù)為偶數(shù)時，返回的是中間兩個結(jié)點中的前一個
while (quickPoint.next != null && quickPoint.next.next != null) {
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint.data;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node cursor = head;
T data;
@Override
public boolean hasNext() {
if (cursor != null) {
data = cursor.data;
cursor = cursor.next;
return true;
}
return false;
}
@Override
public T next() {
return data;
}
@Override
public void remove() {
BothwayLinked.this.remove(data);
}
};
}
}雙向循環(huán)鏈表
相比單鏈表，雙向循環(huán)鏈表是一個更加復雜的結(jié)構。因為雙向循環(huán)鏈表的節(jié)點不僅包含指向下一個節(jié)點的指針(next)，還包含指向前一個節(jié)點的指針(prev)。
在雙向循環(huán)鏈表中，可見的不只有頭指針head，還有尾節(jié)點end。這是和單鏈表的區(qū)別。
雙向循環(huán)鏈表的頭指針head的前一個節(jié)點指向end，尾節(jié)點end的后一個節(jié)點指向head。
注意: 雙向循環(huán)鏈表,實現(xiàn)反查詢特別容易只需要反過來遍歷一遍就行
package com.lineardatastructure.linked;
import org.w3c.dom.Node;
import java.util.Iterator;
/**
* @param <T>
* @author huanmin
*/
public class BothwayLoopLinked<T> extends LinkedAbs<T> {
@Override
public void reserveLink() {
Object[] ts = new Object[size];
int i = size - 1;
for (T t : this) {
ts[i] = t;
i--;
}
Node node = head;
node.data = (T) ts[0];
for (int i1 = 1; i1 < ts.length; i1++) {
Node node1 = new Node((T) ts[i1]);
node.next = node1;
node1.previous = node;
node = node1;
end= node1;
}
//調(diào)整位置
head.previous=end;
end.next=head;
}
/**
* 尋找單鏈表的中間結(jié)點：
* 方法一、先求出鏈表的長度，再遍歷1/2鏈表長度，尋找出鏈表的中間結(jié)點
* 方法二、：
* 用兩個指針遍歷鏈表，一個快指針、一個慢指針，
* 快指針每次向前移動2個結(jié)點，慢指針一次向前移動一個結(jié)點，
* 當快指針移動到鏈表的末尾，慢指針所在的位置即為中間結(jié)點所在的位置
*/
@Override
public T findMiddle() {
Node slowPoint = head;
Node quickPoint = head;
//quickPoint.next == null是鏈表結(jié)點個數(shù)為奇數(shù)時，快指針已經(jīng)走到最后了
//quickPoint.next.next == null是鏈表結(jié)點數(shù)為偶數(shù)時，快指針已經(jīng)走到倒數(shù)第二個結(jié)點了
//鏈表結(jié)點個數(shù)為奇數(shù)時,返回的是中間結(jié)點；鏈表結(jié)點個數(shù)為偶數(shù)時，返回的是中間兩個結(jié)點中的前一個
while (quickPoint.next != head && quickPoint.next.next != head) {
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint.data;
}
/**
* 查詢指定下標數(shù)據(jù)
* @param index
* @return
*/
@Override
public T get(int index) {
if (size < 0 || index > size) {//待查詢結(jié)點不存在
return null;
}
if (index == 0) {//查詢頭結(jié)點
return head.data;
}
Node curNode = head.next;
int i = 1;
while ( curNode!= head) {
if (i == index) {//尋找到待查詢結(jié)點
return curNode.data;
}
//當先結(jié)點和前結(jié)點同時向后移
curNode = curNode.next;
i++;
}
return null;
}
@Override
public void addFirst(T e) {
Node next = head;
Node previous = new Node(e);
previous.previous = head.previous;
previous.next = next;
next.previous = previous;
head = previous;
end.next=previous;//修改尾節(jié)點的指向
size++;
}
@Override
public void addlast(T e) {
Node newNode = new Node(e);
if (head == null) {
head = newNode;
head.previous=head;//環(huán)型
head.next=head; //環(huán)型
end=head;//添加尾節(jié)點
size++;
return;
}
Node temp = end;
temp.next = newNode;
newNode.previous = temp;
newNode.next = head;//給為節(jié)點添加頭節(jié)點(環(huán)型)
end=newNode;//修改尾節(jié)點
size++;
}
@Override
public void add(T e) {
addlast(e);
}
@Override
public boolean remove(T obj) {
if (removeHead()) {
return true;
}
//頭部刪除需要特殊處理
if (obj == head.data) {
Node previous = head.previous;
head = head.next;
head.previous = previous;
end.next=head;
size--;
return true;
}
Node curNode = head.next;
while (curNode != head) {
//尋找到待刪除結(jié)點
if (curNode.data.equals(obj)) {
//將刪除的節(jié)點后節(jié)點,覆蓋刪除的節(jié)點,然后將父節(jié)點指向被刪除元素的父節(jié)點
Node previous = curNode.previous;
Node next = curNode.next;
if (next == null) {
//刪除的是最后節(jié)點,那么就把他上一個節(jié)點的下一個節(jié)點刪除
previous.next = null;
} else {
next.previous = previous;
previous.next = next;
}
size--;
return true;
}
//當先結(jié)點向后移
curNode = curNode.next;
}
return false;
}
@Override
public boolean remove(int index) {
if (removeHead()) {
return true;
}
if (size < 0 || index >= size) {//待刪除結(jié)點不存在
return false;
}
//頭部刪除需要特殊處理
if (index==0) {
Node previous = head.previous;
head = head.next;
head.previous = previous;
size--;
return true;
}
Node curNode = head.next;
int i = 1;
while (curNode != null) {
if (i == index) {//尋找到待刪除結(jié)點
//將刪除的節(jié)點后節(jié)點,覆蓋刪除的節(jié)點,然后將父節(jié)點指向被刪除元素的父節(jié)點
Node previous = curNode.previous;
Node next = curNode.next;
if (next == null) {
//刪除的是最后節(jié)點,那么就把他上一個節(jié)點的下一個節(jié)點給替換成頭節(jié)點
previous.next = head;
} else {
next.previous = previous;
previous.next = next;
}
size--;
return true;
}
//當先結(jié)點向后移
curNode = curNode.next;
i++;
}
return false;
}
@Override
public boolean removeFirst() {
head = head.next;
head.previous = end; //環(huán)繞
end.next=head; //環(huán)繞
size--;
return false;
}
@Override
public boolean removeLast() {
//將刪除結(jié)尾節(jié)點
end.previous.next=head;
size--;
return true;
}
//如果只有一個元素那么就將頭刪除
public boolean removeHead() {
if (head.next==null) {
head=null;
return true ;
}
return false;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
Node cursor = head;
T data;
@Override
public boolean hasNext() {
if (cursor != null&&cursor.next != head) {
data = cursor.data;
cursor = cursor.next;
return true;
}
if (cursor != null) {
data = cursor.data;
cursor = null;
return true;
}
return false;
}
@Override
public T next() {
return data;
}
@Override
public void remove() {
BothwayLoopLinked.this.remove(data);
}
};
}
}到此這篇關于Java實現(xiàn)鏈表數(shù)據(jù)結(jié)構的文章就介紹到這了,更多相關Java鏈表數(shù)據(jù)結(jié)構內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- java數(shù)據(jù)結(jié)構基礎:單鏈表與雙向鏈表
- Java數(shù)據(jù)結(jié)構之順序表和鏈表精解
- Java 數(shù)據(jù)結(jié)構之刪除鏈表中重復的結(jié)點
- 帶你了解Java數(shù)據(jù)結(jié)構和算法之鏈表
- Java 數(shù)據(jù)結(jié)構與算法系列精講之環(huán)形鏈表
- Java?數(shù)據(jù)結(jié)構與算法系列精講之單向鏈表
- Java?精煉解讀數(shù)據(jù)結(jié)構的鏈表的概念與實現(xiàn)
- Java數(shù)據(jù)結(jié)構之雙向鏈表圖解
- Java鏈表數(shù)據(jù)結(jié)構及其簡單使用方法解析
相關文章
這篇文章主要介紹了淺談Java方法調(diào)用的優(yōu)先級問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-10-10
這篇文章主要給大家介紹了關于myBatis組件教程之緩存的實現(xiàn)與使用的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2018-11-11
Swagger是一款RESTful接口的文檔在線自動生成、功能測試功能框架。本文重點給大家介紹springboot項目配置swagger2示例代碼詳解，需要的朋友參考下吧2021-09-09
這篇文章主要介紹了Java 如何獲取url地址文件流，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
裝飾者模式：在不改變原有對象的基礎之上，動態(tài)的將功能附加到對象上，提供了繼承更有彈性的替代方案，也體現(xiàn)了開閉原則。本文將通過示例詳細講解一下裝飾者模式，需要的可以參考一下2022-02-02
這篇文章主要介紹了Java的SPI機制實例詳解的相關資料,需要的朋友可以參考下2017-06-06
ConcurrentHashMap（CHM）是日常開發(fā)中使用頻率非常高的一種數(shù)據(jù)結(jié)構。本文將從源碼角度帶大家深入了解一下ConcurrentHashMap的使用，需要的可以收藏一下2023-05-05
今天小編就為大家分享一篇關于Java壓縮之LZW算法字典壓縮與解壓講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-02-02
這篇文章主要介紹了java 使用正則表達式去除前后空格，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
這篇文章主要介紹了spring單元測試之@RunWith的使用詳解,@RunWith 就是一個運行器,@RunWith(JUnit4.class) 就是指用JUnit4來運行,2023-12-12
@RunWith(SpringJUnit4ClassRunner.class),讓測試運行于Spring測試環(huán)境,需要的朋友可以參考下