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