建站
咨詢
售后
建站咨詢
新聞中心
作為一個(gè)技術(shù)博主，了不起不是在創(chuàng)作就是在創(chuàng)作的路上（當(dāng)然偶爾也會(huì)有點(diǎn)恰飯文~還指望大家多多支持），昨天的時(shí)候，了不起給大家分享了一下這個(gè)關(guān)于數(shù)據(jù)結(jié)構(gòu)里面的數(shù)組是什么內(nèi)容，而且也給大家說(shuō)了數(shù)據(jù)結(jié)構(gòu)都有什么，我們來(lái)回顧一下內(nèi)容。
數(shù)據(jù)結(jié)構(gòu)分類
我們?cè)陂_(kāi)發(fā)中，也都經(jīng)常的用到數(shù)據(jù)結(jié)構(gòu)，只是不是很在意這個(gè)名詞，而是直接使用他們的另外的說(shuō)法，比如：
- 數(shù)組
- 鏈表
- 堆
- 棧
上面的這四個(gè)數(shù)結(jié)構(gòu)，可以統(tǒng)稱為線性表。而除了線性表，我們還有其他的數(shù)據(jù)結(jié)構(gòu)，比如散列表，樹(shù)，還有圖。
散列表有：
- hash
- 位圖
樹(shù)有：
- 二叉樹(shù)
- 多路樹(shù)
- 堆
圖包含：
- 有向圖
- 無(wú)向圖
- 帶權(quán)圖
今天我們就來(lái)分析一下這個(gè)數(shù)據(jù)結(jié)構(gòu)中的另外一個(gè)，鏈表。
什么是鏈表
按照慣例，我們先從百度百科上面看看他是怎么解釋的：
鏈表（linked list）是一種在物理上非連續(xù)、非順序的數(shù)據(jù)結(jié)構(gòu)，由若干節(jié)點(diǎn)（node）所組成。
鏈表中數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?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)地址的指針域。
其實(shí)換成大白話解釋，那就是一個(gè)一個(gè)的結(jié)點(diǎn)組合成的一個(gè)鏈?zhǔn)浇Y(jié)構(gòu)，上一個(gè)元素存儲(chǔ)下一個(gè)元素的指針域。
我們常見(jiàn)的鏈表結(jié)構(gòu)，比較少，就那么幾種
單鏈表
單向鏈表的每一個(gè)節(jié)點(diǎn)又包含兩部分，一部分是存放數(shù)據(jù)的變量data，另一部分是指向下一個(gè)節(jié) 點(diǎn)的指針next
實(shí)際上模擬代碼:
Node{
int data;
Node next;
}那么他的圖解是什么樣子呢？
圖解畫(huà)的比較爛，大家多見(jiàn)諒。
雙向鏈表
雙向鏈表是什么呢？
雙向鏈表的每一個(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)鏈表。
那么圖解是什么樣的呢？
我們?cè)谧蛱炜磾?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)起來(lái)。這樣可以靈活有效地利用零散的碎 片空間。
我們?cè)賮?lái)一個(gè)簡(jiǎn)單的內(nèi)存結(jié)構(gòu)圖來(lái)看一下這個(gè)鏈表在內(nèi)存中的存儲(chǔ)模型。
那么查找操作是什么操作呢？
查找節(jié)點(diǎn)：
在查找元素時(shí)，鏈表只能從頭節(jié)點(diǎn)開(kāi)始向后一個(gè)一個(gè)節(jié)點(diǎn)逐一查找。
更新節(jié)點(diǎn)：
找到要更新的節(jié)點(diǎn)，然后把舊數(shù)據(jù)替換成新數(shù)據(jù)
其實(shí)鏈表這個(gè)地方，很多時(shí)候后在面試的時(shí)候，經(jīng)常會(huì)被問(wèn)到一個(gè)內(nèi)容，那就是插入還有刪除，這是面試的時(shí)候經(jīng)常會(huì)被問(wèn)到的一個(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è)插入，又離不開(kāi) head，
我們來(lái)模擬一下這個(gè)使用 Java 代碼來(lái)簡(jiǎn)單的實(shí)現(xiàn)一下這個(gè)頭插法，尾插法，已經(jīng)按照位置插入。
我們先定義一個(gè)頭部
ListNode head = null;
我們?cè)俳㈡湵韺?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); 讓原來(lái)最后一個(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; 通過(guò)它找到正確插入位置
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è)插入簡(jiǎn)單了。
鏈表刪除
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++;
}
}對(duì)于這個(gè)鏈表，你學(xué)會(huì)了么？
分享名稱：鏈表還有頭插和尾插？
分享網(wǎng)址：http://www.dlmjj.cn/article/cdhcgdg.html
