链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
如下图所示，假设要存储线性表a={1, 2, 3}，如果通过链表的方式存储则可以不考虑：1）物理空间是否连续；2）元素之间是否顺序。而是通过【指针】的方式来显式指定各个元素之间的相对位置关系即可。
链表中的数据元素在内存中的存储位置是非连续、非顺序的。
1）优点：相比顺序存储结构，链表的增删改更加灵活，只需要更改当前数据元素附近的数据及指针即可，时间复杂度位O(1)；对空间的利用更加灵活；
2）缺点：查询慢，每个数据元素的位置，都需要从链表起始位置开始遍历，时间复杂度O(n)；空间利用率低，容易造成存储碎片化；需要额外的指针来指明相对位置，空间成本较高。
1）节点、数据域&指针域
首先，链表实现数据元素在物理存储中随机，同时元素间又保持逻辑位置关系的秘诀，在于链表中每个数据元素附带了指针。具体而言，链表中的每个数据元素被设计成一个节点，每个节点由数据域和指针域构成，如下图（单向链表的节点）所示：
2）链式结构
我们以线性表的单向链式存储结构为例，说明链表中元素的位置结构。如下图所示：
尾节点的指针指向null。
我们这里只考虑线性表的链式存储结构，可以分为以下几种类型：
单向链表、双向链表、单向循环链表、双向循环链表。
这里以单向链表为例，进行java代码实现，双向及循环链表将在后面的文章中学习和介绍。
要点：
1）设计节点类
2）初始化的时候需要先new一个数据域为空的头节点
1 public class MLinkList { 2 /** 3 * 节点 4 */ 5 public class Node<E> { 6 /* 数据域 */ 7 public E data; 8 /* 单向链表的指针域指向下一个节点 */ 9 public Node next; 10 11 public Node(E data) { 12 this.data = data; 13 } 14 } 15 16 /* 头节点 */ 17 private Node head; 18 19 /** 20 * 初始化单向链表 21 */ 22 public MLinkList() { 23 head = new Node(null); // 头节点数据域为空 24 } 25 }
操作如下，时间复杂度为O(1)
操作如下，时间复杂度为O(1)
只需要修改数据域的值即可，时间复杂度为O(1)
需要从起始节点开始遍历链表，时间复杂度为O(n)
1 package com.lrspace.learn.ds.list; 2 3 /** 4 * Author: llx 5 * Description: 单向链表（首元节点的下标是0） 6 * Date: 2021/2/16 7 */ 8 public class MLinkList<E> { 9 /** 10 * 节点 11 */ 12 public class Node<E> { 13 /* 数据域 */ 14 public E data; 15 /* 单向链表的指针域指向下一个节点 */ 16 public Node next; 17 18 public Node(E data) { 19 this.data = data; 20 } 21 } 22 23 /* 头节点 */ 24 private Node head; 25 /* 当前数据元素个数 */ 26 private int size; 27 28 /** 29 * 初始化单向链表（首元节点的下标是0） 30 */ 31 public MLinkList() { 32 head = new Node(null); // 头节点数据域为空 33 size = 0; 34 } 35 36 /** 37 * 在末尾添加数据元素 38 * 39 * @param data 待添加的数据元素 40 */ 41 public void add(E data) { 42 Node tmp = new Node(data); 43 Node cur = head; 44 while (cur.next != null) { 45 cur = cur.next; 46 } 47 cur.next = tmp; 48 size++; 49 } 50 51 /** 52 * 插入数据元素 53 * 54 * @param pos 待插入的位置 55 * @param data 待插入的数据 56 */ 57 public void insert(int pos, E data) { 58 if (pos >= size || pos < 0) { 59 throw new IllegalArgumentException("error: the input pos " + pos + " is exceed the bound."); 60 } 61 Node tmp = new Node(data); 62 Node cur = head; 63 if (pos == 0) { 64 cur = cur.next; 65 head.next = tmp; 66 tmp.next = cur; 67 return; 68 } 69 for (int i = 0; i < pos; i++) { 70 cur = cur.next; 71 } 72 Node curNext = cur.next; 73 cur.next = tmp; 74 tmp.next = curNext; 75 size++; 76 } 77 78 /** 79 * 删除数据元素 80 * 81 * @param pos 待删除数据元素的位置 82 */ 83 public void delete(int pos) { 84 if (pos >= size || pos < 0) { 85 throw new IllegalArgumentException("error: the input pos " + pos + " is exceed the bound."); 86 } 87 if (pos == 0) { 88 head.next = head.next.next; 89 return; 90 } 91 Node cur = head; 92 for (int i = 0; i < pos; i++) { 93 cur = cur.next; 94 } 95 Node curNext = cur.next; 96 cur.next = curNext.next; 97 size--; 98 } 99 100 /** 101 * 更新数据元素 102 * 103 * @param pos 待更新数据元素的位置 104 * @param data 待更新数据元素的目标值 105 */ 106 public void update(int pos, E data) { 107 if (pos >= size || pos < 0) { 108 throw new IllegalArgumentException("error: the input pos " + pos + " is exceed the bound."); 109 } 110 Node cur = head; 111 for (int i = 0; i < pos + 1; i++) { 112 cur = cur.next; 113 } 114 cur.data = data; 115 } 116 117 /** 118 * 查询数据元素 119 * 120 * @param pos 带查询数据元素的位置 121 * @return 查询出的数据元素 122 */ 123 public E select(int pos) { 124 if (pos >= size || pos < 0) { 125 throw new IllegalArgumentException("error: the input pos " + pos + " is exceed the bound."); 126 } 127 Node cur = head; 128 for (int i = 0; i < pos + 1; i++) { 129 cur = cur.next; 130 } 131 return (E) cur.data; 132 } 133 134 @Override 135 public String toString() { 136 StringBuilder out = new StringBuilder(); 137 out.append("["); 138 Node cur = head; 139 for (int i = 0; i < size; i++) { 140 cur = cur.next; 141 out.append(cur.data.toString()); 142 out.append(", "); 143 } 144 if (size > 0) { 145 out.delete(out.length() - 2, out.length()); 146 } 147 out.append("]"); 148 return out.toString(); 149 } 150 }
1 package com.lrspace.learn.ds.list; 2 3 import org.junit.Test; 4 5 import static org.junit.Assert.*; 6 7 public class MLinkListTest { 8 9 @Test 10 public void test() { 11 /* 初始化单向链表 */ 12 MLinkList<String> mLinkList = new MLinkList<>(); 13 System.out.println("单向链表初始化: " + mLinkList.toString()); 14 /* 在末尾添加数据元素 */ 15 mLinkList.add("first"); 16 System.out.println("在末尾添加数据元素1: " + mLinkList.toString()); 17 mLinkList.add("third"); 18 System.out.println("在末尾添加数据元素3: " + mLinkList.toString()); 19 /* 插入数据元素 */ 20 mLinkList.insert(1, "second"); 21 System.out.println("插入数据元素: " + mLinkList.toString()); 22 /* 删除数据元素 */ 23 mLinkList.delete(1); 24 System.out.println("删除数据元素: " + mLinkList.toString()); 25 /* 更新数据元素 */ 26 mLinkList.update(1, "second"); 27 System.out.println("更新数据元素: " + mLinkList.toString()); 28 /* 查询数据元素 */ 29 System.out.println("查询数据元素，位置0: " + mLinkList.select(0)); 30 System.out.println("查询数据元素，位置1: " + mLinkList.select(1)); 31 } 32 }
输出结果：
单向链表初始化: []
在末尾添加数据元素1: [first]
在末尾添加数据元素3: [first, third]
插入数据元素: [first, second, third]
删除数据元素: [first, third]
更新数据元素: [first, second]
查询数据元素，位置0: first
查询数据元素，位置1: second
1）百度百科：https://baike.baidu.com/item/%E9%93%BE%E8%A1%A8/9794473?fr=aladdin
2）南孚先生的博客：https://www.cnblogs.com/782687539-nanfu/p/10333031.html
3）解学武的教程：http://data.biancheng.net/view/160.html
原文：https://www.cnblogs.com/llxrl/p/14407804.html