那么我们正式踏入了对数据结构的学习 本篇博客教大家学习单链表 以下为代码实现的思维导图 单链表.png

本篇代码较多,我会在代码块中,进行许多的注释讲解,想要理解清楚的小伙伴一定要点开来耐心看完哦

单链表的概念

image.png

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

image.png
链式的结构分为一个一个节点,什么是节点呢?

节点:

  1. 数值域
  2. next域(可以理解为指针域或是引用域)

image.png

注意:👇

  1. 那么我们在下面的图中可以看出,链式结构在逻辑上是连续的,但是在物理上不一定连续
  2. 现实中的节点一般都是从堆上申请的
  3. 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续,下图中的0×11,0×12就是连续的特殊情况

1651457344847.jpg
这样单向,带头,非循环的,我们称其中的节点为傀儡节点,那么什么是双向呢?
1651458216428.jpg
那么什么是不带头的呢?,就是没有数值域为空的节点
那么什么是循环呢?就是最后的next域不指向null,而是指向首节点,构成循环
image.png

这些条件排列组合一下会产生许许多多的链表,但我们常用的链表主要是以下两种:

  1. 无头单项肺循环链表:结构比较简单,一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构。

[Java实现数据结构]-单链表 - 图8

  1. 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

1651458216428.jpg

单链表的实现

  1. /**
  2. * @author Gremmie102
  3. * @date 2022/4/28 9:24
  4. * @purpose :单链表的实现
  5. */
  6. public class MySingleList {
  7. static class ListNode {
  8. public int val;//数值域
  9. public ListNode next;//存储下一个节点的地址
  10. public ListNode(int val) {
  11. this.val = val;
  12. }
  13. }
  14. public ListNode head;//代表单链表的头结点的引用
  15. /**
  16. * 这里只是简单的进行,链表的构造。
  17. */
  18. public void createList() {
  19. ListNode listNode1 = new ListNode(12);
  20. ListNode listNode2 = new ListNode(23);
  21. ListNode listNode3 = new ListNode(34);
  22. ListNode listNode4 = new ListNode(45);
  23. ListNode listNode5 = new ListNode(56);
  24. listNode1.next = listNode2;
  25. listNode2.next = listNode3;
  26. listNode3.next = listNode4;
  27. listNode4.next = listNode5;
  28. this.head = listNode1;
  29. }
  30. public void display() {
  31. ListNode cur = head;
  32. while (cur != null) {
  33. System.out.print(cur.val+" ");
  34. cur = cur.next;
  35. }
  36. System.out.println();
  37. }
  38. /**
  39. * 头插法
  40. * O(1)
  41. */
  42. public void addFirst(int data){
  43. ListNode node = new ListNode(data);
  44. /*if(this.head == null) {
  45. this.head = node;
  46. }else {
  47. node.next = this.head;
  48. this.head = node;
  49. }*/
  50. node.next = this.head;
  51. this.head = node;
  52. }
  53. //尾插法 O(n)
  54. public void addLast(int data) {
  55. ListNode node = new ListNode(data);
  56. if(head == null) {
  57. head = node;
  58. }else {
  59. ListNode cur = head;
  60. while (cur.next != null) {
  61. cur = cur.next;
  62. }
  63. //cur.next == null;
  64. cur.next = node;
  65. }
  66. }
  67. /**
  68. * 任意位置插入,第一个数据节点为0号下标
  69. * 指定位置插入
  70. */
  71. public void addIndex(int index,int data) throws MySingleListIndexOutOfException{
  72. checkIndexAdd(index);
  73. if(index == 0) {
  74. addFirst(data);
  75. return;
  76. }
  77. if(index == size()) {
  78. addLast(data);
  79. return;
  80. }
  81. ListNode node = new ListNode(data);
  82. ListNode cur = findIndexSubOne(index);
  83. node.next = cur.next;
  84. cur.next = node;
  85. }
  86. /**
  87. * 找到index-1位置的节点
  88. * @param index
  89. * @return 该节点的地址
  90. */
  91. private ListNode findIndexSubOne(int index) {
  92. ListNode cur = this.head;
  93. while (index-1 != 0) {
  94. cur = cur.next;
  95. index--;
  96. }
  97. return cur;
  98. }
  99. private void checkIndexAdd(int index) {
  100. if(index < 0 || index > size()) {
  101. throw new MySingleListIndexOutOfException("任意位置插入的时候,index不合法!");
  102. }
  103. }
  104. //查找是否包含关键字key是否在单链表当中 314
  105. public boolean contains(int key) {
  106. //head == null
  107. ListNode cur = this.head;
  108. //cur != null 说明 没有遍历完 链表
  109. while (cur != null) {
  110. if(cur.val == key) {
  111. return true;
  112. }
  113. cur = cur.next;
  114. }
  115. return false;
  116. }
  117. //删除第一次出现关键字为key的节点
  118. public void remove(int key){
  119. if(this.head == null) {
  120. System.out.println("此时链表为空,不能进行删除!");
  121. return;
  122. }
  123. if(this.head.val == key) {
  124. //判断 第一个节点是不是等于我要删除的节点
  125. this.head = this.head.next;
  126. return;
  127. }
  128. ListNode cur = this.head;
  129. while (cur.next != null) {
  130. if(cur.next.val == key) {
  131. //进行删除了
  132. ListNode del = cur.next;
  133. cur.next = del.next;
  134. return;
  135. }
  136. cur = cur.next;
  137. }
  138. }
  139. //删除所有值为key的节点
  140. public void removeAllKey(int key){
  141. while(true){
  142. remove(key);
  143. if (this.contains(key)){
  144. continue;
  145. }else break;
  146. }
  147. }
  148. //得到单链表的长度
  149. public int size(){
  150. int count = 0;
  151. ListNode cur = this.head;
  152. while (cur != null) {
  153. count++;
  154. cur = cur.next;
  155. }
  156. return count;
  157. }
  158. public void clear(){
  159. this.head = null;
  160. }
  161. }

