Java數(shù)據(jù)結(jié)構(gòu)之鏈表的增刪查改詳解
一. 概念與結(jié)構(gòu)
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的引用鏈接次序?qū)崿F(xiàn)的 。
雖然有這么多的鏈表的結(jié)構(gòu),但是我們重點(diǎn)掌握兩種:
1.無(wú)頭單向非循環(huán)鏈表:結(jié)構(gòu)簡(jiǎn)單,一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu),如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
2.無(wú)頭雙向鏈表:在Java的集合框架庫(kù)中LinkedList底層實(shí)現(xiàn)就是無(wú)頭雙向循環(huán)鏈表。
二.單鏈表接口實(shí)現(xiàn)
接下來(lái)新一帶大家寫無(wú)頭單向非循環(huán)鏈表
import java.util.List; /** * Created with IntelliJ IDEA. * Description: 鏈表 * User: mac * Date: 2022-08-31 * Time: 10:09 */ //ListNode代表一個(gè)節(jié)點(diǎn) - 存放在一個(gè)節(jié)點(diǎn)類中 class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val = val; } } public class MyLinkedList { public ListNode head;//鏈表的頭引用 //打印鏈表 public void display() { //this.head.next != null 會(huì)丟失一個(gè)數(shù)據(jù) ListNode cur = this.head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } //查找是否包含關(guān)鍵字k public boolean contains(int key) { ListNode cur = this.head; while (cur != null) { if (cur.val == key) { return true; } cur = cur.next; } return false; } //得到單鏈表的長(zhǎng)度 public int size() { int count = 0; ListNode cur = this.head; while (cur != null) { count++; cur = cur.next; } return count; } //頭插法 public void addFirst(int data){ //綁定位置的時(shí)候一定要先綁定后邊 ListNode node = new ListNode(data); node.next = this.head; this.head = node; } //尾插法 public void addLast(int data){ ListNode node = new ListNode(data); if (this.head == null){//判空,否則就會(huì)造成引用異常this.head.next this.head = node; } else { ListNode cur = this.head; while (cur.next != null){ cur = cur.next; } //cur.next = null; cur.next = node; } } public ListNode findindex(int index){//通過(guò)下表來(lái)移動(dòng)指針 ListNode cur = this.head; while (index - 1 != 0){ cur = cur.next; index--; } return cur; } //任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo) public void addIndex(int index, int data){ if (index < 0 || index > size()){ System.out.println("index位置不合法!"); return; } if (index == 0){ addFirst(data); return; } if (index == size()){ addLast(data); return; } ListNode cur = findindex(index); ListNode node = new ListNode(data); node.next = cur.next; cur.next = node; } //刪除第一次出現(xiàn)的關(guān)鍵字為key的節(jié)點(diǎn) public void remove(int key){ if (this.head == null){ System.out.println("單鏈表為空,不能刪除!"); return; } if (this.head.val == key){//判斷頭部是否為目標(biāo)節(jié)點(diǎn) this.head = this.head.next; return; } ListNode cur = this.head; while (cur.next != null){ if (cur.next.val == key){ cur.next = cur.next.next; return; } cur = cur.next; } System.out.println("未找到該節(jié)點(diǎn)"); } //刪除所有值為key的節(jié)點(diǎn) public ListNode removeAllKey(int key){ if (this.head == null) return null; ListNode prev = this.head; ListNode cur = this.head.next; while (cur != null){ if (cur.val == key){ prev.next = cur.next; cur = cur.next; } else{ prev = cur; cur = cur.next; } } //最后處理頭 if (this.head.val == key){ this.head = this.head.next; } return this.head; } //清空鏈表 public void clear(){ //this.head = null;//暴力解決 - 不推薦但沒(méi)毛病 while (this.head != null){ ListNode curNext = this.head.next; this.head.next = null; this.head = curNext; } } }
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之鏈表的增刪查改詳解的文章就介紹到這了,更多相關(guān)Java鏈表增刪查改內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java?Map接口子類HashMap遍歷與LinkedHashMap詳解
這篇文章主要介紹了java?Map接口子類HashMap遍歷與LinkedHashMap詳解,Map接口下的集合與Collection接口下的集合,它們存儲(chǔ)數(shù)據(jù)的形式不同,感興趣的小伙伴可以參考下面文章詳細(xì)內(nèi)容介紹2022-06-06SpringBoot實(shí)現(xiàn)過(guò)濾器攔截器的耗時(shí)對(duì)比
這篇文章主要為大家詳細(xì)介紹了SpringBoot實(shí)現(xiàn)過(guò)濾器攔截器的輸出接口耗時(shí)對(duì)比,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2022-06-06Mybatis詳細(xì)對(duì)比一級(jí)緩存與二級(jí)緩存
MyBatis 包含一個(gè)非常強(qiáng)大的查詢緩存特性,它可以非常方便地配置和定制,緩存可以極大的提升查詢效率。MyBatis中默認(rèn)定義了兩級(jí)緩存,分別是一級(jí)緩存和二級(jí)緩存2022-10-10Java實(shí)現(xiàn)簡(jiǎn)單的彈球游戲
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)簡(jiǎn)單的彈球游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-12-12Java中List根據(jù)map的某個(gè)key去重的代碼
今天小編就為大家分享一篇關(guān)于Java中List根據(jù)map的某個(gè)key去重的代碼,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧2018-12-12