思维导图：
1.List的介绍和使用：
- List是一个接口不能直接实例化，List继承于Collection。
- List是一个线性表，是有相同类型元素的有限序列。
- ArrayList和LinkedList都实现了List接口。
//只能访问 List 当中的方法
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new LinkedList<>();
List<Integer> list3 = new Stack<>();
//可以访问接口中的方法，也可以访问自己类中的方法
ArrayList<Integer> list4 = new ArrayList<>();
LinkedList<Integer> list5 = new LinkedList<>();
Stack<Integer> list6 = new Stack<>();
2.线性表：
- 线性表是有多个相同特性元素的有限序列，在数据结构中广泛使用。常见的线性表有数组、顺序表、链表、栈和队列等。
- 线性表的结构特点。从逻辑结构和物理结构上来说，在逻辑上是线性结构，类似于一条直线。而在物理上也可以称为内存上，确是不一定连续的，比如连续的有顺序表，链式结构的有链表。
- 线性表的存储方式有顺序存储和链式存储。
3.ArrayList：
- ArrayList是一个类，实现了List接口。
- ArrayList是一个动态类型的顺序表，体现在增加元素时会自动发生扩容。
- ArrayList底层是一块连续的内存空间，就是采用数组的存储形式，其背后就是一个数组。
- 如果创建了一个ArrayList但是没有指定容量的话，这个顺序表默认的大小为0，当add ();元素时ArraysList就会扩容到10，以后每次按照1.5倍扩容。例如：原来大小是10，扩容后变成15。
- 检测到要扩容时会调用grow方法，源码中是调用copyOf进行扩容。
- ArrayList有3种创建方法
| 3种创建方法 | 说明 |
| List<Integer> list1 = new ArrayList<>()； | 推荐写法 |
| List<Integer> list2 = new ArrayList<>(66)； | 可以指定顺序表的容量 |
| List<Integer> list3 = new ArrayList<>(list2)； | List3中的元素和list2一样 |
- ArrayList的模拟实现
1. public class MyArrayList { 2. 3. public int[] elem; 4. public int usedSize;//当前顺序表中元素的个数 5. private static final int DEFAULT_CAPACITY = 10;//给定一个默认的容量 6. 7. public MyArrayList(){ 8. elem = new int[DEFAULT_CAPACITY]; 9. } 10. 11. //打印顺序表 12. public void diaplay(){ 13. for (int i = 0; i < usedSize; i++) { 14. System.out.print(elem[i]+" "); 15. } 16. System.out.println(); 17. } 18. //判断顺序表有没有满 19. private boolean isFull(){ 20. return usedSize == elem.length; 21. } 22. 23. //增加元素时检查下标是否合法 24. private void checkPos1(int pos) { 25. if(pos < 0 || pos > usedSize){ 26. return; 27. } 28. } 29. 30. //修改查找元素时检查下标是否合法 31. private void checkPos2(int pos){ 32. if(pos<0 || pos >= usedSize){ 33. return; 34. } 35. } 36. //增加元素（尾插） 37. public void add(int data){ 38. if(isFull()){ 39. elem = Arrays.copyOf(elem,elem.length*2); 40. } 41. elem[usedSize] = data; 42. usedSize++; 43. } 44. 45. //在pos位置上增加元素 46. public void add(int pos,int data){ 47. checkPos1(pos); 48. if(isFull()){ 49. elem = Arrays.copyOf(elem,elem.length*2); 50. } 51. //注意是 i>=pos 52. for (int i = usedSize-1; i >= pos; i--) { 53. elem[i+1] = elem[i]; 54. } 55. elem[pos] = data; 56. usedSize++; 57. } 58. 59. //判断是否包含某个元素 60. public boolean contains(int data){ 61. //i最多会走到usedSize的前一个元素，所以usedSize不用-1 62. for (int i = 0; i < usedSize; i++) { 63. if(data == elem[i]){ 64. return true; 65. } 66. } 67. return false; 68. } 69. 70. //找到某个元素的下标 71. public int indexOf(int data){ 72. for (int i = 0; i < usedSize; i++) { 73. if(data == elem[i]){ 74. return i; 75. } 76. } 77. return -1; 78. } 79. 80. //获取pos下标的元素 81. public int get(int pos){ 82. checkPos2(pos); 83. return elem[pos]; 84. } 85. 86. //将pos位置的值改成value 87. public void set(int pos,int value){ 88. checkPos2(pos); 89. elem[pos] = value; 90. } 91. 92. //删除第一次出现的关键字key 93. public void remove(int key){ 94. int index = indexOf(key); 95. if(index == -1){ 96. System.out.println("找不到这个数字"); 97. } 98. checkPos2(index); 99. //这里注意一下：一定要-1 100. for (int i = index; i < usedSize-1; i++) { 101. elem[i] = elem[i+1]; 102. } 103. usedSize--; 104. } 105. 106. //获取顺序表的长度 107. public int size(){ 108. /*int count = 0; 109. for (int i = 0; i < usedSize; i++) { 110. count++; 111. } 112. return count;*/ 113. return usedSize; 114. } 115. 116. //清空顺序表 117. public void clear(){ 118. /*for (int i = 0; i < usedSize; i++) { 119. elem[i]=null; 120. }*/ 121. usedSize = 0; 122. } 123. 124. }
4.ArrayList的常见操作：
- 增加元素
| 增加元素 | 说明 |
| add（x）； | 尾插元素x |
| add（index，x）； | 将元素x插入到下标为index的位置 |
| addAll（c）； | 将c中的元素插入到顺序表的末尾 |
- 删除元素
| 删除元素 | 说明 |
| remove（index）； | 删除index处的下标 |
| remove（x）; | 删除第一个元素为x |
| clear（）； | 清空顺序表 |
- 查找元素
| 查找元素 | 说明 |
| get（index）； | 获取下标为index的元素 |
| contains（x）; | 判断元素x是否在顺序表中 |
| indexOf（x）; | 返回第一个元素为x的下标 |
| lastIndexOf（x）; | 返回最后一个元素为x的下标 |
- 修改元素
| 修改元素 | 说明 |
| set（index，x）； | 将下标为index的元素改为x |
| subList（first，last）； | 截取下标从first到last的部分顺序表 |
- 对subList（）；截取的部分的值修改，也会影响到原顺序表的值。因为subList（）；截取后返回的是该起始点的地址。
5.ArrayList的遍历：
- 有4种遍历方法//直接打印
System.out.println(list); //for循环+下标 for( int i = 0; i<list.size() ; i++ ) { System.out,println( list.get(i) ); } //foreach实现 for( Integer integer : list ) { System.out, println(integer + " "); } //使用迭代器1 Iterator<Integer> it = list.listIterator(); while (it.hasNext()) { System.out.println(it.next() + " "); } //使用迭代器2 ListIterator<String> it = list.listIterator(); while (it.hasNext()) { System.out.println(it.next()); }
- 只要实现了Iterable接口的，就可以使用迭代器来打印。
6.顺序表的缺陷：
- 增删查改，使用顺序表进行数据的插入、查找和删除其时间复杂度都是O(n)，效率太低！例如：插入和删除某个元素，需要移动其他元素。
- 顺序表的开辟需要一块连续的空间，空间利用率较低。
- 扩容问题，扩容一般是1.5倍增长，容易造成一定空间的浪费。例如：当前容量100，扩容到了150，但是我只存了9个元素，剩下的41个数据空间就浪费了......
(下面是链表部分)
7.链表的结构：
- 从物理结构上看（内存上），链表是非连续的结构；从逻辑结构上看链表又是连续的。
- 链表分为单向、双向、带头、不带头、循环和非循环。
- 组合起来一共就有8种链表结构。
- 最难掌握也是最重要的是单向不带头非循环链表。
8.单链表：
- 单链表的结构特点，单向链表存放当前元素值val和下一个元素的地址next，最后一个元素的next为null。
- 无头单向非循环链表的模拟实现
1. public class MySingleList { 2. 3. static class ListNode{ 4. public int val; 5. public ListNode next; 6. 7. public ListNode(int val) { 8. this.val = val; 9. } 10. } 11. public ListNode head; 12. 13. //头插法 14. public void addFirst(int data){ 15. ListNode node = new ListNode(data); 16. node.next = head; 17. head = node; 18. } 19. 20. //尾插法 21. public void addLast(int data){ 22. ListNode node = new ListNode(data); 23. if(head == null){ 24. head = node; 25. }else{ 26. ListNode cur = head; 27. while(cur.next != null){ 28. cur = cur.next; 29. } 30. cur.next = node; 31. } 32. } 33. 34. //打印链表 35. public void display(){ 36. ListNode cur = head; 37. while(cur != null){ 38. System.out.print(cur.val+" "); 39. cur = cur.next; 40. } 41. System.out.println(); 42. } 43. 44. //从指定节点打印 45. public void display(ListNode newHead){ 46. ListNode cur = newHead; 47. while(cur != null){ 48. System.out.print(cur.val+" "); 49. cur = cur.next; 50. } 51. System.out.println(); 52. } 53. 54. //查找元素key是否在单链表中 55. public boolean contains(int key){ 56. ListNode cur = head; 57. while(cur != null){ 58. if(cur.val == key){ 59. return true; 60. } 61. cur = cur.next; 62. } 63. return false; 64. } 65. 66. //得到链表的长度 67. public int size(){ 68. ListNode cur = head; 69. int count = 0; 70. while(cur != null){ 71. count++; 72. cur = cur.next; 73. } 74. return count; 75. } 76. 77. //插入元素时检查下标合法性 78. private void checkIndex(int index) { 79. if(index < 0 || index > size()){ 80. return; 81. } 82. } 83. 84. //任意位置插入元素,首元素若为0下标 85. public void addIndex(int index,int data){ 86. checkIndex(index); 87. if(index == 0){ 88. addFirst(data); 89. return; 90. } else if (index == size()) { 91. addLast(data); 92. return; 93. }else { 94. ListNode node = new ListNode(data); 95. ListNode cur = head; 96. while (index - 1 != 0) { 97. cur = cur.next; 98. index--; 99. } 100. node.next = cur.next; 101. cur.next = node; 102. } 103. 104. } 105. 106. //删除第一次出现的元素key 107. public void remove(int key){ 108. if(head.val == key){ 109. head = head.next; 110. return; 111. } 112. ListNode cur = head; 113. //循环中时cur.next，如果是cur的话会空指针异常 114. while(cur.next != null){ 115. //这里处理不了头节点 116. if(cur.next.val == key){ 117. cur.next = cur.next.next; 118. return; 119. } 120. cur = cur.next; 121. } 122. } 123. 124. //删除所有值为key的元素。只遍历了一遍！！ 125. public void removeAll(int key){ 126. if(head == null){ 127. return; 128. } 129. ListNode cur = head; 130. ListNode prev = head; 131. 132. while(cur != null){ 133. if(cur.val == key){ 134. prev.next = cur.next; 135. cur = cur.next; 136. }else{ 137. prev = cur; 138. cur = cur.next; 139. } 140. } 141. if(head.val == key){ 142. head = head.next; 143. } 144. } 145. 146. //清空链表 147. public void clear(){ 148. ListNode cur = head; 149. while(cur != null){ 150. ListNode curNext = cur.next; 151. cur.next = null; 152. cur = curNext; 153. } 154. head = null; 155. } 156. 157. }
9.LinkedList：
- LinkedList底层是一个双向链表，可以当作栈和队列来使用。
- LinkedList的特点，LinkedList没有实现RandomAccess接口因此不支持随机访问，而顺序表ArrayList实现了接口因此支持随机访问。
10.LinkedList常见的操作方法：
- 增加元素
| 增加元素 | 说明 |
| add（x）； | 尾插元素 x |
| add（index，x）； | 将x插入到 index下标 |
| addAll（c）； | 将c中的元素全部尾插 |
- 删除元素
| 删除元素 | 说明 |
| remove（index）； | 删除index下标元素 |
| remove（x）； | 删除遇到的第一个x元素 |
| clear（）； | 清空链表 |
- 查找元素
| 查找元素 | 说明 |
| get（index）； | 获取index下标元素 |
| contains（x）; | 判断链表中是否包含x |
| indexOf（x）; | 返回遇到的第一个x元素下标 |
| lastIndexOf（x）； | 返回最后一个值为x的元素的下标 |
- 修改元素
| 修改元素 | 说明 |
| set（index，x）； | 将index下标元素修改为x |
| subList（first，last）； | 截取first下标到last下标之间的元素 |
11.LinkedList的遍历：
- 有4种打印方法//直接打印
System.out.println(linkedlist); //for循环+下标 for( int i = 0; i < linkedlist.size(); i++ ) { System.out,println( linkedlist.get(i) ); } //foreach实现 for( Integer integer : linkedlist ) { System.out, println(integer + " "); } //使用迭代器 ListIterator<Integer> it = linkedlist.listIterator(); while (it.hasNext()) { System.out.println(it.next()); }
12.ArrayList和LinkedList异同：
- 结构上，ArrayList在物理结构和逻辑结构上是连续的，而LinkedList在逻辑结构上连续，物理结构上不一定连续。
- 因为ArrayList实现了RandomAccess接口所以支持随机访问，而LinkedList不可以。知道元素下标时ArrayList可以更快访问，时间复杂度为O(1)；LinkedList查找访问元素时效率低，时间复杂度为O(n)。
- 修改、删除和插入元素时，ArrayList的效率很低，有一种“牵一发而动全身”的感觉，因此时间复杂度为O(n)。LinkedList在处理增删改的时候只需要改动部分的next即可，效率很高。
- ArrayList还有一个特点，他是动态类型的顺序表，其容量和扩容都是固定的操作，很浪费空间，空间利用率也不高。而LinkedList没有扩容一说，如果需要增加元素只需要插入并且修改next的地址即可，空间利用率很高。
- 如果需要频繁的查找访问元素，可以使用ArrayList来完成。如果需要大量的插入删除元素，那么使用LinkedList会更好。
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
