目錄

1 鏈表的概念和分類(lèi)

2 鏈表對(duì)于數(shù)據(jù)的增刪查操作（以單向鏈表為例）

2.1 增刪查操作的描述

2.2 增刪查操作的代碼實(shí)現(xiàn)（JAVA）

---

1 鏈表的概念和分類(lèi)

鏈表，又稱(chēng)線性表或線性鏈表，是若干數(shù)據(jù)元素組成的線性序列，將數(shù)據(jù)元素像鏈條一樣組織在一起。存儲(chǔ)在鏈表中的數(shù)據(jù)元素被稱(chēng)為結(jié)點(diǎn)（node）,每個(gè)結(jié)點(diǎn)具有兩個(gè)要素：第一、數(shù)據(jù)元素的具體值，第二、指向下一個(gè)結(jié)點(diǎn)的指針，指針用來(lái)存儲(chǔ)下一個(gè)結(jié)點(diǎn)的內(nèi)存地址。根據(jù)結(jié)點(diǎn)的結(jié)構(gòu)，鏈表可分為單向鏈表、雙向鏈表、循環(huán)鏈表。

最基本的鏈表結(jié)構(gòu)是單向鏈表，最前面是一個(gè)頭指針用來(lái)指向第一個(gè)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的指針是一個(gè)空指針（null pointer），每一個(gè)結(jié)點(diǎn)都只指向它的下一個(gè)結(jié)點(diǎn)，例如一個(gè)存儲(chǔ)了5個(gè)學(xué)生考試分?jǐn)?shù)的鏈表：

雙向鏈表（duoble linked list）每一個(gè)結(jié)點(diǎn)有兩個(gè)指針，一個(gè)指向前驅(qū)結(jié)點(diǎn)（prev pointer），一個(gè)指向后續(xù)結(jié)點(diǎn)（next pointer），第一個(gè)結(jié)點(diǎn)的prev指針和最后一個(gè)結(jié)點(diǎn)的next指針都是空指針。

讓鏈表的最后一個(gè)元素指向第一個(gè)元素就構(gòu)成了循環(huán)鏈表，循環(huán)鏈表也有單向和雙向兩個(gè)類(lèi)型。

2 鏈表對(duì)于數(shù)據(jù)的增刪查操作（以單向鏈表為例）

2.1 增刪查操作的描述

查找元素的功能弱，速度慢：只能通過(guò)遍歷方式找到指定元素，即從鏈頭（或鏈尾）開(kāi)始一個(gè)個(gè)跳轉(zhuǎn)，直到跳轉(zhuǎn)到指定元素的位置。

增刪元素的功能強(qiáng)，速度快：無(wú)論在哪個(gè)位置增加或刪除元素，只需改變指針指向就能實(shí)現(xiàn)，即修改連接的下個(gè)元素的內(nèi)存地址。

• 插入元素的操作：先讓待插入結(jié)點(diǎn)的指針指向指定位置原來(lái)的結(jié)點(diǎn)，再讓指定位置前驅(qū)結(jié)點(diǎn)的指針指向待插入的結(jié)點(diǎn)。
• 刪除元素的操作：只需修改待刪除結(jié)點(diǎn)前驅(qū)元素的指針，讓前驅(qū)結(jié)點(diǎn)指針指向待刪除結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)。

?

2.2 增刪查操作的代碼實(shí)現(xiàn)（JAVA）

用 Java 模擬以上圖示中的鏈表操作。

MyLink.java：準(zhǔn)備工作，創(chuàng)建一個(gè)鏈表類(lèi)

