Java?精煉解讀數(shù)據(jù)結(jié)構的鏈表的概念與實現(xiàn)
更新時間：2022年03月14日 16:08:07 作者：K媾?
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針連接次序?qū)崿F(xiàn)的，每一個鏈表都包含多個節(jié)點，節(jié)點又包含兩個部分，一個是數(shù)據(jù)域，一個是引用域
前言：
順序表的問題及思考
1. 順序表中間/頭部的插入刪除，時間復雜度為O(N)
2. 增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗。
3. 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續(xù) 插入了5個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費了95個數(shù)據(jù)空間。
思考： 如何解決以上問題呢？下面給出了鏈表的結(jié)構來看看。
一、什么是鏈表
鏈表的概念
鏈表是一種物理存儲結(jié)構上非連續(xù)存儲結(jié)構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用鏈接次序?qū)崿F(xiàn)的 。
鏈表的結(jié)構
鏈表結(jié)構分為8種：
這里我們只講最下面兩種，因為在工作中、業(yè)務里、考試題、刷到的鏈表題、面試題里面都是用到這兩種鏈表。?
鏈表如何存儲數(shù)據(jù)
鏈表是由一個一個節(jié)點組成的。(這里我們以單鏈表為例)
什么叫做節(jié)點？
節(jié)點分為兩個域 ,假設一個叫做val域，一個叫做next域。
val：數(shù)據(jù)域
next：下一個節(jié)點的地址
鏈表的實現(xiàn)??
//ListNode代表一個節(jié)點
class ListNode{
public int val;
public ListNode next;
//構造方法
public ListNode(int val){
this.val = val;
}
}
//MyLinkedList 代表這是一個鏈表
public class MyLinkedList {
public ListNode head;//鏈表的頭引用，所以定義在鏈表里，head是鏈表的頭，不是節(jié)點的頭，節(jié)點只有兩個屬性，一個屬性是val值，一個屬性是next值，所以不能定義在ListNode類里面
ListNode listNode = new ListNode(2);//節(jié)點實例化，val域賦值為2
}
窮舉法創(chuàng)建鏈表
/MyLinkedList 代表這是一個鏈表
public class MyLinkedList {
public ListNode head;//鏈表的頭引用，所以定義在鏈表里
public void createList(){
ListNode listNode0 = new ListNode(11);
ListNode listNode1 = new ListNode(26);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(45);
ListNode listNode4 = new ListNode(56);
listNode0.next = listNode1;
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
this.head = listNode0;
}
打印鏈表
//打印鏈表
public void display(){
ListNode cur = this.head;
while (cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
打印結(jié)果：
查找是否包含關鍵字key是否在單鏈表當中?
//查找是否包含關鍵字key是否在單鏈表當中
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
打印結(jié)果：
得到單鏈表的長度：
//得到單鏈表的長度
public int size(){
ListNode cur = this.head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
?打印結(jié)果：
頭插法
//頭插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
} else {
node.next = this.head;
head = node;
}
}
打印結(jié)果：
尾插法
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
ListNode cur = this.head;
if(this.head == null){
this.head = node;
}else {
while(cur.next != null){
cur = cur.next;
}
cur.next = node;
}
}
打印結(jié)果：
任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標
public ListNode findIndex(int index){
ListNode cur = this.head;
while(index -1 != 0){
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標
public void addIndex(int index,int data){
if(index < 0 || index > size()){
System.out.println("位置不合法");
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;
}
打印結(jié)果：
刪除第一次出現(xiàn)關鍵字為key的節(jié)點
//刪除第一次出現(xiàn)關鍵字為key的節(jié)點
public void remove(int key){
if(this.head == null){
System.out.println("沒有你要刪除的節(jié)");
return;
}
if (this.head.val == key){
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;
}
if(cur.next == null){
System.out.println("沒有該節(jié)點");
return;
}
}
打印結(jié)果：
刪除所有值為key的節(jié)點
//刪除所有值為key的節(jié)點
public ListNode removeAllKey(int key){
if(this.head == null) return null;
ListNode prev = this.head;
ListNode cur = this.head;
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;
}
打印結(jié)果：
總結(jié)：
本文簡單介紹了數(shù)據(jù)結(jié)構的鏈表，如何創(chuàng)建鏈表，鏈表上如何操作數(shù)據(jù)。通過簡單例題的方式加深對順序表的理解。上述就是今天的內(nèi)容，有任何疑問的話可以隨時私信我，文章哪里出現(xiàn)了問題我都會積極改正，也希望大家能更快的掌握自己想要的知識，讓我們一起加油！?。。。?/p>
到此這篇關于Java?精煉解讀數(shù)據(jù)結(jié)構的鏈表的概念與實現(xiàn)的文章就介紹到這了,更多相關Java 數(shù)據(jù)結(jié)構的鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- java數(shù)據(jù)結(jié)構基礎:單鏈表與雙向鏈表
- Java數(shù)據(jù)結(jié)構之順序表和鏈表精解
- Java 數(shù)據(jù)結(jié)構之刪除鏈表中重復的結(jié)點
- Java實現(xiàn)鏈表數(shù)據(jù)結(jié)構的方法
- 帶你了解Java數(shù)據(jù)結(jié)構和算法之鏈表
- Java 數(shù)據(jù)結(jié)構與算法系列精講之環(huán)形鏈表
- Java?數(shù)據(jù)結(jié)構與算法系列精講之單向鏈表
- Java數(shù)據(jù)結(jié)構之雙向鏈表圖解
- Java鏈表數(shù)據(jù)結(jié)構及其簡單使用方法解析
相關文章
這篇文章主要為大家詳細介紹了Java+OpenCV實現(xiàn)人臉檢測，并調(diào)用筆記本攝像頭實時抓拍，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-07-07
在類中沒有包含足夠的信息來描繪一個具體的對象，這樣的類稱為抽象類，接口是Java中最重要的概念之一，它可以被理解為一種特殊的類，不同的是接口的成員沒有執(zhí)行體，是由全局常量和公共的抽象方法所組成，本文給大家介紹Java抽象類和接口，感興趣的朋友一起看看吧2022-04-04
springboot集成opencv實現(xiàn)人臉識別功能的詳細步驟
大家都知道OpenCV是一個基于BSD許可（開源）發(fā)行的跨平臺計算機視覺和機器學習軟件庫，可以運行在Linux、Windows、Android和Mac OS操作系統(tǒng)上今天通過本文給大家分享springboot集成opencv實現(xiàn)人臉識別，感興趣的朋友一起看看吧2021-06-06
這篇文章主要介紹了一文詳解Spring是怎么讀取配置Xml文件的，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，感興趣的小伙伴可以參考一下2022-08-08
這篇文章主要為大家介紹了Java根據(jù)ip地址獲取歸屬地實例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
這篇文章主要給大家介紹了關于spring boot與ktor整合的實現(xiàn)方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-09-09
這篇文章主要介紹了單元測試 @mock與@SpringBootTest的使用方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-10-10
Java爬蟲Jsoup+httpclient獲取動態(tài)生成的數(shù)據(jù)
這篇文章主要介紹了Java爬蟲Jsoup+httpclient獲取動態(tài)生成的數(shù)據(jù)的相關資料,需要的朋友可以參考下2017-05-05
SchedulingConfigurer實現(xiàn)動態(tài)定時,導致ApplicationRunner無效解決
這篇文章主要介紹了SchedulingConfigurer實現(xiàn)動態(tài)定時,導致ApplicationRunner無效的解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-05-05
這篇文章主要介紹了Mybatis查詢多條記錄并返回List集合的方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-09-09