Java數(shù)據(jù)結(jié)構(gòu)和算法之鏈表詳解
更新時(shí)間：2024年01月03日 10:48:02 作者：權(quán)sir
鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(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ù)組來存儲(chǔ)元素，由于其底層是一段連續(xù)空間，當(dāng)在ArrayList任意位置插入或者刪除元素時(shí)，就需要將后序元素整體往前或者往后搬移，時(shí)間復(fù)雜度為O(n)，效率比較低，因此ArrayList不適合做任意位置插入和刪除比較多的場景。因此：java集合中又引入了LinkedList，即鏈表結(jié)構(gòu)
一、鏈表的概念及結(jié)構(gòu)
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)存儲(chǔ)結(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)建一個(gè)類：
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) {//走到最后一個(gè)節(jié)點(diǎn)的位置
cur = cur.next;
}
cur.next = node;
}
}
2.5任意位置插入
在任意位置插入時(shí)我們要判斷該位置是否合法，不合法的時(shí)候要拋一個(gè)異常
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)位置的前一個(gè)節(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查找是否包含某個(gè)元素的節(jié)點(diǎn)
遍歷這個(gè)鏈表找是否與這個(gè)元素相同
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)這個(gè)元素的節(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;//沒有要?jiǎng)h除的元素
}
ListNode del = cur.next;
cur.next = del.next;
}
要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(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刪除包含這個(gè)元素的所以節(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));//查看是否包含某個(gè)節(jié)點(diǎn)
System.out.println("*****");
System.out.println(list.size());//求鏈表長度
System.out.println("*****");
list.remove(30);//刪除第一個(gè)出現(xiàn)的節(jié)點(diǎn)
list.display();
list.removeAllKey(30);//刪除包含這個(gè)元素的所以節(jié)點(diǎn)
System.out.println("*****");
list.display();
System.out.println("*****");
list.clear();//清空鏈表
list.display();
}
}
三、雙向不帶頭非循壞鏈表的實(shí)現(xiàn)
創(chuàng)建一個(gè)類：
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) {//一個(gè)節(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) {//一個(gè)節(jié)點(diǎn)都沒有的情況
head = node;
last = node;
}else {
last.next = node;
node.prev = last;
last = node;
}
}
3.5任意位置插入
這里的插入與單向鏈表一樣也需要判斷該位置的合法性，不合法時(shí)拋一個(gè)異常
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查找是否包含某個(gè)元素的節(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)這個(gè)元素的節(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 {
//只有一個(gè)節(jié)點(diǎn)，而且是需要?jiǎng)h除的節(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刪除包含這個(gè)元素的所有節(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 {
//只有一個(gè)節(jié)點(diǎn)，而且是需要?jiǎng)h除的節(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));//查找是否包含某個(gè)元素的節(jié)點(diǎn)
System.out.println("******");
myLinkedList.remove(45);//刪除第一次出現(xiàn)這個(gè)元素的節(jié)點(diǎn)
myLinkedList.display();
System.out.println("******");
myLinkedList.removeAllKey(45);//刪除包含這個(gè)元素的所以節(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是基于動(dòng)態(tài)數(shù)組的，而LinkedList則是基于鏈表的
3.當(dāng)需要隨機(jī)訪問元素（如get和set操作）時(shí)，ArrayList效率更高，因?yàn)長inkedList需要逐個(gè)查找。但當(dāng)進(jìn)行數(shù)據(jù)的增加和刪除操作（如add和remove操作）時(shí)，LinkedList效率更高，因?yàn)锳rrayList在進(jìn)行這些操作時(shí)需要移動(dòng)大量數(shù)據(jù)
4.ArrayList需要手動(dòng)設(shè)置固定大小的容量，使用方便但自由性低；而LinkedList能夠隨數(shù)據(jù)量變化而動(dòng)態(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手動(dòng)實(shí)現(xiàn)常見數(shù)據(jù)結(jié)構(gòu)的示例代碼
相關(guān)文章
這篇文章主要介紹了Springboot使用jsp具體案例解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04
Java對(duì)象深復(fù)制與淺復(fù)制實(shí)例詳解
這篇文章主要介紹了 Java對(duì)象深復(fù)制與淺復(fù)制實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-05-05
這篇文章主要介紹了mybatis中嵌套查詢的使用解讀，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-03-03
這篇文章主要介紹了java中的transient關(guān)鍵字解讀,transient關(guān)鍵字的主要作用就是讓某些被transient關(guān)鍵字修飾的成員屬性變量不被序列化,實(shí)際上也正是因此,在學(xué)習(xí)過程中很少用得上序列化操作,一般都是在實(shí)際開發(fā)中,需要的朋友可以參考下2023-09-09
從原理到最佳實(shí)踐詳解SpringBoot如何實(shí)現(xiàn)優(yōu)雅停機(jī)
優(yōu)雅停機(jī)在現(xiàn)代微服務(wù)架構(gòu)中是非常重要的,它幫助我們確保在應(yīng)用程序停止時(shí),不會(huì)中斷正在進(jìn)行的請求或?qū)е聰?shù)據(jù)丟失,下面我們就來看看SpringBoot實(shí)現(xiàn)優(yōu)雅停機(jī)的具體方法吧2026-03-03
這篇文章主要介紹了java開發(fā)線上事故理解RocketMQ異步精髓2022-07-07
guava是谷歌基于java封裝好的開源庫，這篇文章主要通過介紹幾個(gè)好用的guava工具類，感興趣的朋友可以參考下面文章內(nèi)容2021-09-09
Java AQS中CyclicBarrier回環(huán)柵欄的使用
這篇文章主要介紹了Java中的 CyclicBarrier詳解，CyclicBarrier沒有顯示繼承哪個(gè)父類或者實(shí)現(xiàn)哪個(gè)父接口, 所有AQS和重入鎖不是通過繼承實(shí)現(xiàn)的，而是通過組合實(shí)現(xiàn)的，下文相關(guān)內(nèi)容需要的小伙伴可以參考一下2023-02-02
詳解Intellij IDEA 2017 debug斷點(diǎn)調(diào)試技巧(總結(jié))
這篇文章主要介紹了詳解Intellij IDEA 2017 debug斷點(diǎn)調(diào)試技巧(總結(jié))，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-11-11
SpringCloud消息總線Bus配置中心實(shí)現(xiàn)過程解析
這篇文章主要介紹了SpringCloud消息總線Bus配置中心實(shí)現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03