package com.notes.data_structure1;public class MyLink {private Node headNode; // 定義一個(gè)頭結(jié)點(diǎn)private Node currentNode; // 定義一個(gè)當(dāng)前結(jié)點(diǎn)// 定義一個(gè)結(jié)點(diǎn)類(lèi)private class Node {// 結(jié)點(diǎn)的兩個(gè)要素：數(shù)據(jù)和指針private int data;private Node next;// 構(gòu)造方法：Node實(shí)例化時(shí)給data賦值public Node(int data) {this.data = data;}}// 創(chuàng)建頭結(jié)點(diǎn)private Node addHeadNode() {// 頭結(jié)點(diǎn)用來(lái)模擬頭指針，數(shù)據(jù)設(shè)為0headNode = new Node(0);return headNode;}// 增加結(jié)點(diǎn)public void addNode(int data) {// 如果頭結(jié)點(diǎn)不存在，當(dāng)前結(jié)點(diǎn)為頭結(jié)點(diǎn)，這樣就有了頭指針if (headNode==null) {// 當(dāng)前結(jié)點(diǎn)是頭結(jié)點(diǎn)，調(diào)用創(chuàng)建頭結(jié)點(diǎn)的方法currentNode = addHeadNode();}// 創(chuàng)建一個(gè)新的結(jié)點(diǎn)Node node = new Node(data);// 當(dāng)前結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)currentNode.next = node;// 當(dāng)前結(jié)點(diǎn)后移一位，新結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)，正式加入鏈表currentNode = currentNode.next;}// 遍歷打印所有的結(jié)點(diǎn)（不包括頭結(jié)點(diǎn)）public void printLink() {// temp可以看作一個(gè)移動(dòng)的指針Node temp = headNode;// 通過(guò)指針的移動(dòng)遍歷數(shù)組，直到指針指向鏈尾的nullwhile(temp.next != null) {temp = temp.next;System.out.println(temp.data);}}/*** 模擬 “查” 有關(guān)的鏈表操作* 查找指定數(shù)據(jù)，返回?cái)?shù)據(jù)所在的位置（索引）*/public void searchNode(int data) {int index = 0; // 用于計(jì)算數(shù)據(jù)位置boolean notFound = true; // 用于存儲(chǔ)是否找到數(shù)據(jù)// 遍歷查找指定的數(shù)據(jù)Node temp = headNode;while(temp.next != null) {temp = temp.next;index ++;if (temp.data == data) {System.out.println(data+"存儲(chǔ)在鏈表的第"+index+"個(gè)結(jié)點(diǎn)中");notFound = false;break;}}if(notFound) {System.out.println("沒(méi)有找到值為"+data+"的元素");}}/*** 模擬與 “增” 有關(guān)的操作* 從尾部添加元素可直接通過(guò) addNode() 方法實(shí)現(xiàn)* 由于設(shè)置了頭結(jié)點(diǎn)（索引為0），從頭部插入和從中間插入的操作是一樣的* 插入的位置用 索引 描述，新結(jié)點(diǎn)進(jìn)入該位置，其后的結(jié)點(diǎn)自動(dòng)后移一位*/public void insertNode(int index, int data) {// 實(shí)例化待插入的新結(jié)點(diǎn)，傳入數(shù)據(jù)Node insertNode = new Node(90);// 用 for 定位到待插入位置的前一個(gè)結(jié)點(diǎn)Node prev = headNode;for(int i=0;i<index-1;i++) {prev = prev.next;}// 先讓待插入結(jié)點(diǎn)的指針指向指定位置原來(lái)的結(jié)點(diǎn)（紅色箭頭）insertNode.next = prev.next;// 再讓指定位置前驅(qū)結(jié)點(diǎn)的指針指向待插入的結(jié)點(diǎn)（綠色箭頭）prev.next = insertNode;}/*** 模擬與 “刪” 有關(guān)的操作* 這里采用按 位置（索引） 刪除的方式*/public void deleteNode(int index) {// 用 for 定位到待刪除位置的前一個(gè)結(jié)點(diǎn)Node prev = headNode;for(int i=0;i<index-1;i++) {prev = prev.next;}// 修改前驅(qū)結(jié)點(diǎn)的指針指向，讓其指向待刪除結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)prev.next = prev.next.next;} }

linkdemo1.java：模擬查找與插入元素的操作

package com.notes.data_structure;public class linkDemo01 {public static void main(String[] args) {/*** 準(zhǔn)備工作，實(shí)例化 MyLink類(lèi)，并添加結(jié)點(diǎn)*/MyLink mylink = new MyLink();mylink.addNode(95);mylink.addNode(85);mylink.addNode(88);mylink.addNode(93);mylink.addNode(99);/*** 模擬鏈表 “查” 的操作，打印指定數(shù)據(jù)所在鏈表位置（索引）*/mylink.searchNode(88);mylink.searchNode(100);/*** 模擬鏈表 “增” 的操作，讓插入新結(jié)點(diǎn)到指定的鏈表位置（索引）*/mylink.insertNode(3,90);// 打印所有元素，驗(yàn)證插入操作的結(jié)果mylink.printLink();} }

linkdemo2.java：模擬刪除操作

package com.notes.data_structure;public class linkDemo02 {public static void main(String[] args) {MyLink mylink = new MyLink();mylink.addNode(95);mylink.addNode(85);mylink.addNode(88);mylink.addNode(93);mylink.addNode(99);/*** 模擬鏈表 “刪” 的操作，刪除指定索引位置的元素*/mylink.deleteNode(3);// 遍歷打印驗(yàn)證刪除結(jié)果mylink.printLink();} }

?

總結(jié)

以上是生活随笔為你收集整理的数据结构学习笔记（一）：链表（linked list）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。