鏈表還有頭插和尾插？

作者：了不起 2023-03-29 07:36:32

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

作為一個(gè)技術(shù)博主，了不起不是在創(chuàng)作就是在創(chuàng)作的路上（當(dāng)然偶爾也會(huì)有點(diǎn)恰飯文~還指望大家多多支持），昨天的時(shí)候，了不起給大家分享了一下這個(gè)關(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)，只是不是很在意這個(gè)名詞，而是直接使用他們的另外的說法，比如：

數(shù)組
鏈表
堆
棧

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

散列表有：

hash
位圖

樹有：

二叉樹
多路樹
堆

圖包含：

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

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

什么是鏈表

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

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

其實(shí)換成大白話解釋，那就是一個(gè)一個(gè)的結(jié)點(diǎn)組合成的一個(gè)鏈?zhǔn)浇Y(jié)構(gòu)，上一個(gè)元素存儲(chǔ)下一個(gè)元素的指針域。

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

單鏈表

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

實(shí)際上模擬代碼:

Node{
int data;
Node next;
}

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

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

雙向鏈表

雙向鏈表是什么呢？

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

循環(huán)鏈表

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

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

那么圖解是什么樣的呢？

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

那么鏈表呢？

其實(shí)鏈表在內(nèi)存中的存儲(chǔ)方式則是隨機(jī)存儲(chǔ)（鏈?zhǔn)酱?儲(chǔ)）

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

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

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

查找節(jié)點(diǎn)：

在查找元素時(shí)，鏈表只能從頭節(jié)點(diǎn)開始向后一個(gè)一個(gè)節(jié)點(diǎn)逐一查找。

更新節(jié)點(diǎn)：

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

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

鏈表的插入

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

1.頭插法

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

2.尾插法

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

3.按位置插入

當(dāng)在鏈表中間插入值的時(shí)候，新節(jié)點(diǎn)：new

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

temp前一個(gè)節(jié)點(diǎn)：pre

插入操作需要做的：

new.next = temp
pre.next = new

而這個(gè)插入，又離不開 head，

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

我們先定義一個(gè)頭部

ListNode head = null;

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

尾插法

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

按位置插入

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++;
   }
  }
 }

其實(shí)相對(duì)而言，鏈表的刪除就真的比這個(gè)插入簡單了。

鏈表刪除

public void Delete(int index) {
  if (index < 0 || index>getLength()) {
   System.out.println("位置不合法");
            return;
  }
  if(index == 0) {    刪除第一個(gè)節(jié)點(diǎn)時(shí)
   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的下一個(gè)值由pre和temp都指向，刪除temp的                                       
    tempNode.setNext(null );    
    return;
   }
   preNode = tempNode;
   tempNode = tempNode.getNext();
   position++;
  }
 }