思维导图：
?
目录
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的模拟实现
public class MyArrayList { public int[] elem; public int usedSize;//当前顺序表中元素的个数 private static final int DEFAULT_CAPACITY = 10;//给定一个默认的容量 public MyArrayList(){ elem = new int[DEFAULT_CAPACITY]; } //打印顺序表 public void diaplay(){ for (int i = 0; i < usedSize; i++) { System.out.print(elem[i]+" "); } System.out.println(); } //判断顺序表有没有满 private boolean isFull(){ return usedSize == elem.length; } //增加元素时检查下标是否合法 private void checkPos1(int pos) { if(pos < 0 || pos > usedSize){ return; } } //修改查找元素时检查下标是否合法 private void checkPos2(int pos){ if(pos<0 || pos >= usedSize){ return; } } //增加元素（尾插） public void add(int data){ if(isFull()){ elem = Arrays.copyOf(elem,elem.length*2); } elem[usedSize] = data; usedSize++; } //在pos位置上增加元素 public void add(int pos,int data){ checkPos1(pos); if(isFull()){ elem = Arrays.copyOf(elem,elem.length*2); } //注意是 i>=pos for (int i = usedSize-1; i >= pos; i--) { elem[i+1] = elem[i]; } elem[pos] = data; usedSize++; } //判断是否包含某个元素 public boolean contains(int data){ //i最多会走到usedSize的前一个元素，所以usedSize不用-1 for (int i = 0; i < usedSize; i++) { if(data == elem[i]){ return true; } } return false; } //找到某个元素的下标 public int indexOf(int data){ for (int i = 0; i < usedSize; i++) { if(data == elem[i]){ return i; } } return -1; } //获取pos下标的元素 public int get(int pos){ checkPos2(pos); return elem[pos]; } //将pos位置的值改成value public void set(int pos,int value){ checkPos2(pos); elem[pos] = value; } //删除第一次出现的关键字key public void remove(int key){ int index = indexOf(key); if(index == -1){ System.out.println("找不到这个数字"); } checkPos2(index); //这里注意一下：一定要-1 for (int i = index; i < usedSize-1; i++) { elem[i] = elem[i+1]; } usedSize--; } //获取顺序表的长度 public int size(){ /*int count = 0; for (int i = 0; i < usedSize; i++) { count++; } return count;*/ return usedSize; } //清空顺序表 public void clear(){ /*for (int i = 0; i < usedSize; i++) { elem[i]=null; }*/ usedSize = 0; } }
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。
- 无头单向非循环链表的模拟实现
public class MySingleList { static class ListNode{ public int val; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode head; //头插法 public void addFirst(int data){ ListNode node = new ListNode(data); node.next = head; head = node; } //尾插法 public void addLast(int data){ ListNode node = new ListNode(data); if(head == null){ head = node; }else{ ListNode cur = head; while(cur.next != null){ cur = cur.next; } cur.next = node; } } //打印链表 public void display(){ ListNode cur = head; while(cur != null){ System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); } //从指定节点打印 public void display(ListNode newHead){ ListNode cur = newHead; while(cur != null){ System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); } //查找元素key是否在单链表中 public boolean contains(int key){ ListNode cur = head; while(cur != null){ if(cur.val == key){ return true; } cur = cur.next; } return false; } //得到链表的长度 public int size(){ ListNode cur = head; int count = 0; while(cur != null){ count++; cur = cur.next; } return count; } //插入元素时检查下标合法性 private void checkIndex(int index) { if(index < 0 || index > size()){ return; } } //任意位置插入元素,首元素若为0下标 public void addIndex(int index,int data){ checkIndex(index); if(index == 0){ addFirst(data); return; } else if (index == size()) { addLast(data); return; }else { ListNode node = new ListNode(data); ListNode cur = head; while (index - 1 != 0) { cur = cur.next; index--; } node.next = cur.next; cur.next = node; } } //删除第一次出现的元素key public void remove(int key){ if(head.val == key){ head = head.next; return; } ListNode cur = head; //循环中时cur.next，如果是cur的话会空指针异常 while(cur.next != null){ //这里处理不了头节点 if(cur.next.val == key){ cur.next = cur.next.next; return; } cur = cur.next; } } //删除所有值为key的元素。只遍历了一遍！！ public void removeAll(int key){ if(head == null){ return; } ListNode cur = head; ListNode prev = head; while(cur != null){ if(cur.val == key){ prev.next = cur.next; cur = cur.next; }else{ prev = cur; cur = cur.next; } } if(head.val == key){ head = head.next; } } //清空链表 public void clear(){ ListNode cur = head; while(cur != null){ ListNode curNext = cur.next; cur.next = null; cur = curNext; } head = null; } }
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会更好。
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