一篇文章帶你玩轉JAVA單鏈表
一、鏈表
1. 概念
鏈表是一種物理存儲結構上非連續(xù)的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用鏈接次序實現(xiàn)的
上章介紹到順序表適合用作查詢和修改，而不適合用作插入和刪除。并且它增容時容易造成空間浪費。而鏈表則具有以下的特點
適合用作插入和刪除隨用隨取，避免了空間的浪費不適合用作查詢和修改
2. 結構
鏈表其實可以想象成一條被打了一些結的繩子
而實際上，鏈表就是由一個個節(jié)點構成的，只不過每個節(jié)點一般有兩個域
數(shù)值域 data： 里面存儲數(shù)據(jù)
next 域： 里面存儲的是下一個節(jié)點的地址（是引用變量）
其中
尾節(jié)點： 當這個節(jié)點的 next 域為 null 時，該節(jié)點就是尾節(jié)點
頭節(jié)點： 整個鏈表的第一個節(jié)點就是頭節(jié)點
實際中的鏈表結構非常多，通過以下的情況的組合可以有8種鏈表的結構（比如帶頭單向循環(huán)鏈表就是一種）
單向、雙向
帶頭節(jié)點、不帶頭
節(jié)點循環(huán)、非循環(huán)
而上圖所示，就是一個單向不帶頭非循環(huán)鏈表。
可能有人會疑問，上述圖片中不是存在頭節(jié)點嗎？那為啥它又是一個不帶頭節(jié)點的鏈表呢？我將上述圖片實例稍稍改一下就是帶頭節(jié)點的了
我在原有的頭節(jié)點前面又多了一個節(jié)點，并且這個節(jié)點的數(shù)值域里面的數(shù)據(jù)可有可無，因為對其沒有影響。而這里面的頭節(jié)點只是一個標志，標識這個節(jié)點是該鏈表的頭
那帶頭節(jié)點的和不帶頭結點的鏈表有啥差別呢？
不帶頭： 這個鏈表的頭節(jié)點可能發(fā)生改
變帶頭： 這個鏈表的頭節(jié)點不會發(fā)生改變
那循環(huán)鏈表又是啥樣的呢？我們可以將上述單向不帶頭非循環(huán)鏈表稍微修改一下
即將尾節(jié)點的 next 域存儲了頭節(jié)點的地址
我們知道一個節(jié)點一般就兩個域，但如果是雙向鏈表，則就有三個域了
數(shù)值域 data： 里面存儲數(shù)據(jù)
next 域： 里面存儲的是下一個節(jié)點的地址（是引用變量）
prev 域： 里面存儲的是上一個節(jié)點的地址（是引用變量）
我們畫一個不帶頭雙向非循環(huán)鏈表就是這樣的
接下來我將主要介紹單向不帶頭非循環(huán)鏈表和雙向不帶頭非循環(huán)鏈表，這兩種鏈表也是經(jīng)常出現(xiàn)在面試題中的
二、單向不帶頭非循環(huán)鏈表
1. 概念及結構
上述通過圖解，大家應該對單向不帶頭非循環(huán)鏈表應該有了了解。那么代碼中該怎么實現(xiàn)呢？
我們知道，鏈表應該可以看作一個類，而節(jié)點本身其實也可以抽象的看作成一個類
首先對于節(jié)點類，代碼可以寫出這樣
class Node{
public int val;
public Node next;
public Node(int val){
this.val=val;
}
}
先定義了數(shù)值域，再定義了 next 域（由于 next 存儲的是下一個節(jié)點的地址，故寫出上述那樣）。而我們初始時可以知道 val，所以可以寫個構造函數(shù)對 val 進行初始化，而該節(jié)點的 next 域初始時是不可能知道的，所以不對 next 做初始化
如果創(chuàng)造一個 Node 對象就可以寫出
Node node = new Node(10);
即頭節(jié)點的數(shù)值域為10。
再定義鏈表類，代碼可以寫成這樣
public class MyLinkedList {
public Node head;
}
我們定義了一個頭節(jié)點，這是我們很容易發(fā)現(xiàn)的，就比如我要對該鏈表進行頭插，則該鏈表的頭節(jié)點一直都在改變。所以寫上述的代碼就是為了標識單鏈表的頭節(jié)點。
2. 鏈表的實現(xiàn)
接下來我們來實現(xiàn)單向不帶頭非循環(huán)鏈表的一些操作
打印鏈表
public void display(){
Node cur =this.head;
while(cur!=null){
System.out.print(cur.val + " ");
cur=cur.next;
}
System.out.println();
}
求鏈表的長度
public int size(){
Node cur=this.head;
int count=0;
while(cur!=null){
count++;
cur=cur.next;
}
return count;
}
查找值 key 是否在單鏈表中
public boolean contains(int key){
Node cur=this.head;
while(cur!=null){
if(key==cur.val){
return true;
}
cur=cur.next;
}
return false;
}
清除單鏈表
public void clear(){
this.head.val=0;
this.head.next=null;
}
頭插法
public void addFirst(int data){
Node node=new Node(data);
if(head==null){
this.head=node;
}else {
node.next = this.head;
this.head = node;
}
}
尾插法
public void addLast(int data){
Node node = new Node(data);
if(this.head==null){
this.head=node;
}else {
Node cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
通過下標找到前驅節(jié)點（第一個節(jié)點下標為0）
public Node searchPrev(int index){
Node cur = this.head;
int count=0;
while(count!=index-1){
cur=cur.next;
count++;
}
return cur;
}
任意位置插入
public void addIndex(int index, int data){
if(index<0 || index>size()){
throw new RuntimeException("index 不合法");
}
if(index==0){
addFirst(data);
return;
}
if(index==size()) {
addLast(data);
return;
}
Node node =new Node(data);
Node cur =searchPrev(index);
node.next=cur.next;
cur.next=node;
}
通過值 key 找到前驅節(jié)點（第一個節(jié)點下標為0）
public Node searchPrevNode(int key){
Node cur = this.head;
while(cur.next!=null){
if(cur.next.val==key) {
return cur;
}
cur=cur.next;
}
return null;
}
刪除第一次出現(xiàn)的值為 key 的節(jié)點
public void remove(int key){
if(this.head==null){
return;
}
if(key==this.head.val){
this.head=this.head.next;
return;
}
Node node = searchPrevNode(key);
if(node==null){
System.out.println("鏈表中無要刪除的元素");
}else {
node.next = node.next.next;
}
}
刪除所有出現(xiàn)的值為 key 的節(jié)點
public void removeAllKey(int key){
if(this.head==null){
return;
}
Node prev=this.head;
Node cur=this.head.next;
while(cur!=null){
if(cur.val==key){
cur=cur.next;
prev.next=cur;
}else{
prev=cur;
cur=cur.next;
}
}
if(this.head.val==key){
this.head=this.head.next;
}
}
呼，寫的我人傻了
你以為結束了嗎？NO！下面還有一大波鏈表面試題等著我和你，沖吧，牛牛！
三、鏈表面試題
刪除鏈表中等于給定值 val 的所有節(jié)點 OJ 鏈接
反轉一個單鏈表 OJ 鏈接
給定一個帶有頭結點 head 的非空單鏈表，返回鏈表的中間結點。如果有兩個中間結點，則返回第二個中間結點 OJ 鏈接
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結點 OJ 鏈接
將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的 OJ 鏈接
編寫代碼，以給定值x為基準將鏈表分割成兩部分，所有小于x的結點排在大于或等于x的結點之前 OJ 鏈接
在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點，重復的結點不保留，返回鏈表頭指針 OJ 鏈接
鏈表的回文結構 OJ 鏈接
輸入兩個鏈表，找出它們的第一個公共結點 OJ 鏈接
給定一個鏈表，判斷鏈表中是否有環(huán) OJ 鏈接
給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null OJ 鏈接
如果你已經(jīng)可以輕松應對上述題目了，可以繼續(xù)去下面的鏈接中做題 Leetcode OJ 鏈接 和 ?？?OJ 鏈接
四、總結
今天簡單了解了鏈表，以及對單向不帶頭非循環(huán)鏈表做了一些基操的實現(xiàn)。下章將包含個人的上述前11道 OJ 題的題解，以及了解雙向不帶頭非循環(huán)鏈表
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關注腳本之家的更多內容！
相關文章
這篇文章主要介紹了springboot如何獲取yml里面的屬性值，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-02-02
java環(huán)境變量path和classpath的配置
這篇文章主要為大家詳細介紹了java系統(tǒng)環(huán)境變量path和classpath的配置過程，感興趣的小伙伴們可以參考一下2016-07-07
在實際工作中，常常需要設定數(shù)字的輸出格式，如以百分比的形式輸出，或者設定小數(shù)位數(shù)等，現(xiàn)稍微總結如下2014-01-01
這篇文章主要為大家詳細介紹了java導出csv格式文件的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12
這篇文章主要介紹了springboot如何整合elasticsearch問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-04-04
這篇文章主要為大家介紹了java大話之創(chuàng)建型設計模式教程示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-02-02
關于java入門與java開發(fā)環(huán)境配置詳細教程
這篇文章主要介紹了關于java入門與java開發(fā)環(huán)境配置詳細教程,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-03-03
在使用學習使用 Spring過程中，當我們要實現(xiàn)一個功能的時候，先應該考慮的是有沒有相應的注解是實現(xiàn)對應功能的，Spring 中很多功能的配置都是可以依靠注解實現(xiàn)的，而本篇中介紹的是使用注解來存儲 Bean 對象2023-07-07
這篇文章主要介紹了Mybatis中萬能的Map和模糊查詢寫法的相關資料，幫助大家更好的理解和使用Mybatis，感興趣的朋友可以了解下2021-03-03
這篇文章主要為大家介紹了Lucene?索引刪除策略源碼解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03