Java數(shù)據(jù)結(jié)構(gòu)之鏈表實(shí)現(xiàn)(單向、雙向鏈表及鏈表反轉(zhuǎn))
前言
之前學(xué)習(xí)的順序表查詢非常快,時(shí)間復(fù)雜度為O(1),但是增刪改效率非常低,因?yàn)槊恳淮卧鰟h改都會(huì)元素的移動(dòng)??梢允褂昧硪环N存儲(chǔ)方式-鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)。鏈表由一序列的結(jié)點(diǎn)(鏈表中的每一個(gè)元素成為結(jié)點(diǎn))組成。
結(jié)點(diǎn)API設(shè)計(jì):
類名 | Node |
構(gòu)造方法 | Node(T t,Node next) 創(chuàng)建Node對(duì)象 |
成員變量 |
T item:存儲(chǔ)數(shù)據(jù) Node next :指向下一個(gè)結(jié)點(diǎn) |
結(jié)點(diǎn)類:
public class Node<T>{ Node next; private T item; public Node(Node next, T item) { this.next = next; this.item = item; } }
生成鏈表:
public class TestNode { public static void main(String[] args) { // 生成結(jié)點(diǎn) Node<Integer> one = new Node<Integer>(null,12); Node<Integer> two = new Node<Integer>(null,16); Node<Integer> three = new Node<Integer>(null,11); Node<Integer> four = new Node<Integer>(null,10); //生成鏈表 one.next = two; two.next = three; three.next =four; } }
1、單鏈表
單向鏈表是鏈表的一種,它有多個(gè)結(jié)點(diǎn)組成,每個(gè)結(jié)點(diǎn)都由一個(gè)數(shù)據(jù)域和一個(gè)指針組成,數(shù)據(jù)域用來存儲(chǔ)數(shù)據(jù),指針域用來指向其后結(jié)點(diǎn)。
鏈表的頭結(jié)點(diǎn)的數(shù)據(jù)域不存儲(chǔ)數(shù)據(jù),指針域指向第一個(gè)真正存儲(chǔ)數(shù)據(jù)的結(jié)點(diǎn)。
單向鏈表API設(shè)計(jì)
類名 | LinkList | ||||||||||||||||
構(gòu)造方法 | LinkList() :創(chuàng)建LinkList對(duì)象 | ||||||||||||||||
成員變量 |
private Node head;記錄首結(jié)點(diǎn) private int N; 記錄鏈表的長度 |
||||||||||||||||
成員內(nèi)部類 | private class Node;結(jié)點(diǎn)類 | ||||||||||||||||
成員方法 |
|
單向鏈表Java代碼實(shí)現(xiàn)
package com.ycy.Algorithm.LinkList; import java.util.Iterator; /** * 鏈表的head是不可以動(dòng)的 * @param <T> */ public class LinkList<T> implements Iterable<T>{ private Node head;//頭結(jié)點(diǎn),鏈表的head是不可以動(dòng)的 private int N;//結(jié)點(diǎn)個(gè)數(shù) public LinkList() { this.head = new Node(null,null); N = 0; } /** * 結(jié)點(diǎn)內(nèi)部類 */ private class Node{ //存儲(chǔ)數(shù)據(jù) T item; //下一個(gè)結(jié)點(diǎn) Node next; public Node(T item,Node next) { this.item = item; this.next = next; } } /** * 清空鏈表 */ public void clear(){ head.item=null; head.next=null;// 頭節(jié)點(diǎn)next為null就是空鏈表 this.N=0; } /** * 判斷鏈表是否為空 */ public boolean isEmpty(){ return this.N==0; } /** * 獲取鏈表的長度 */ public int length(){ return this.N; } /** * 讀取鏈表第i位置的元素值并返回 */ public T get(int i){ //非法性檢查 if(i<0 || i > this.N){ throw new RuntimeException("位置不合法"); } // n也是指向頭結(jié)點(diǎn) Node n = head; for(int index=0; index<i; index++){ n = n.next; } return n.item; } /** * 往鏈表中插入數(shù)據(jù)t */ public void insert(T t){ // head不可以移動(dòng),不然就無法在找到鏈表 // 定義一個(gè)臨時(shí)的Node也指向head的指針就可以通過移動(dòng)該指針就可以 Node n = head; // 獲取尾節(jié)點(diǎn) while(true){ // 當(dāng)剛好就一個(gè)節(jié)點(diǎn)時(shí)(頭節(jié)點(diǎn)) if(n.next == null){ break; } n = n.next; } //當(dāng)為空表時(shí),就可以插入 Node node = new Node(t, null); n.next =node; this.N ++; } /** * 在第i位置上插入數(shù)據(jù)t */ public void insert(T t,int i){ // 非法性檢查 if(i < 0 || i > this.N){ throw new RuntimeException("插入位置❌"); } Node pre = head; for(int index=0;index <= i-1; index++){ pre = pre.next; } Node current = pre.next; //先鏈接后面結(jié)點(diǎn) Node newNode = new Node(t,null); pre.next = newNode; newNode.next = current; this.N++; } /** * 移除并返回第i位置的元素值 */ public T remove(int i){ // 非法性檢查 if(i < 0 || i >this.N){ throw new RuntimeException("刪除位置有誤"); } Node n =head; for(int index=0;index <= i-1;index ++){ n = n.next; } //要?jiǎng)h除的節(jié)點(diǎn) Node curr = n.next; n.next = curr.next; this.N--;//結(jié)點(diǎn)個(gè)數(shù)減一 return curr.item; } //查找元素t在鏈表中第一次出現(xiàn)的位置 public int indexof(T t){ Node n = head; for(int i = 0; n.next != null;i++){ n =n.next; if(n.item.equals(t)){ return i; } } return -1; } @Override public Iterator iterator() { return new Iterator() { Node n =head; @Override public boolean hasNext() { return n.next !=null; } @Override public Object next() { //下移一個(gè)指針 n = n.next; return n.item; } }; } }
補(bǔ)充一點(diǎn):鏈表的賦值給新的鏈表后,兩個(gè)鏈表是會(huì)相會(huì)影響的,說白了就是把地址賦值給它了,他們操作是同一塊內(nèi)存的同一個(gè)對(duì)象。Node n = head;把head賦值給n,現(xiàn)在對(duì)n操作也是會(huì)影響head的
其中提供遍歷方式,實(shí)現(xiàn)Iterable接口。
測試代碼:
public class test { public static void main(String[] args) { LinkList<Integer>linkList = new LinkList<>(); linkList.insert(1); linkList.insert(2); linkList.insert(4); linkList.insert(3); linkList.insert(1,2); for (Integer i : linkList) { System.out.print(i+" "); } } }
運(yùn)行結(jié)果:
D:\Java\jdk-12.0.2\bin\java.exe "-javaagent:D:\IDEA\IntelliJ IDEA 2019.1\lib\idea_rt.jar=3542:D:\IDEA\IntelliJ IDEA 2019.1
1 2 1 4 3
學(xué)習(xí)完鏈表還是需要加以練習(xí)的,可以在LeetCode上刷題加深理解。
2、雙向鏈表
頭插法:新增節(jié)點(diǎn)總是插在頭部
便于理解可以畫圖表示
頭插法:原圖,node是待插入的結(jié)點(diǎn).
插入后圖:
關(guān)鍵性代碼:
尾插法:新增節(jié)點(diǎn)總是插在尾部
原圖如下:
插入結(jié)點(diǎn)后圖如下:
關(guān)鍵性代碼:
中間任意位置插入
插入之前的原圖:
插入到鏈表中間位置:
關(guān)鍵性代碼:
代碼演示:
class MyLinkedList { Node head;//定義雙向鏈表的頭節(jié)點(diǎn) Node last;//定義雙向鏈表的尾節(jié)點(diǎn) //打印雙向鏈表 public void disPlay() { Node cur = this.head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } //求雙向鏈表的長度(之后addIndex代碼會(huì)用到) public int size() { int count = 0; Node cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; } //頭插法 public void addFirst(int data) { Node node = new Node(data);//定義一個(gè)用作插入的節(jié)點(diǎn) //1.假設(shè)雙向鏈表為空 if (this.head == null) { this.head = node; this.last = node; } else { //2.雙向鏈表不為空的情況下 //不懂請(qǐng)看上面的圖解,就很簡單了 node.next = this.head; this.head.prev = node; this.head = node; } } //尾插法(與頭插法類似) public void addLast(int data) { //定義一個(gè)用作插入的節(jié)點(diǎn) Node node = new Node(data); //1.假設(shè)雙向鏈表為空 if (this.head == null) { this.head = node; this.last = node; } else { //2.雙向鏈表不為空的情況下 //不懂請(qǐng)看上面的圖解,就很簡單了 last.next = node; node.prev = last; last = node; } } //在任意位置插入 public void addIndex(int index, int data) {//形參index為插入元素位置,data為插入的數(shù)值 //定義一個(gè)用作插入的節(jié)點(diǎn) Node node = new Node(data); Node cur = this.head;//定義一個(gè)cur用作遍歷雙向鏈表 //1、判斷插入位置的合法性 if (index < 0 || index > size()) { System.out.println("插入位置不合法!??!"); return; } //2、假設(shè)插入位置為頭結(jié)點(diǎn)的情況下,即就是頭插法 if (index == 0) { addFirst(data);//調(diào)用頭插法代碼 return; } //3、假設(shè)插入位置為尾結(jié)點(diǎn)的情況下,即就是尾插法 if (index == size()) { addLast(data);//調(diào)用尾插法代碼 return; } //4、在中間任意位置的情況下 while (index != 0) { cur = cur.next; index--; } //不懂請(qǐng)看上面的圖解,就很簡單了 //核心代碼 node.next = cur; node.prev = cur.prev; cur.prev = node; node.prev.next = node; } } //雙向鏈表的節(jié)點(diǎn)結(jié)構(gòu) class Node { int val; Node prev; Node next; Node(int val) { this.val = val; } }
3、鏈表反轉(zhuǎn)
public void reverse(){ if(N==0){ //當(dāng)前是空鏈表,不需要反轉(zhuǎn) return; } reverse(head.next); } /** * @param curr 當(dāng)前遍歷的結(jié)點(diǎn) * @return 反轉(zhuǎn)后當(dāng)前結(jié)點(diǎn)上一個(gè)結(jié)點(diǎn) */ public Node reverse(Node curr){ //已經(jīng)到了最后一個(gè)元素 if(curr.next==null){ //反轉(zhuǎn)后,頭結(jié)點(diǎn)應(yīng)該指向原鏈表中的最后一個(gè)元素 head.next=curr; return curr; } //當(dāng)前結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn) Node pre=reverse(curr.next); pre.next=curr; //當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)設(shè)為null curr.next=null; //返回當(dāng)前結(jié)點(diǎn) return curr; }
總結(jié)
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之鏈表實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java數(shù)據(jù)結(jié)構(gòu)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- Java數(shù)據(jù)結(jié)構(gòu)與算法之雙向鏈表、環(huán)形鏈表及約瑟夫問題深入理解
- java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ):單鏈表與雙向鏈表
- java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ):單,雙向鏈表
- Java雙向鏈表按照順序添加節(jié)點(diǎn)的方法實(shí)例
- Java實(shí)現(xiàn)雙向循環(huán)鏈表
- Java雙向鏈表倒置功能實(shí)現(xiàn)過程解析
- JAVA實(shí)現(xiàn)雙向鏈表的增刪功能的方法
- java基于雙向環(huán)形鏈表解決丟手帕問題的方法示例
- Java中雙向鏈表詳解及實(shí)例
- Java如何實(shí)現(xiàn)雙向鏈表功能
相關(guān)文章
解決IDEA報(bào)錯(cuò)war?exploded?is?not?valid問題
在使用IntelliJ?IDEA時(shí)遇到'[projectname]warexploded'無效的問題,可以通過清除項(xiàng)目列表、重新導(dǎo)入項(xiàng)目和配置新的Tomcat來解決,確保在Tomcat配置中,將ApplicationContext修改為僅包含一個(gè)'/',這一方法或許能幫助遇到相似問題的開發(fā)者2024-09-09Springboot+echarts實(shí)現(xiàn)可視化
這篇文章主要為大家詳細(xì)介紹了Springboot+echarts實(shí)現(xiàn)可視化,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-12-12Java的Hibernate框架中集合類數(shù)據(jù)結(jié)構(gòu)的映射編寫教程
Hibernate可以將Java中幾個(gè)內(nèi)置的集合結(jié)構(gòu)映射為數(shù)據(jù)庫使用的關(guān)系模型,下面我們就來看一下Java的Hibernate框架中集合類數(shù)據(jù)結(jié)構(gòu)的映射編寫教程:2016-07-07解決springboot項(xiàng)目啟動(dòng)報(bào)錯(cuò)Error creating bean with&nb
這篇文章主要介紹了解決springboot項(xiàng)目啟動(dòng)報(bào)錯(cuò)Error creating bean with name dataSourceScriptDatabaseInitializer問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助2024-03-03MyBatis一對(duì)一級(jí)聯(lián)更新問題小結(jié)
日常工作中經(jīng)常會(huì)涉及到一對(duì)一級(jí)聯(lián)更新的問題,本文主要介紹了MyBatis一對(duì)一級(jí)聯(lián)更新問題小結(jié),具有一定的參考價(jià)值,感興趣的可以了解一下2024-01-01