LinkedList

那么上面的代码是我们自己实现的单链表。
在Java中,已经有大佬帮我们写好了单链表,叫做LinkedList

使用方式

image.png

方法

method explain
void add(int index, E element) 将 e 插入到 index 位置
boolean add(E e) 尾插 e
boolean addAll(Collection c) 尾插 c 中的元素
E remove(int index) 删除 index 位置元素
boolean remove(Object o) 删除遇到的第一个 o
E get(int index) 获取下标 index 位置元素
E set(int index, E element) 将下标 index 位置元素设置为 element
void clear() 清空
boolean contains(Object o) 判断 o 是否在线性表中
int lastIndexOf(Object o) 返回最后一个 o 的下标
int indexOf(Object o) 返回第一个 o 所在下标
List subList(int fromIndex, int toIndex) 截取部分 list
  1. public static void main(String[] args) {
  2. LinkedList<Integer> list = new LinkedList<>();
  3. list.add(1);
  4. // add(elem): 表示尾插
  5. list.add(2);
  6. list.add(3);
  7. list.add(4);
  8. list.add(5);
  9. list.add(6);
  10. list.add(7);
  11. System.out.println(list.size());
  12. System.out.println(list);
  13. // 在起始位置插入0
  14. list.add(0, 0); // add(index, elem): 在index位置插入元素elem
  15. System.out.println(list);
  16. list.remove(); // remove(): 删除第一个元素,内部调用的是removeFirst()
  17. list.removeFirst(); // removeFirst(): 删除第一个元素
  18. list.removeLast(); // removeLast(): 删除最后元素
  19. list.remove(1); // remove(index): 删除index位置的元素
  20. System.out.println(list);
  21. // contains(elem): 检测elem元素是否存在,如果存在返回true,否则返回false
  22. if(!list.contains(1)){
  23. list.add(0, 1);
  24. }
  25. list.add(1);
  26. System.out.println(list);
  27. System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
  28. System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
  29. int elem = list.get(0); // get(index): 获取指定位置元素
  30. list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
  31. System.out.println(list);
  32. // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
  33. List<Integer> copy = list.subList(0, 3);
  34. System.out.println(list);
  35. System.out.println(copy);
  36. list.clear(); // 将list中元素清空
  37. System.out.println(list.size());
  38. }

链表后续还会更新题目,大家拭目以待
最近临近考试,学习任务繁重
如果文章有哪里不足的地方麻烦大佬指出
感谢阅读~