單向鏈表結構

?鏈表結構簡介

? ? ? ? 鏈表結構是一種用比較特殊的數據結構類型,它也是線性數據結構中的一種,但是與棧結構等線性數據結構不同,它的內部結構并不是一個簡單的存儲空間,而是一個帶有指向性質的單元。要理解鏈表結構要弄清楚兩個問題,第一個就是鏈表結構的存儲方式是怎樣的,第二個就是鏈表結構的模型該如何描述。

? ? ? ? 先說第一個問題,鏈表結構的存儲方式。鏈表結構對數據存儲的時候并不是簡單的將這個數據存放到一個指定的空間中,而是將數據存儲到一個屬于鏈表結構的節點當中。這個節點就是鏈表的一個組成部分,在這個節點中,不僅存儲了這個元素還存儲了下一個元素或者上一個元素的地址,通過這些儲存的地址就可以找到當前元素的上一個元素或者下一個元素。

? ? ? ? 了解完鏈表結構的存儲方式,那么鏈表結構的模型就比較好建立了。最簡單的模型就是鏈子,不論是鐵鏈還是狗鏈都能幫助我們理解鏈表結構。因為鏈表結構就相當于是用一根無形的繩子將內存中的數據串了起來,就像是一根鏈子一樣,所以稱之為鏈表結構。但是要注意的是,雖然我們可以將鏈表結構想象成一根鐵鏈,但是在實際內存中,鏈表結構中相鄰的兩個元素在內存中并不是相鄰的。只是通過上一個節點中存儲的地址能找到下一個節點中存儲的元素而已。

? ? ? ? 綜上,鏈表結構是由許多節點組成的,每一個節點中都應包含數據部分和地址部分兩個部分。其中數據部分用來存儲該節點的實際數據,而地址部分用來存儲上一個或者下一個節點的地址。

? ? ? ? 鏈表結構可以分為單向鏈表、雙向鏈表和雙向循環鏈表三種,其中單向鏈表和雙向鏈表是比較常見的鏈表結構,雙向循環鏈表不太常見,簡單了解即可。

單向鏈表

? ? ? ? 單向鏈表是鏈表結構中最為簡單的一類,它的特點是鏈表中節點的鏈接方向是單向的,也就是說訪問鏈表中的元素時只能從頭開始一個一個的尋找,不能直接鎖定指定元素的位置,也不能從尾向前訪問元素。故能夠判斷出單向鏈表的結構中節點存儲的內容應該為節點存儲的元素以及下一個節點的地址。

? ? ? ? 了解了單向鏈表的結構以及存儲模式,就可以創建單向鏈表的具體對象了。目前,在java中是找不到一個合適的結構來描述鏈表結構的,因此需要自行創建鏈表實現類。考慮到單向鏈表和雙向鏈表的除了在存儲結構上純在些許差異之外其余并無太多不同,并且它們都應該具有對內部儲存元素進行操作的方法,因此為了提高代碼的復用性,可以將鏈表結構中的方法抽象出來創建一個接口,這樣在實現單向鏈表或者雙向鏈表類的時候只需要實現接口中的方法就能夠實現對應的操作方法了。大大降低了代碼的復雜程度。根據鏈表結構中應該具備的操作元素的方法,創建了以下接口:

package com.data.demo;/*** 基于鏈表結構存取元素的API定義* @param <E>*/public interface MyList <E>{void add (E element);E get (int index);int size();E remove(int index);
}

此接口中定義了四個抽象方法,對應了添加元素、獲取元素、獲取元素個數以及刪除元素四個功能。

? ? ? ? 創建完鏈表結構的接口類,就可以創建一個單向鏈表類來實現這個接口類了。由于向單向鏈表中添加元素之前并不能確定添加的元素類型,因此定義的單向鏈表類應該是一個泛型類,它當中的需要參數的方法應該為泛型方法,這也說名了上面定義的接口為泛型接口的原因。

