鏈表中數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元 素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據 域，另一個是存儲下一個結點地址的指針域。
作為一個技術博主，了不起不是在創作就是在創作的路上（當然偶爾也會有點恰飯文~還指望大家多多支持），昨天的時候，了不起給大家分享了一下這個關于數據結構里面的數組是什么內容，而且也給大家說了數據結構都有什么，我們來回顧一下內容。
數據結構分類
我們在開發中，也都經常的用到數據結構，只是不是很在意這個名詞，而是直接使用他們的另外的說法，比如：
上面的這四個數結構，可以統稱為線性表。而除了線性表，我們還有其他的數據結構，比如散列表，樹，還有圖。
散列表有：
樹有：
圖包含：
今天我們就來分析一下這個數據結構中的另外一個，鏈表。
什么是鏈表
按照慣例，我們先從百度百科上面看看他是怎么解釋的：
鏈表（linked list）是一種在物理上非連續、非順序的數據結構，由若干節點（node）所組成。
鏈表中數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元 素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據 域，另一個是存儲下一個結點地址的指針域。
其實換成大白話解釋，那就是一個一個的結點組合成的一個鏈式結構，上一個元素存儲下一個元素的指針域。
我們常見的鏈表結構，比較少，就那么幾種
單鏈表
單向鏈表的每一個節點又包含兩部分，一部分是存放數據的變量data，另一部分是指向下一個節 點的指針next
實際上模擬代碼:
Node{
int data;
Node next;
}那么他的圖解是什么樣子呢？
圖解畫的比較爛，大家多見諒。
雙向鏈表
雙向鏈表是什么呢？
雙向鏈表的每一個節點除了擁有data和next指針，還擁有指向前置節點的prev指針。
循環鏈表
那么什么是循環鏈表呢？
循環鏈表實際上就是鏈表的尾節點指向頭節點形成一個環，稱為循環鏈表。
那么圖解是什么樣的呢？
我們在昨天看數組的時候，知道了數組數組在內存中的存儲方式是順序存儲（連續存儲）。
那么鏈表呢？
其實鏈表在內存中的存儲方式則是隨機存儲（鏈式存 儲）
鏈表的每一個節點分布在內存的不同位置，依靠next指針關聯起來。這樣可以靈活有效地利用零散的碎 片空間。
我們再來一個簡單的內存結構圖來看一下這個鏈表在內存中的存儲模型。
那么查找操作是什么操作呢？
查找節點：
在查找元素時，鏈表只能從頭節點開始向后一個一個節點逐一查找。
更新節點：
找到要更新的節點，然后把舊數據替換成新數據
其實鏈表這個地方，很多時候后在面試的時候，經常會被問到一個內容，那就是插入還有刪除，這是面試的時候經常會被問到的一個內容，那么這個插入是什么樣子的呢？
鏈表的插入
鏈表的插入也即鏈表的構建，把點連成鏈。因插入位置不同分成三種情況。
在鏈表最前端插入數據
在鏈表最后插入數據
當在鏈表中間插入值的時候，新節點：new
原插入位置節點：temp
temp前一個節點：pre
插入操作需要做的：
new.next = temp
pre.next = new
而這個插入，又離不開 head，
我們來模擬一下這個使用 Java 代碼來簡單的實現一下這個頭插法，尾插法，已經按照位置插入。
我們先定義一個頭部
我們再建立鏈表對象的類：LinkNode
public class ListNode {
private int val;
private ListNode next;
public ListNode(int value) {
this.val = value;
}
public ListNode() {}
public ListNode getNext() {
return this.next;
}
public int getVal() {
return this.val;
}
public void setNext(ListNode next) {
this.next = next;
}
public void setVal(int value) {
this.val = value;
}
}頭插法
public void HeadInsert(int val) {
ListNode newNode = new ListNode(val); 首先把val建立成一個新節點
if(head == null) { 鏈表為空的情況
head = newNode;
return;
}
newNode.setNext(head); 鏈表不為空，則把原第一個節點給到新節點的next
head = newNode; 新節點成為頭節點
}尾插法
public void EndInsert(int val) {
新建節點存儲數據
ListNode newNode = new ListNode(val);
判斷頭節點是否為空，就是鏈表是否為空
if(head == null) {
head = newNode;
return;
}
ListNode indexNode = head; 由于頭節點head不能改變，召喚替身
while (indexNode.getNext() != null) { 從頭向后遍歷，直到某一節點的next
indexNode = indexNode.getNext(); 是空的，意味他是最后一個節點。
}
indexNode.setNext(newNode); 讓原來最后一個節點的next指向新節點
}按位置插入
public void Insert(int val,int index) {數值，插入位置
if(index<0 || index > this.getLength()) {
System.out.println("index位置不合法");
return;
}
if(index == 0) {
HeadInsert(val);
}else if(index == getLength()) {
EndInsert(val);
}else {
ListNode newNode = new ListNode(val);
ListNode tempNode = head;
ListNode preNode = null; pre在temp前1位
int position = 0; 通過它找到正確插入位置
while (tempNode != null) {
if(position == index) {
newNode.setNext(tempNode); pre在temp前1位
temp指向的是要被插入的位置的值
preNode.setNext(newNode);
return;
}
preNode = tempNode;
tempNode = tempNode.getNext();
position++;
}
}
}其實相對而言，鏈表的刪除就真的比這個插入簡單了。
鏈表刪除
public void Delete(int index) {
if (index < 0 || index>getLength()) {
System.out.println("位置不合法");
return;
}
if(index == 0) { 刪除第一個節點時
head = head.getNext();
return;
}
ListNode tempNode = head;
ListNode preNode = null;
int position = 0;
while(tempNode != null) {
if(position == index) {
//pre和temp差1位，temp指向的是要被刪除的值
preNode.setNext(tempNode.getNext());
//temp的下一個值由pre和temp都指向，刪除temp的
tempNode.setNext(null );
return;
}
preNode = tempNode;
tempNode = tempNode.getNext();
position++;
}
}對于這個鏈表，你學會了么？
