转载声明：文章来源https://blog.csdn.net/qq_53869058/article/details/129642201?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522bf08e343b1a4223aad78833de9b80b37%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=bf08e343b1a4223aad78833de9b80b37&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-4-129642201-null-null.142^v101^pc_search_result_base6&utm_term=java%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8&spm=1018.2226.3001.4187
1. ArrayList的缺陷
由于其底层是一段连续空间，当 在 ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后 搬移，时间复杂度为 O(n) ，效率比较低，因此 ArrayList 不适合做任意位置插入和删除比较多的场景 。因此： java集合中又引入了LinkedList ，即链表结构。
2. 链表
2.1 链表的概念及结构
链表是一种 物理存储结构上非连续 存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。
实际中链表的结构非常多样，以下情况组合起来就有6 种链表结构：
（1） 单向或者双向
（2） 带头或者不带头
（3）循环或者非循环
虽然有这么多的链表的结构，但是我们重点掌握两种 :
无头单向非循环链表 ： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结构 ，如哈希桶、图的邻接表等等。
无头双向链表 ：在 Java 的集合框架库中 LinkedList 底层实现就是无头双向循环链表。
2.2 接口的实现
使用泛型更好的接收不同数据类型（一个顺序表只能接受一种类型！）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | public interface SeqList<E> { // 尾插 void add(E element); // 将 element 插入到 index 位置 void add(int index,E element); // 删除 index 位置元素<返回删除的值 E removeByIndex(int index); // 删除第一个值element的元素 void removeByValue(E element); // 删除所有值element的元素 void removeAllValue(E element); // 将下标 index 位置元素设置为 element，返回替换前的值 E set(int index,E element); E get(int index); // 判断 o 是否在其中 boolean contains(E element); int indexOf(E element); int size(); void clear(); } |
3. 动手实现单链表
实现没有头节点的单链表
3.1 重写SeqList接口方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | public class SingleLinkedList<E> implements SeqList<E> { private Node head;//头节点 private int size; // 节点个数，保存的元素个数 //类的定义，内部类,对外部完全隐藏 private class Node { E val;//保存的元素 Node next;//下节车厢的位置 Node(E val) { this.val = val; } } public void addFrist(E val){ } @Override public void add(E element) { } @Override public void add(int index, E element) { } @Override public E removeByIndex(int index) { } @Override public void removeByValue(E element) { } @Override public void removeAllValue(E element) { } @Override public E set(int index, E element) { } public boolean rangeCheck(int index){ } @Override public E get(int index) { } @Override public boolean contains(E element) { } @Override public int indexOf(E element) { } @Override public int size() { } @Override public void clear() { } @Override public String toString() { }} |
3.2 在当前链表头部添加节点（头插）
无论链表中是否包含节点，头插法都是这相同的代码处理~
1 2 3 4 5 6 7 8 9 10 11 12 13 | public void addFrist(E val){ // 要插入一个元素，首先要产生一个新节点 Node node = new Node(val); // 将当前节点插入到链表中 node.next = head; // 更新head的引用，指向当前的新节点 head = node; size ++; } public void add(E element) { add(size,element); } |
思考一下，①和②的代码顺序能换吗?
先执行2再执行1，原来的链表就丢了，head指向新节点，最终链表中只剩下新节点了~
3.3 在 第index位置添加节点（任意位置）
（1）判断index是否合法
（2）判断没有前驱，没有就是头插
（3）寻找index位置的前驱节点（单链表的核心操作就是在寻找前驱节点!）
（4）先将新节点和原先位置节点连接
（5）再更改原先prev的引用
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public void add(int index, E element) { // 1.base case，边界判断 if (index < 0 || index > size) { throw new IllegalArgumentException("add index illegal!"); } // 2.判断没有前驱的情况 if (index == 0) { addFrist(element); return; } // 3.确实是中间位置的插入，寻找待插入位置的前驱！ Node prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } // prev走到待插入位置的前驱 Node node = new Node(element); node.next = prev.next; prev.next = node; size ++; } |
3.4 在当前链表尾部添加节点（尾插）
第一种方法
（1）走到当前链表的最后
（2）让最后节点的next指向这个新添加的节点
第二种方法
调用add()方法，index等于size就是在链表末尾插入了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public void addLast(E val){ Node prev = head; while (prev.next != null){ prev = prev.next; } Node node = new Node(val); prev.next = node; } //尾插2 @Override public void add(E element) { add(size,element); } |
3.5 删除第index个节点
（1）判断index是否合法（链表为空则index不合法）
（2）判断没有前驱，没有就是头节点删除
（3）寻找index位置的前驱节点
（4）将前驱节点和原先位置的下一个节点连接
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | public E removeByIndex(int index) { // 1.base case if (!rangeCheck(index)) { throw new IllegalArgumentException("remove index illegal!"); } // 2.判断头节点的删除问题 if (index == 0) { Node node = head; head = head.next; node.next = null; size --; return node.val; } // 3.现在确实是中间位置的删除 Node prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } Node node = prev.next; prev.next = node.next; node.next = null; size --; return node.val; } |
3.6 检验index是否合法
1 2 3 4 5 6 | public boolean rangeCheck(int index){ if (index < 0 || index >= size) { return false; } return true; } |
3.7 删除第一个值element的节点
（1）判断链表是否为空
（2）判断头节点是否是待删除的节点，是的话删除完就方法返回
（3）找element节点的前驱节点（凡是用到引用的位置，一定要保证这个引用不为空）
（4）将前驱节点和原先位置的下一个节点连接
这里的图和3.5 中的图一致
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | public void removeByValue(E element) { // 1.base case if (head == null) { return; } // 2.判断头节点恰好是待删除的节点 if (head.val.equals(element)) { head = head.next; size --; return; } // 3.此时头节点不为空其一定不是待删除的结点 Node prev = head; while (prev.next != null) { if (prev.next.val.equals(element)) { // prev走到了待删除节点的前驱位置 prev.next = prev.next.next; size --; return; } prev = prev.next; } // 4.链表中没有待删除的节点 System.out.println("当前链表中不存在值为" + element + "的节点"); } |
3.8 删除所有值element的节点
（1）判断链表是否为空
（2）判断头节点是否是待删除的节点
（3）判断链表是否已经删除完，删除完就返回
（4）寻找element节点的前驱节点（凡是用到引用的位置，一定要保证这个引用不为空）
（5）将前驱节点和原先位置的下一个节点连接
（6）如果下一个节点不是待删除的节点，prev指向下一个节点
（7）循环执行步骤（5）、（6）直到链表走完(prev.next != null)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | public void removeAllValue(E element) { // 1.base case if(head == null) { return; } // 2.若头节点就是待删除的节点且出现连续的待删除节点 while (head != null && head.val.equals(element)) { head = head.next; size --; } if (head == null) { // 整个链表已经删除完了 return; } // 3.头节点一定不是待删除的节点且链表不为空！ // prev一定指向的不是待删除的结点~ Node prev = head; while (prev.next != null) { if (prev.next.val.equals(element)) { // 此时prev就是待删除节点的前驱 prev.next = prev.next.next; size --; }else { // 只有后继节点不是待删除的结点才能移动prev引用! prev = prev.next; } } } |
3.9 修改第index个节点的值为element
（1）判断index是否合法
（2）寻找index位置的节点
（3）将节点的val修改为element
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public E set(int index, E element) {// 1.索引的合法性校验 if(!rangeCheck(index)){ throw new IllegalArgumentException("set index illegal!"); } // 从前向后遍历走到index对应的元素 Node x = head; for (int i = 0; i < index; i++) { x = x.next; } // 此时x就落在了待修改的节点位置 E oldVal = x.val; x.val = element; return oldVal; } public boolean rangeCheck(int index){ if (index < 0 || index >= size) { return false; } return true; } |
3.10 获取第index个节点的值
1 2 3 4 5 6 7 8 9 10 | public E get(int index) { if(!rangeCheck(index)){ throw new IllegalArgumentException("get index illegal!"); } Node x = head; for (int i = 0; i < index; i++) { x = x.next; } return x.val; } |
3.11 判断链表中是否存在element
1 2 3 4 5 6 7 8 9 | public boolean contains(E element) { Node cur = head; while (cur.next != null){ if (cur.val.equals(element)){ return true; } } return false; } |
3.12 获取element在链表中的位置
1 2 3 4 5 6 7 8 9 10 11 12 | public int indexOf(E element) { int count = 0; Node cur = head; while (cur.next != null){ if (cur.val.equals(element)){ return count; } count++; cur = cur.next; } return -1; } |
3.13 打印链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | public String toString() { StringBuilder sb = new StringBuilder(); // 从当前链表的第一个节点开始向后遍历，直到走到尾结点为止 // 第一个节点head for(Node x = head;x != null;x = x.next){ sb.append(x.val); sb.append("->"); if(x.next == null){ // 此时temp走到了尾结点 sb.append("NULL"); } } return sb.toString(); } |
3.14 获取链表长度以及清空链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public int size() { return this.size; } @Override public void clear() { Node cur = this.head; Node curNext = null; while (cur != null) { curNext = cur.next; cur.next = null; cur = curNext; } head = null; } |
4. SingleLinkedList整体实现
4.1 SingleLinkedList类
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 | public class SingleLinkedList<E> implements SeqList<E> { private Node head;//头节点 private int size; // 车厢节点个数，保存的元素个数 //车厢类的定义，车厢作为火车的内部类,对外部完全隐藏 private class Node { E val;//保存的元素 Node next;//下节车厢的位置 Node(E val) { this.val = val; } } // ------------------------------------------------ // 头插，在当前链表头部添加元素 head在移动 public void addFrist(E val){ // 要插入一个元素，首先要产生一个新节点 Node node = new Node(val); // 将当前节点插入到链表中 node.next = head; // 更新head的引用，指向当前的新节点 head = node; size ++; } @Override public void add(E element) { add(size,element); } @Override public void add(int index, E element) { // 1.base case，边界判断 if (index < 0 || index > size) { throw new IllegalArgumentException("add index illegal!"); } // 2.判断没有前驱的情况 if (index == 0) { addFrist(element); return; } // 3.确实是中间位置的插入，寻找待插入位置的前驱！ Node prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } // prev走到待插入位置的前驱 Node node = new Node(element); node.next = prev.next; prev.next = node; size ++; } @Override public E removeByIndex(int index) { // 1.base case if (!rangeCheck(index)) { throw new IllegalArgumentException("remove index illegal!"); } // 2.判断头节点的删除问题 if (index == 0) { Node node = head; head = head.next; node.next = null; size --; return node.val; } // 3.现在确实是中间位置的删除 Node prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } Node node = prev.next; prev.next = node.next; node.next = null; size --; return node.val; } @Override public void removeByValue(E element) { // 1.base case if (head == null) { return; } // 2.判断头节点恰好是待删除的节点 if (head.val.equals(element)) { head = head.next; size --; return; } // 3.此时头节点不为空其一定不是待删除的结点 Node prev = head; while (prev.next != null) { if (prev.next.val.equals(element)) { // prev走到了待删除节点的前驱位置 prev.next = prev.next.next; size --; return; } prev = prev.next; } // 4.链表中没有待删除的节点 System.out.println("当前链表中不存在值为" + element + "的节点"); } @Override public void removeAllValue(E element) { // 1.base case if(head == null) { return; } // 2.若头节点就是待删除的节点且出现连续的待删除节点 while (head != null && head.val.equals(element)) { head = head.next; size --; } if (head == null) { // 整个链表已经删除完了 return; } // 3.头节点一定不是待删除的节点且链表不为空！ // prev一定指向的不是待删除的结点~ Node prev = head; while (prev.next != null) { if (prev.next.val.equals(element)) { // 此时prev就是待删除节点的前驱 prev.next = prev.next.next; size --; }else { // 只有后继节点不是待删除的结点才能移动prev引用! prev = prev.next; } } } // 修改 @Override public E set(int index, E element) {// 1.索引的合法性校验 if(!rangeCheck(index)){ throw new IllegalArgumentException("set index illegal!"); } // 从前向后遍历走到index对应的元素 Node x = head; for (int i = 0; i < index; i++) { x = x.next; } // 此时x就落在了待修改的节点位置 E oldVal = x.val; x.val = element; return oldVal; } public boolean rangeCheck(int index){ if (index < 0 || index >= size) { return false; } return true; } @Override public E get(int index) { if(!rangeCheck(index)){ throw new IllegalArgumentException("get index illegal!"); } Node x = head; for (int i = 0; i < index; i++) { x = x.next; } return x.val; } @Override public boolean contains(E element) { Node cur = head; while (cur.next != null){ if (cur.val.equals(element)){ return true; } } return false; } @Override public int indexOf(E element) { int count = 0; Node cur = head; while (cur.next != null){ if (cur.val.equals(element)){ return count; } count++; cur = cur.next; } return -1; } @Override public int size() { return this.size; } @Override public void clear() { Node cur = this.head; Node curNext = null; while (cur != null) { curNext = cur.next; cur.next = null; cur = curNext; } head = null; } @Override public String toString() { StringBuilder sb = new StringBuilder(); // 从当前链表的第一个节点开始向后遍历，直到走到尾结点为止 // 第一个节点head for(Node x = head;x != null;x = x.next){ sb.append(x.val); sb.append("->"); if(x.next == null){ // 此时temp走到了尾结点 sb.append("NULL"); } } return sb.toString(); }} |
4.2 Test类
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | public class SingleLinkedTest { public static void main(String[] args) { SingleLinkedList<Integer> list = new SingleLinkedList<>(); list.add(1); list.add(2); list.add(3); list.add(9); list.add(10); list.add(10); list.add(6); list.add(10); list.add(5); list.add(7); list.add(10); list.add(10); System.out.println(list); System.out.println("------------添加测试-----------"); System.out.println("从链表尾部添加99"); list.add(99); System.out.println("添加index为2，element为88"); list.add(2,88); System.out.println(list); System.out.println("-----------删除测试------------"); System.out.println("删除index为0"); list.removeByIndex(0); System.out.println("删除元素为6"); list.removeByValue(6); System.out.println("删除所有10"); list.removeAllValue(10); System.out.println(list); System.out.println("-----------其他------------"); System.out.println("查看是否包含10这个元素"); System.out.println(list.contains(10)); System.out.println("修改index为3，element为19"); list.set(3,19); System.out.println("获取index为3的元素"); System.out.println(list.get(3)); System.out.println(list); System.out.println("获取element为88的index"); System.out.println(list.indexOf(88)); System.out.println("获取顺序表长度"); System.out.println(list.size()); System.out.println("清空顺序表"); list.clear(); System.out.println(list + "..."); }} |
4.3 测试结果
帖子还没人回复快来抢沙发