????????在單向鏈表結構中應該具備這樣一個部分,這個部分是用來描述節點內容的。而且很容易發現,節點功能只會在單向鏈表類中被使用,在其它類中不會被使用。這個描述符合內部類的特征,因此可以在單向鏈表類中定義一個內部類來存儲節點信息。將這個內部類定義為內部泛型類,它的名稱為Node,在Node類型中item變量用來存儲當前節點的元素,定義一個變量next用來指向下一個節點對象的地址,并且還要提供一個全參構造方法。具體實現如演示代碼所示。

? ? ? ? 以上定義了單向鏈表中的用于描述節點的結構,接下來就需要對單向鏈表中的具體方法做出實現了。

實現添加元素的方法

? ? ? ? 結合上文所說,單向鏈表訪問元素必須從頭節點開始,不能從尾節點或者鏈表當中的任意節點開始,因此在實現單向鏈表中的具體方法之前需要確定單向鏈表頭節點的位置。因此最簡單的方法就是定義一個私有的Node類型的成員變量來存儲單向鏈表中頭節點的位置。這里將這個變量定義為?head。此外,操作元素的方法中還涉及了元素個數的變動,也應該添加一個私有變量來記錄單向鏈表中的元素個數變動,此處為size。

? ? ? ? 隨后實現單行鏈表中添加元素的方法add。這個方法的作用是將指定元素添加到單向鏈表結構中,根據對單向鏈表結構的描述,這個方法可以分為三步實現。第一步,創建節點,將傳入方法的元素添加到創建的節點當中;第二步,找到尾節點;第三步,實現節點掛接。

????????這三步中比較難理解的是第二步和第三步。第二步找到尾節點的原因是添加元素是將元素添加到單向鏈表的尾節點之后,因此需要先找到尾節點。而在單向鏈表中,訪問元素是從頭節點開始的,所以要找到尾節點就得從頭節點開始不斷向下訪問節點,直到訪問的節點不再指向下一個元素為止,就找到了尾節點。也就是說,當next的地址為null時,尾節點就找到了。根據描述,第二步應該用一個死循環來實現,具體實現如演示代碼中的getTail方法所示。這里要注意,循環結構中的this.node = head;的意思是將head的值賦給一個新的變量node,這樣做的目的是因為真正頭節點的位置是不能改變的。其次循環實現是通過移動node指向的地址來實現的。如果不滿足要求,就像node.next也就是下一個節點的地址傳給node,直到node的地址為空。

????????第三步實現節點的掛接就稍微好理解點了,因為是在尾節點添加元素,所以新添加的元素成為了尾節點,原來的尾節點不再是尾節點,所以原來節點中指向下一個節點的地址不應為空,而應是新添加的節點。這就是節點掛接的簡單描述,具體實現為

???????????????if(tail == null){
? ? ? ? ? ? ????????this.head = node;
? ? ? ????????????}else{
? ? ? ? ? ????????? tail.next = node;

????????????????}

其中tail == null代表沒有尾節點,即整個單向鏈表均為空,這時添加的節點就是頭節點,即只需要將添加的節點賦給頭節點即可。在擁有尾節點的情況下用代碼tail.next = node;即可將尾節點指向的下一個節點指向添加的節點,節點掛接的操作就完成了。當然,添加有元素會使得單向鏈表中的元素個數發生變動,因此還需要對元素變動進行記錄。至此,添加元素的方法就完成了。

實現獲取元素的方法

? ? ? ? 獲取元素的方法是getNode,這個方法需要傳入一個int類型的參數作為元素索引,通過索引來獲取元素。這里可能會有人提出一個疑問,鏈表結構存在索引嗎?為什么能夠通過索引來過去元素?我們先暫時將這個問題擱淺,實現獲取元素的方法之后自然就清楚了。

