鏈表分為單鏈表，循環鏈表，雙向鏈表。
1，鏈表

采用鏈式方式儲存的線性表稱為鏈表，鏈表是用若干地址分散的存儲單元存儲數據元素。必須采用附加信息表示數據元素之間的邏輯關系（邏輯上相鄰結點地址-指針域）。還包含元素本身的信息-數據域。

2，單鏈表

指結點中只包含一個指針域的鏈表。單鏈表的頭指針是線性表的起始地址，是線性表中第一個數據元素的存儲地址，是單鏈表的唯一標識。單鏈表的尾結點沒有后繼節點，指針域為null。
單鏈表的結點的存儲空間是在插入和刪除過程中動態申請和釋放的，不需要預先分配，從而避免了順序表因空間不足要擴充空間或者復制元素的過程，避免了順序表因容量過大造成的資源浪費的問題，提高了運行效率和存儲空間的利用率。

Java代碼描述

/*** 2020年3月31日下午5:43:19* 線性表的抽線數據Java接口 --線性表儲存結構*/ package com.lovely.linearList;/*** @author echo lovely**/ public interface IList {void clear();boolean isEmpty();int length();Object get(int i) throws Exception; // 返回線性表數據中第i個元素void insert(int i, Object x) throws Exception; // 把x插入第i個位置void remove(int i) throws Exception;int indexOf(Object x);void display(); // 輸出線性表各個元素的值} package com.lovely.linearList;/** * 2020年4月1日下午8:25:10* * @author echo lovely** @category 節點類 用于存數據 和 后繼節點*/public class Node {public Object data; // 存放節點數據值public Node next; // 存放后繼節點public Node() {this(null, null);}// 只有節點值的構造函數public Node(Object data) {this(data, null);}// 帶有節點值和后繼節點的構造函數public Node(Object data, Node next) {this.data = data;this.next = next;} }

實現鏈表功能

package com.lovely.linearList;import java.util.Scanner;/*** @author echo lovely** 2020年4月1日下午8:32:46* * 單鏈表的一系列操作*/public class LinkedList implements IList {public Node head; // 單鏈表的頭指針public LinkedList() {this.head = new Node(); // 初始化 頭節點}// 構造長度為n的單鏈表public LinkedList(int n, boolean order) {this();if (order) create1(n);elsecreate2(n);}public void create1(int n) {// 用尾插法順序建立單鏈表 n為單鏈表長度Scanner sc = new Scanner(System.in);for (int i = 0; i < n; i ++) {try {insert(0, sc.nextInt());} catch (Exception e) {e.printStackTrace();sc.close();}}}public void create2(int n) {// 用頭插法逆序建立單鏈表Scanner sc = new Scanner(System.in);for (int i = 0; i < n; i ++) {try {insert(length(), sc.nextInt());} catch (Exception e) {e.printStackTrace();sc.close();}}}@Overridepublic void clear() {// 將鏈表置空head.data = null;head.next = null; // 后繼節點置空}@Overridepublic boolean isEmpty() {// 判斷鏈表是否 是 空return head.next == null;}@Overridepublic int length() {// 鏈表長度Node p = head.next; // p 指向單鏈表的首結點int length = 0;while (p != null) {p = p.next; // 下個節點length ++;}return length;}@Overridepublic Object get(int i) throws Exception {Node p = head.next; // p指向單鏈表的首結點int j;// 從首結點開始向后查找 直到p指向第i個節點 或者結點為 nullfor (j = 0; j < i && p != null; j ++) {p = p.next;}if (j > i || p == null)throw new Exception("第" + i + "數據元素不存在");return p.data;}@Overridepublic void insert(int i, Object x) throws Exception {Node p = head; // 頭指針int j = -1;// 尋找第i個節點的前驅while (p != null && j < i - 1) {p = p.next;j ++;}if (j > i - 1 || p == null)throw new Exception("插入位置不合法");// 創建結點Node s = new Node(x);s.next = p.next;p.next = s;}@Overridepublic void remove(int i) throws Exception {Node p = head;int j = -1;// 尋找第i個結點的前驅結點while (p != null && j < i - 1) {p = p.next;j ++;}if (j > i - 1 || p.next == null)throw new Exception("刪除位置不合法");p.next = p.next.next;}@Overridepublic int indexOf(Object x) {Node p = head.next; int j = 0;while (p != null && !p.data.equals(x)) { // 數據元素存在，沒查找到下個結點繼續找p = p.next;j ++;}if (p == null)return -1;return j;}@Overridepublic void display() {Node p = head.next;while (p != null) {System.out.print(p.data + " ");p = p.next;}System.out.println();}}

測試

package com.lovely.linearList;import java.util.Scanner;public class TestLinkedList {public static void main(String[] args) {LinkedList list = new LinkedList(5, true);int i = list.indexOf(3);System.out.println(i);list.display();}static void showInsert() {int n,val;Scanner sc = new Scanner(System.in);System.out.println("請輸入元素數組的個數：");n = sc.nextInt();LinkedList l = new LinkedList(); // 聲明單鏈表for (int i = 0; i < n; i++) {Node q = l.head;System.out.print("輸入" + (i + 1) + "個元素的值: ");val = sc.nextInt();Node p = new Node(val);while (q != null && q.next != null && Integer.valueOf(q.next.data.toString()) < val) {q = q.next; }p.next = q.next; // 插入操作q.next = p;}Node k = l.head;for (int i = 0; i < n; i++) {k = k.next;System.out.println(k.data);}sc.close();}}

3，循環鏈表

鏈表首尾相連，尾結點的指針域指向頭節點，環狀的鏈表。

4，雙向鏈表

有兩個指針域，一個指針指向前驅結點，一個指針指向后繼結點，查找快。

😵😵😵😵

比較順序表和鏈表
順序表查找快捷，靠下標。插入，刪除效率低，需要移動很多數據。
鏈表插入，刪除效率高，動態對儲存空間分配。儲存密度低，不可按照下標存取。查找遍歷慢。

總結

以上是生活随笔為你收集整理的线性表----链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。