Java數(shù)據(jù)結(jié)構(gòu)和算法之鏈表詳解
更新時間：2024年01月03日 10:48:02 作者：權(quán)sir
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu),java代碼實(shí)現(xiàn)單鏈表,插入,刪除和遍歷等功能,這篇文章主要給大家介紹了關(guān)于Java數(shù)據(jù)結(jié)構(gòu)和算法之鏈表的相關(guān)資料,需要的朋友可以參考下
前言
在前面我們已經(jīng)學(xué)習(xí)了關(guān)于順序表ArrayList的一些基本操作。通過源碼知道，ArrayList底層使用數(shù)組來存儲元素，由于其底層是一段連續(xù)空間，當(dāng)在ArrayList任意位置插入或者刪除元素時，就需要將后序元素整體往前或者往后搬移，時間復(fù)雜度為O(n)，效率比較低，因此ArrayList不適合做任意位置插入和刪除比較多的場景。因此：java集合中又引入了LinkedList，即鏈表結(jié)構(gòu)
一、鏈表的概念及結(jié)構(gòu)
鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用鏈接次序?qū)崿F(xiàn)的
注意：
1.鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定連續(xù)
2.現(xiàn)實(shí)中的結(jié)點(diǎn)一般都是從堆上申請出來的
3.從堆上申請的空間，是按照一定的策略來分配的，兩次申請的空間可能是連續(xù)，也可能不連續(xù)
鏈表的結(jié)構(gòu)有8種樣式：
- 單向帶頭循壞、單向帶頭非循壞、單向不帶頭循壞、單向不帶頭非循壞
- 雙向帶頭循壞、雙向帶頭非循壞、雙向不帶頭循壞、雙向不帶頭非循壞
這里我們主要學(xué)習(xí)以下兩中結(jié)構(gòu)：
單向不帶頭非循壞
LinkedList底層使用的就是雙向不帶頭非循壞
二、單向不帶頭非循壞鏈表的實(shí)現(xiàn)
創(chuàng)建一個類：
public class MySingleList {
static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
//鏈表的頭節(jié)點(diǎn)
public ListNode head;
}
2.1打印鏈表
不帶參數(shù)的打印
public void display() {
ListNode cur = head;
if(cur != null) {//遍歷完所以節(jié)點(diǎn)
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
帶參數(shù)的打印
public void display(ListNode newHead) {
ListNode cur = newHead;
if(cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
2.2求鏈表的長度
public int size(){
ListNode cur = head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
2.3頭插法
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
2.4尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
head = node;
}else {
ListNode cur = head;
while (cur.next != null) {//走到最后一個節(jié)點(diǎn)的位置
cur = cur.next;
}
cur.next = node;
}
}
2.5任意位置插入
在任意位置插入時我們要判斷該位置是否合法，不合法的時候要拋一個異常
public void addIndex(int index,int data){
if(index < 0 || index > size()) {
throw new IndexException("index位置不合法："+index);
}
ListNode node = new ListNode(data);
if(head == null) {
head = node;
return;
}
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
//中間插入
ListNode cur = serchIndex(index);
node.next = cur.next;
cur.next = node;
}
找要添加節(jié)點(diǎn)位置的前一個節(jié)點(diǎn)
public ListNode serchIndex(int index) {
ListNode cur = head;
int count = 0;
while (count != index-1) {
cur = cur.next;
count++;
}
return cur;
}
2.6查找是否包含某個元素的節(jié)點(diǎn)
遍歷這個鏈表找是否與這個元素相同
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
2.7刪除第一次出現(xiàn)這個元素的節(jié)點(diǎn)
public void remove(int key){
if(head == null) {
return;
}
if(head.val == key) {
head = head.next;
return;
}
ListNode cur = findKey(key);
if(cur == null) {
return;//沒有要刪除的元素
}
ListNode del = cur.next;
cur.next = del.next;
}
要刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn)
public ListNode findKey(int key) {
ListNode cur = head;
while (cur.next != null) {
if(cur.next.val == key) {
return cur;
}else {
cur = cur.next;
}
}
return null;
}
2.8刪除包含這個元素的所以節(jié)點(diǎn)
public void removeAllKey(int key){
if(head == null) {
return;
}
ListNode prev = head;
ListNode cur = head.next;
while (cur != null){
if(cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
//除了頭節(jié)點(diǎn)外，其余都刪完了
if(head.val == key) {
head = head.next;
}
}
2.9清空鏈表
清空鏈表只需要把頭節(jié)點(diǎn)置為空
public void clear() {
head = null;
}
單向鏈表的測試
public class Test {
public static void main(String[] args) {
MySingleList list = new MySingleList();
list.addLast(30);//尾插
list.addLast(20);
list.addLast(30);
list.addLast(40);
list.addLast(50);
list.addFirst(100);//頭插
list.addIndex(2,15);//任意位置插入
list.display();
System.out.println("*****");
System.out.println(list.contains(20));//查看是否包含某個節(jié)點(diǎn)
System.out.println("*****");
System.out.println(list.size());//求鏈表長度
System.out.println("*****");
list.remove(30);//刪除第一個出現(xiàn)的節(jié)點(diǎn)
list.display();
list.removeAllKey(30);//刪除包含這個元素的所以節(jié)點(diǎn)
System.out.println("*****");
list.display();
System.out.println("*****");
list.clear();//清空鏈表
list.display();
}
}
三、雙向不帶頭非循壞鏈表的實(shí)現(xiàn)
創(chuàng)建一個類：
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.1打印雙向鏈表
public void display(){
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
3.2求雙向鏈表的長度
public int size(){
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
3.3頭插法
public void addFist(int data) {
ListNode node = new ListNode(data);
if(head == null) {//一個節(jié)點(diǎn)都沒有的情況
head = node;
last = node;
}else {
node.next = head;
head.prev = node;
head = node;
}
}
3.4尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if(head == null) {//一個節(jié)點(diǎn)都沒有的情況
head = node;
last = node;
}else {
last.next = node;
node.prev = last;
last = node;
}
}
3.5任意位置插入
這里的插入與單向鏈表一樣也需要判斷該位置的合法性，不合法時拋一個異常
public void addIndex(int index,int data) {
if(index < 0 || index > size()) {
throw new IndexException("雙向鏈表中index的位置不合法："+index);
}
if(index == 0) {
addFist(data);
}
if(index == size()) {
addLast(data);
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
要添加節(jié)點(diǎn)的位置
public ListNode findIndex(int index) {
ListNode cur = head;
if(index != 0) {
cur = cur.next;
index --;
}
return cur;
}
3.6查找是否包含某個元素的節(jié)點(diǎn)
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
3.7刪除第一次出現(xiàn)這個元素的節(jié)點(diǎn)
因?yàn)閿?shù)據(jù)結(jié)構(gòu)是一門邏輯性非常嚴(yán)謹(jǐn)?shù)膶W(xué)科，所以這里的刪除需要考慮多種因素
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 {
//只有一個節(jié)點(diǎn)，而且是需要刪除的節(jié)點(diǎn)
last = null;
}
}else {
//刪除中間節(jié)點(diǎn)
if(cur.next != null) {
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}else {
//刪除尾巴節(jié)點(diǎn)
cur.prev.next = cur.next;
last = last.prev;
}
}
return;
}
cur = cur.next;
}
}
3.7刪除包含這個元素的所有節(jié)點(diǎn)
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 {
//只有一個節(jié)點(diǎn)，而且是需要刪除的節(jié)點(diǎn)
last = null;
}
}else {
//刪除中間節(jié)點(diǎn)
if(cur.next != null) {
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}else {
//刪除尾巴節(jié)點(diǎn)
cur.prev.next = cur.next;
last = last.prev;
}
}
}
cur = cur.next;
}
}
3.9清空雙向鏈表
public void clear(){
ListNode cur = head;
while (cur != null) {
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = cur.next;
}
head = null;//頭節(jié)點(diǎn)置空
last = null;//尾巴節(jié)點(diǎn)置空
}
雙向鏈表的測試
public class Test {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(12);//尾插法
myLinkedList.addLast(45);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
myLinkedList.addFist(56);//頭插法
myLinkedList.addIndex(2,15);//任意位置插入
myLinkedList.display();
System.out.println(myLinkedList.size());//求雙向鏈表的長度
System.out.println("******");
System.out.println(myLinkedList.contains(23));//查找是否包含某個元素的節(jié)點(diǎn)
System.out.println("******");
myLinkedList.remove(45);//刪除第一次出現(xiàn)這個元素的節(jié)點(diǎn)
myLinkedList.display();
System.out.println("******");
myLinkedList.removeAllKey(45);//刪除包含這個元素的所以節(jié)點(diǎn)
myLinkedList.display();
System.out.println("******");
myLinkedList.clear();//清空鏈表
myLinkedList.display();
}
}
LinkedList的遍歷方式
關(guān)于LinkedList的遍歷方式有四種：
public class Test {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list);
//for循壞遍歷
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+" ");
}
System.out.println();
System.out.println("*******");
//foreach遍歷
for (int m : list) {
System.out.print(m +" ");
}
System.out.println();
System.out.println("*******");
//使用迭代器——正向遍歷
ListIterator<Integer> it = list.listIterator();
while (it.hasNext()) {
System.out.print(it.next()+" ");
}
System.out.println();
System.out.println("*******");
//使用迭代器——反向遍歷
ListIterator<Integer> it2 = list.listIterator(list.size());
while (it2.hasPrevious()) {
System.out.print(it2.previous()+" ");
}
System.out.println();
}
}
四、ArrayList和LinkedList的區(qū)別
1.ArrayList在物理上是連續(xù)的，LinkedList在邏輯上連續(xù)，但在物理上不一定連續(xù)
2.ArrayList和LinkedList是兩種不同的數(shù)據(jù)結(jié)構(gòu)。ArrayList是基于動態(tài)數(shù)組的，而LinkedList則是基于鏈表的
3.當(dāng)需要隨機(jī)訪問元素（如get和set操作）時，ArrayList效率更高，因?yàn)長inkedList需要逐個查找。但當(dāng)進(jìn)行數(shù)據(jù)的增加和刪除操作（如add和remove操作）時，LinkedList效率更高，因?yàn)锳rrayList在進(jìn)行這些操作時需要移動大量數(shù)據(jù)
4.ArrayList需要手動設(shè)置固定大小的容量，使用方便但自由性低；而LinkedList能夠隨數(shù)據(jù)量變化而動態(tài)調(diào)整，自由性較高但使用較為復(fù)雜
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)和算法之鏈表的文章就介紹到這了,更多相關(guān)Java鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- Java數(shù)據(jù)結(jié)構(gòu)之紅黑樹的實(shí)現(xiàn)方法和原理詳解
- Java數(shù)據(jù)結(jié)構(gòu)中七種排序算法實(shí)現(xiàn)詳解
- Java數(shù)據(jù)結(jié)構(gòu)中關(guān)于AVL樹的實(shí)現(xiàn)方法詳解
- Java數(shù)據(jù)結(jié)構(gòu)篇之實(shí)現(xiàn)二叉搜索樹的核心方法
- Java數(shù)據(jù)結(jié)構(gòu)與算法之二分查找詳解
- Java數(shù)據(jù)結(jié)構(gòu)中的HashMap和HashSet詳解
- Java常見的數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列詳解
- java手動實(shí)現(xiàn)常見數(shù)據(jù)結(jié)構(gòu)的示例代碼
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于java高并發(fā)進(jìn)程和線程的內(nèi)容，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用java具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2021-10-10
Spring Boot2.0實(shí)現(xiàn)靜態(tài)資源版本控制詳解
這篇文章主要給大家介紹了關(guān)于Spring Boot2.0實(shí)現(xiàn)靜態(tài)資源版本控制的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-11-11
CompletableFuture并行處理List分批數(shù)據(jù)demo
這篇文章主要介紹了CompletableFuture并行處理List分批數(shù)據(jù)實(shí)現(xiàn)實(shí)例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-11-11
Spring boot如何快速的配置多個Redis數(shù)據(jù)源
這篇文章主要介紹了Spring boot如何快速的配置多個Redis數(shù)據(jù)源，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06
這篇文章主要介紹了java如何獲取實(shí)體類的屬性名和屬性值問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-11-11
這篇文章主要介紹了使用Maven Helper解決Maven插件沖突的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-12-12
springboot讀取.properties配置文件中的map和list類型配置參數(shù)方式
這篇文章主要介紹了springboot讀取.properties配置文件中的map和list類型配置參數(shù)方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-03-03
Java 中函數(shù) Function 的使用和定義示例小結(jié)
這篇文章主要介紹了Java 中函數(shù) Function 的使用和定義小結(jié),本文通過實(shí)例代碼給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2024-07-07
MD5 是 Message Digest Algorithm 的縮寫，譯為信息摘要算法，它是 Java 語言中使用很廣泛的一種加密算法。本文將通過示例討論下MD5的安全性，感興趣的可以了解一下2022-10-10
這篇文章主要介紹了Java如何獲取JSON中某個對象的值，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06