? ? ? ? 由于getNode方法是通過索引來獲取指定位置的元素的,所以在獲取元素之前要先檢查給定的索引是否合法。因為編寫的單向鏈表類中的元素是從0這個索引開始的,所以索引的范圍為[0,size),即最小為0,最大為元素個數減1。通過單向鏈表實現的接口能發現,要實現的四個方法中不止getNaoe方法用到了元素索引,所以對索引合法性的判斷最好編寫成一個獨立的方法。在演示代碼中體現為checkIndex方法。在這個方法中,如果索引合法則會執行獲取索引所指向的元素,如果不合法則會拋出索引異常的的提示。

? ? ? ? 當給定的索引合法之后就可以獲取索引指向的元素了,那么其實可以發現,單向鏈表并沒有索引,那么這個索引哪兒來的呢?其實這里要聯系到添加元素到單向鏈表的操作,可以發現,添加元素時提供的方法時從尾節點添加的,也就是說這個單向鏈表中的元素有一個默認順序,這個順序就是添加元素的順序。那么,如果把元素添加的元素作為單向鏈表中元素的“虛假的索引”就可以通過這個“虛假的索引”來獲取單向鏈表中的元素了。這個想法在getNode這個方法得到了充分的體現。

????????????????????????????????private Node getNode(int index){
? ? ? ????????????????????????????????? Node node = this.head;
? ? ? ????????????????????????????????? for(int i = 0;i < index;i++){
? ? ? ? ? ? ????????????????????????????????node = node.next;
? ? ? ? ????????????????????????????????}
? ? ? ????????????????????????????????? return node;
? ????????????????????????????????? ? }

在方法getNode方法的代碼中,由于單向鏈表只能從頭節點開始訪問元素的限制,所以先將頭節點賦給一個新的變量node,隨后通過循環結構來訪問單向鏈表中的元素。根據上面描述的原理,獲取索引為index的元素等價于獲取第index個添加到單向鏈表中的元素,所以只要將索引index作為循環是否終止的判斷條件即可獲取到指定索引的元素。如此,先前擱淺的問題便得到了解決,同時獲取指定位置的元素的方法也得到了實現。

刪除指定索引位置的元素

? ? ? ? 刪除元素的方法為remove,這個方法仍然需要傳入一個索引,此外它還會返回刪除的元素的值。由于這個方法有一個索引,所以需要調用方法checkIndex來檢驗傳入索引的合法性。此外也要獲取到當前索引指向的節點,以方便后續操作以及返回當前節點中的元素。

? ? ? ? 接下來闡述單向鏈表中刪除元素的索引。通過上面的描述知道,單向鏈表中的元素是通過節點中存儲的地址值來鏈接在一起的,那么如果能夠將某個元素上的這個中鏈接關系刪除,就能將這個元素從這個單向鏈表中移除。所以這里涉及到三個操作,移除上一個節點指向當前節點的地址值,將上一個節點中存儲的地址值指向當前節點的下一個節點以及將當前節點存儲的地址值置空。以上的這三個操作就是在單項鏈表中刪除指定元素的具體操作,但是在具體操作時又可以分為刪除的元素是否為頭節點的情況,如果刪除的元素時頭節點,則只需要將下一個元素賦給頭節點,隨后將要刪除的節點存儲的地址置空即可。而當要刪除的元素不是頭節點時,上面的三個操作就缺一不可了。以上的描述體現在代碼中具體為:

