作為一個技術(shù)博主，了不起不是在創(chuàng)作就是在創(chuàng)作的路上（當然偶爾也會有點恰飯文~還指望大家多多支持），昨天的時候，了不起給大家分享了一下這個關(guān)于數(shù)據(jù)結(jié)構(gòu)里面的數(shù)組是什么內(nèi)容，而且也給大家說了數(shù)據(jù)結(jié)構(gòu)都有什么，我們來回顧一下內(nèi)容。

數(shù)據(jù)結(jié)構(gòu)分類

我們在開發(fā)中，也都經(jīng)常的用到數(shù)據(jù)結(jié)構(gòu)，只是不是很在意這個名詞，而是直接使用他們的另外的說法，比如：

• 數(shù)組
• 鏈表
• 堆
• 棧

上面的這四個數(shù)結(jié)構(gòu)，可以統(tǒng)稱為線性表。而除了線性表，我們還有其他的數(shù)據(jù)結(jié)構(gòu)，比如散列表，樹，還有圖。

散列表有：

• hash
• 位圖

樹有：

• 二叉樹
• 多路樹
• 堆

圖包含：

• 有向圖
• 無向圖
• 帶權(quán)圖

今天我們就來分析一下這個數(shù)據(jù)結(jié)構(gòu)中的另外一個，鏈表。

什么是鏈表

按照慣例，我們先從百度百科上面看看他是怎么解釋的：

鏈表（linked list）是一種在物理上非連續(xù)、非順序的數(shù)據(jù)結(jié)構(gòu)，由若干節(jié)點（node）所組成。

鏈表中數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元 素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù) 域，另一個是存儲下一個結(jié)點地址的指針域。

其實換成大白話解釋，那就是一個一個的結(jié)點組合成的一個鏈式結(jié)構(gòu)，上一個元素存儲下一個元素的指針域。

我們常見的鏈表結(jié)構(gòu)，比較少，就那么幾種

單鏈表

單向鏈表的每一個節(jié)點又包含兩部分，一部分是存放數(shù)據(jù)的變量data，另一部分是指向下一個節(jié) 點的指針next

實際上模擬代碼:

Node{
int data;
Node next;
}

那么他的圖解是什么樣子呢？

圖解畫的比較爛，大家多見諒。

雙向鏈表

雙向鏈表是什么呢？

雙向鏈表的每一個節(jié)點除了擁有data和next指針，還擁有指向前置節(jié)點的prev指針。

循環(huán)鏈表

那么什么是循環(huán)鏈表呢？

循環(huán)鏈表實際上就是鏈表的尾節(jié)點指向頭節(jié)點形成一個環(huán)，稱為循環(huán)鏈表。

那么圖解是什么樣的呢？

我們在昨天看數(shù)組的時候，知道了數(shù)組數(shù)組在內(nèi)存中的存儲方式是順序存儲（連續(xù)存儲）。

那么鏈表呢？

其實鏈表在內(nèi)存中的存儲方式則是隨機存儲（鏈式存 儲）

鏈表的每一個節(jié)點分布在內(nèi)存的不同位置，依靠next指針關(guān)聯(lián)起來。這樣可以靈活有效地利用零散的碎 片空間。

我們再來一個簡單的內(nèi)存結(jié)構(gòu)圖來看一下這個鏈表在內(nèi)存中的存儲模型。

那么查找操作是什么操作呢？

查找節(jié)點：

在查找元素時，鏈表只能從頭節(jié)點開始向后一個一個節(jié)點逐一查找。

更新節(jié)點：

找到要更新的節(jié)點，然后把舊數(shù)據(jù)替換成新數(shù)據(jù)

其實鏈表這個地方，很多時候后在面試的時候，經(jīng)常會被問到一個內(nèi)容，那就是插入還有刪除，這是面試的時候經(jīng)常會被問到的一個內(nèi)容，那么這個插入是什么樣子的呢？

鏈表的插入

鏈表的插入也即鏈表的構(gòu)建，把點連成鏈。因插入位置不同分成三種情況。

• 1.頭插法

在鏈表最前端插入數(shù)據(jù)

• 2.尾插法

在鏈表最后插入數(shù)據(jù)

• 3.按位置插入

當在鏈表中間插入值的時候，新節(jié)點：new

原插入位置節(jié)點：temp

temp前一個節(jié)點：pre

插入操作需要做的：

new.next = temp
pre.next = new

而這個插入，又離不開 head，

我們來模擬一下這個使用 Java 代碼來簡單的實現(xiàn)一下這個頭插法，尾插法，已經(jīng)按照位置插入。

我們先定義一個頭部

ListNode head = null;

我們再建立鏈表對象的類：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建立成一個新節(jié)點
  if(head == null) {    鏈表為空的情況
   head = newNode;
   return;
  }
  newNode.setNext(head);    鏈表不為空，則把原第一個節(jié)點給到新節(jié)點的next
  head = newNode;    新節(jié)點成為頭節(jié)點
 }

尾插法

public void EndInsert(int val) {
  新建節(jié)點存儲數(shù)據(jù)
  ListNode newNode = new ListNode(val); 
  判斷頭節(jié)點是否為空，就是鏈表是否為空
  if(head == null) {
   head = newNode;    
   return;
  }
  ListNode indexNode = head;    由于頭節(jié)點head不能改變，召喚替身
  while (indexNode.getNext() != null) {    從頭向后遍歷，直到某一節(jié)點的next
   indexNode = indexNode.getNext();    是空的，意味他是最后一個節(jié)點。
  }
  indexNode.setNext(newNode);    讓原來最后一個節(jié)點的next指向新節(jié)點
 }

按位置插入

public void Insert(int val,int index) {數(shù)值，插入位置
  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) {    刪除第一個節(jié)點時
   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++;
  }
 }

對于這個鏈表，你學會了么？