手撕一个简单的队列
我们知道队列它的底层可以是数组或者是链表， 我们今天就用数组来实现一个简单的队列
package com.atguigu.ct.producer.controller; /** * 六脉神剑 * 1.使用数组实现队列功能，使用int数组保存数据特点：先进先出，后进后出 */ public class QueueTest1 { public static void main(String[] args){ //测试队列 System.out.println("测试队列"); Queue queue = new Queue(); queue.in("六脉神剑"); queue.in("七卖神剑"); queue.in("八面玲珑"); System.out.println(queue.out()); System.out.println(queue.out()); } } //使用数组定义一个队列 class Queue { String[] a = new String[5]; int i = 1; //数组下标 //入队 public void in(String m){ a[i++] = m; } //出队 public String out(){ int index = 0; String temp = a[1]; for(int j=1;j<i;j++){ a[j-1] = a[j]; index++; } i = index; return temp; } } 复制代码
结果
测试队列 六脉神剑 七卖神剑 Process finished with exit code 0 复制代码
其实很简单 就是每次出来的时候 把所有的元素的下标往前移一位。队列深入，这边就不深入了，靠各位大佬自己了，我也是黄婆卖瓜。接下来我们讲LinkedList
LinkedList 常量
三个常量 一个表示这个集合的大小，一个表示队列的元素的前一个元素，一个表示队列元素的后一个元素
来看一个Node 元素 它要存三个数据，一个是自己本身，一个是它的前驱，一个是它的后继
构造方法
LinkedList 有两个构造函数，第一个是默认的空的构造函数，第二个是将已有元素的集合Collection 的实例添加到 LinkedList 中，调用的是 addAll() 方法，这个方法下面我们会介绍。
注意：LinkedList 是没有初始化链表大小的构造函数，因为链表不像数组，一个定义好的数组是必须要有确定的大小，然后去分配内存空间，而链表不一样，它没有确定的大小，通过指针的移动来指向下一个内存地址的分配。
添加元素
- addFirst(E e)
- 添加元素到链表的头部 只需要替换链表头部的后继指针就好了
- addLast(E e)和add(E e)
- 将指定元素添加到链表尾
- add(int index, E element)
- 讲元素拆入到指定的位置，这个要先找到这个元素的前后的元素，然后再修改。
- addAll(Collection<? extends E> c)
- 按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾
删除元素
删除元素和添加元素一样，也是通过更改指向上一个节点和指向下一个节点的引用即可。
- remove()和removeFirst()
- 从此列表中移除并返回第一个元素
- removeLast()
- 从该列表中删除并返回最后一个元素
- remove(int index)
- 删除此列表中指定位置的元素
- remove(Object o)
- 如果存在，则从该列表中删除指定元素的第一次出现，需要注意的是，这个是删除第一个出现的，并不是删除所有的这个元素
修改元素
通过调用 set(int index, E element) 方法，用指定的元素替换此列表中指定位置的元素。
这里主要是通过 node(index) 方法获取指定索引位置的节点，然后修改此节点位置的元素即可。
查找元素
因为截图截不全我就没截图了，大家可以对着源码看，具体的实现确实也不难，前面我们手撕链表大部分也实现了
- getFirst()
- 返回此列表中的最后一个元素
- getLast()
- 返回此列表中的最后一个元素
- get(int index)
- 返回指定索引处的元素
- indexOf(Object o)
- 返回此列表中指定元素第一次出现的索引，如果此列表不包含元素，则返回-1。
遍历集合
普通 for 循环
代码很简单，我们就利用 LinkedList 的 get(int index) 方法，遍历出所有的元素。
但是需要注意的是， get(int index) 方法每次都要遍历该索引之前的所有元素，这句话这么理解：比如上面的一个 LinkedList 集合，我放入了 A,B,C,D是个元素。
- 总共需要四次遍历：
- 第一次遍历打印 A：只需遍历一次。
- 第二次遍历打印 B：需要先找到 A，然后再找到 B 打印。
- 第三次遍历打印 C：需要先找到 A，然后找到 B，最后找到 C 打印。
- 第四次遍历打印 D：需要先找到 A，然后找到 B，然后找到 C，最后找到 D。
- 这样如果集合元素很多，越查找到后面（当然此处的get方法进行了优化，查找前半部分从前面开始遍历，查找后半部分从后面开始遍历，但是需要的时间还是很多）花费的时间越多。那么如何改进呢？
迭代器 这个比较适合 迭代器的另一种形式就是使用 foreach 循环，底层实现也是使用的迭代器，这里我们就不做介绍了
总结
- List继承了Collection，是有序的列表，可重复。
- 实现类有ArrayList、LinkedList、Vector、Stack等
- ArrayList是基于数组实现的，是一个数组队列。可以动态的增加容量！,线程不安全。基于数组所以查快，增删慢，因为如果要删除的话，它后面的元素就要重新改版索引。
- LinkedList是基于链表实现的，是一个双向循环列表。可以被当做堆栈使用！，它的查慢，每次查都要遍历整个集合，但是它的增删快，特别是再头尾添加，特别的快。
- Vector是基于数组实现的，是一个矢量队列，是线程安全的！基本差不多和ArrayList差不多，但是它是线程安全的，意味着性能没有那么好。
版本说明
- 这里的源码是JDK8版本，不同版本可能会有所差异，但是基本原理都是一样的。
结尾
List的三个实现，讲完了，是不是感觉也不是很难呢？博主跟着学，发现以前只是用，但是现在确实熟悉很多了。下节开始讲Map,因为Set的底层是基于Map，它放最后
因为博主也是一个开发萌新 我也是一边学一边写 我有个目标就是一周 二到三篇 希望能坚持个一年吧 希望各位大佬多提意见，让我多学习，一起进步。