? ? ? ??????????????????if(this.head == node){
? ? ? ? ? ? ????????????????this.head = node.next;
? ? ? ? ????????????????}else{
? ? ? ? ? ? ????????????????Node<E> temp = this.head;
? ? ? ? ? ? ????????????????for (int i = 0; i < index-1; i++) {
? ? ? ? ? ? ? ? ????????????????temp = temp.next;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ????????????????temp.next = node.next;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ????????????????node.next = null;

在這個代碼中要注意的是獲取前一個節點只需要索引減一即可。然后就是注意中間變量temp的合理運用。當然由于刪除了元素,所以記錄元素個數的變量也要發生相應的變化。

獲取元素個數的方法

? ? ? ? 獲取元素個數的方法極為簡單,因為在添加元素和刪除元素的操作中都實現了元素個數的變化,并且對元素個數的變化進行了相應記錄。所以在這個方法中只需要將記錄元素個數的變量size返回即可。

演示代碼

? ? ? ? 實現了上述的所有方法,接下來要對其進行驗證,所以開辟一個main方法,在main方法中實例化一個單向鏈表類并測試以上的四個方法。具體實現如下所示:

package com.data.demo;/***基于單項鏈表實現元素存取的容器類* @param <E>*/
public class MySinglyLinkedList<E> implements MyList<E> {//定義單向鏈表中的節點對象class Node<E>{private E item;//存儲元素private Node next;//存儲下一個節點對象的地址Node(E item,Node next){this.item = item;this.next = next;}}private Node head;//存放鏈表的頭節點private int size;//記錄元素個數//添加元素@Overridepublic void add(E element) {//創建節點Node<E> node = new Node<>(element,null);//找到尾節點Node tail = getTail();//節點掛接if(tail == null){this.head = node;}else{tail.next = node;}//記錄元素個數this.size++;}//尋找尾節點的方法private Node getTail(){//判斷頭節點是否存在if(this.head == null){return  null;}Node node  = this.head;while(true){if(node.next == null)break;node = node.next;}return node;}//獲取元素@Overridepublic E get(int index) {//校驗index的合法性this.checkIndex(index);//根據位置獲取節點元素Node<E> node = this.getNode(index);//返回節點中的元素return node.item;}/*** 校驗index合法性的方法* @return*/
private void checkIndex(int index){if(!(index < this.size && index >= 0)){throw new IndexOutOfBoundsException("Index:"+index+"Size:"+this.size);}
}/*** 根據位置獲取節點* @return*/private Node getNode(int index){Node node = this.head;for(int i = 0;i < index;i++){node = node.next;}return node;}//獲取元素個數@Overridepublic int size() {return this.size;}//刪除元素@Overridepublic E remove(int index) {//校驗index的合法性this.checkIndex(index);//根據位置找到節點對象Node<E> node = getNode(index);//獲取該節點對象中的元素E item = node.item;//將該節點對象從單向鏈表中刪除//判斷該節點是否為頭節點if(this.head == node){this.head = node.next;}else{Node<E> temp = this.head;for (int i = 0; i < index-1; i++) {temp = temp.next;}temp.next = node.next;}node.next = null;//記錄元素個數this.size--;//返回該元素return item;}public static void main(String[] args) {MySinglyLinkedList<String> mySinglyLinkedList = new MySinglyLinkedList<>();mySinglyLinkedList.add("a");mySinglyLinkedList.add("b");mySinglyLinkedList.add("c");mySinglyLinkedList.add("d");mySinglyLinkedList.add("e");System.out.println(mySinglyLinkedList.size());System.out.println(mySinglyLinkedList.remove(2));for (int i = 0; i < mySinglyLinkedList.size; i++) {System.out.println(mySinglyLinkedList.get(i));}}
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/diannao/39519.shtml
繁體地址,請注明出處:http://hk.pswp.cn/diannao/39519.shtml
英文地址,請注明出處:http://en.pswp.cn/diannao/39519.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

不要再被騙了!電腦無法進入系統的原因可能是這個硬件壞了而已……

前言 前段時間小白在抖音上發了很多很多很多的視頻&#xff0c;其中應該是有很多商家關注了小白。 然后就會出現很多很多很多的賺錢小門道…… 電腦開機沒有顯示&#xff1f;換顯卡&#xff01; 電腦還是不開機&#xff1f;換CPU 電腦還是一樣不開機…… 經過了一番大折騰…

10.8K star!史上最強Web應用防火墻雷池WAF

長亭雷池SafeLine是長亭科技耗時近 10 年傾情打造的WAF(Web Application Firewall)&#xff0c; 一款敢打出口號 “不讓黑客越雷池一步” 的 WAF&#xff0c;愿稱之為史上最強的一款Web應用防火墻&#xff0c;足夠簡單、足夠好用、足夠強的免費且開源的 WAF&#xff0c;基于業…

AI為小微企業賦能:解鎖數字化轉型的金鑰匙

AI為小微企業賦能&#xff1a;解鎖數字化轉型的金鑰匙 在當今全球經濟加速迭代的背景下&#xff0c;小微企業作為社會經濟肌體的毛細血管&#xff0c;面臨著前所未有的挑戰與機遇。人工智能&#xff08;AI&#xff09;的崛起&#xff0c;如同一股強大的科技旋風&#xff0c;為…

binlog區分業務修改還是手動修改

一、Windows下開啟MySQL binLog日志 首先要開啟MySQL的BinLog 管理 show variables like %log_bin%;如果發現log_bin是OFF&#xff0c;打開mysql文件夾下面的my.ini&#xff0c;修改一下 在 [mysqld] 下面加 # 開啟bin-log log-binmysql-bin # 開啟binlog功能 binl…

pads layout 腳本導出不能運行excle解決辦法

在一臺新的電腦上安裝好PADS&#xff0c;打開PCB文件導出坐標文件時&#xff1a; 出現“ActiveX Automation: server could not be found.”的問題,導致無法成功導出文件,錯誤提示截圖如下&#xff1a; 導致上述問題的原因是在我們配置導出帶坐標的腳本時,默認使用的是微軟…

Java 實現application/x-www-form-urlencoded編碼格式的POST請求

一、實現方式 在Java中&#xff0c;實現application/x-www-form-urlencoded內容類型通常涉及到發送HTTP POST請求。你可以使用java.net.HttpURLConnection或者第三方庫如Apache HttpClient來實現。 以下是使用HttpURLConnection發送application/x-www-form-urlencoded數據的代…

linux的shell腳本編程詳解

Shell 腳本是一種用于自動化任務的腳本語言&#xff0c;在 Linux 和其他類 Unix 操作系統中非常流行。它通常用于任務自動化、系統管理和批處理。編寫 Shell 腳本并使其自動化編譯過程&#xff08;例如使用 gcc 編譯 C/C 程序&#xff09;是一種常見的任務。 以下是一個詳細的…

昇思MindSpore學習筆記3--張量 Tensor

一、張量Tensor概念 矢量、標量和其他張量的計算函數&#xff0c;有內積、外積、線性映射以及笛卡兒積等 張量坐標在 n?維空間內&#xff0c;有?nr 個分量 每個分量都是坐標的函數,變換時每個坐標分量都按規則作線性變換 張量是一種特殊的數據結構&#xff0c;類似于數組和…

利用深度學習模型進行語音障礙自動評估

語音的產生涉及器官的復雜協調&#xff0c;因此&#xff0c;語音包含了有關身體各個方面的信息&#xff0c;從認知狀態和心理狀態到呼吸條件。近十年來&#xff0c;研究者致力于發現和利用語音生物標志物——即與特定疾病相關的語音特征&#xff0c;用于診斷。隨著人工智能&…

js基礎學習

1、js概述 js是javascript的簡稱&#xff0c;作用是實現頁面和用戶的交互 js由瀏覽器解析運行&#xff0c;不需要編譯 js由es基礎語法&#xff0c;bom瀏覽器相關&#xff0c;dom文檔操作相關 三大部分組成 2、html引入js <!DOCTYPE html> <html lang"zh-CN&qu…

Vue項目打包上線

Nginx 是一個高性能的開源HTTP和反向代理服務器&#xff0c;也是一個IMAP/POP3/SMTP代理服務器。它在設計上旨在處理高并發的請求&#xff0c;是一個輕量級、高效能的Web服務器和反向代理服務器&#xff0c;廣泛用于提供靜態資源、負載均衡、反向代理等功能。 1、下載nginx 2、…

k8s學習--k8s群集ELK日志收集部署最詳細的過程與應用(收集k8s群集日志)(圖形化界面手把手教學)

文章目錄 FilebeatFilebeat主要特點Filebeat使用場景 ELK簡介Elasticsearch簡介Elasticsearch主要特點Elasticsearch使用場景 Logstash簡介Logstash主要特點Logstash使用場景 Kibana簡介Kibana主要特點Kibana使用場景 簡單理解 環境一、ELK集群部署1.軟件安裝2.軟件配置及啟動(…

Webpack: Loader開發 (2)

概述 在上一篇文章中&#xff0c;我們已經詳細了解了開發 Webpack Loader 需要用到的基本技能&#xff0c;包括&#xff1a;Loader 基本形態、如何構建測試環境、如何使用 Loader Context 接口等。接下來我們繼續拓展學習一些 Loader 輔助工具&#xff0c;包括&#xff1a; 了…

telegram支付

今天開始接入telegram支付,參考教程這個是telegram的官方說明,詳細介紹了機器人支付API。 文章公開地址 新建機器人 因為支付是一個單獨的系統,所以在做支付的時候單獨創建了一個bot,沒有用之前的bot了,特意這樣將其分開。創建bot的方法和之前不變,這里不過多介紹。 獲…

Linux文件數據寫入

結構體 fd fd也就是文件描述符&#xff0c;用于標識已經打開的文件、管道、socket等。是進程和內核的橋梁&#xff0c;允許進程執行各種文件操作 struct fd {struct file *file;unsigned int flags; };file Linux內核中表示打開文件的結構體&#xff0c;包含了文件操作所需…

什么是自然語言處理(NLP)?詳細解讀文本分類、情感分析和機器翻譯的核心技術

什么是自然語言處理&#xff1f; 自然語言處理&#xff08;Natural Language Processing&#xff0c;簡稱NLP&#xff09;是人工智能的一個重要分支&#xff0c;旨在讓計算機理解、解釋和生成人類的自然語言。打個比方&#xff0c;你和Siri對話&#xff0c;或使用谷歌翻譯翻譯一…

2024廣州國際米粉產業展覽會暨米粉節

2024廣州國際米粉產業展覽會 時間&#xff1a;2024年11月16-18日 地點&#xff1a;廣州中國進出口商品交易會展館 主辦單位&#xff1a;企陽國際會展集團 【展會簡介】 米粉作為一種歷史悠久&#xff0c;人們日常食用的食物&#xff0c;其市場需求穩定&#xff0c;且隨著人…

學習.NET 8 MiniApis入門

介紹篇 什么是MiniApis&#xff1f; MiniApis的特點和優勢 MiniApis的應用場景 環境搭建 系統要求 安裝MiniApis 配置開發環境 基礎概念 MiniApis架構概述 關鍵術語解釋&#xff08;如Endpoint、Handler等&#xff09; MiniApis與其他API框架的對比 第一個MiniApis…

WSL2安裝ContOS7并更新gcc

目錄 WSL2安裝CentOS7下載安裝包安裝啟動CentOS7 CentOS7更換國內源gcc從源碼安裝gcc卸載gcc CMake中使用gcc關于linux配置文件參考 WSL2安裝CentOS7 Windows11官方WSL2已經支持Ubuntu、Open SUSE、Debian。但是沒有centos&#xff0c;所以centos的安裝方式略有不同。 下載安…

【面試題】網絡IP協議(第六篇)

1.簡述IP協議的作用。 IP協議&#xff08;Internet Protocol&#xff09;是TCP/IP協議族中的核心協議之一&#xff0c;主要用于在互聯網上進行數據傳輸。它的主要作用包括&#xff1a; 尋址&#xff1a;IP協議通過IP地址來唯一標識網絡中的每一臺設備&#xff0c;確保數據包能…