【LinkedList与链表】
目录
1，ArrayList的缺陷
2，链表
2.1 链表的概念及结构
2.2 链表的实现
2.2.1 无头单向非循环链表实现
3，LinkedList的模拟实现
3.1 无头双向链表实现
4，LinkedList的使用
4.1 什么是LinkedList
4.2 LinkedList的使用
5，ArrayList和LinkedList的区别
1，ArrayList的缺陷
当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java 集合中又引入了LinkedList，即链表结构。
2，链表
2.1 链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
链表是由一个一个节点组织起来的，整体就叫做链表
注意：
1，从上图可以看出，链式结构在逻辑上是连续的，但是在物理上（地址）不一定是连续的
2，现实中的节点一般都是从堆上申请出来的
3，从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，可能不连续
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
我们主讲单向不带头非循环和双向不带头非循环：因为截止到目前为止，所有链表的题考的都是单项不带头非循环
1，单向不带头非循环：
带头：
如果是带头的，头节点里面也可以存储值，但是不具备意义，可以认为头节点是一个标志，永远是头，不会动了，就是说对于不带头的链表，如果把12删了，head就会指向23节点的地址，对于带头的链表来说，把12删了，head还是在原来位置。
循环：
无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向非循环链表。
2.2 链表的实现
2.2.1 无头单向非循环链表实现
1，首先定义一个类，表链是由多个节点组成的，节点是一个完整的结构，提供给链表使用，我们就可以把节点定义到内部类当中，节点当中至少有两个域，value的类型是int，next是用来存下一个节点的地址的，所以next的类型应该是节点的类类型。
2，整个链表有一个东西叫做head，代表指向当前的链表，属于链表的属性，代表的是链表的头节点部分。head存的也是地址，即类型为节点类型
3，创建链表，外部类里面定义一个方法，用于链表的实现。首先有很多节点，一个一个节点属于节点对象
此时的链表是这样的
问题一：如何让第一个节点和第二个节点关联，以此内推......
当这个方法结束之后，node1，2，3，4，5就不会存地址了，他们属于局部变量，局部变量会被回收，所以这个方法走完之后，就没有这几个局部变量了
此时，就形成了一个链表
测试类：
4，打印链表
问题一：怎么从第一个节点走到第二个节点......
head = head.next
问题二：链表什么时候遍历完？
head = null ，整个链表会遍历完。若head.next = null ，56不会打印
还是在外部类中定义一个方法，用于遍历链表
测试类：
5，求链表的长度 ，还是在外部类当中定义一个方法，定义一个count用来计数。
测试类：
6，头插法
我们插入的是一个节点，实例化出来一个节点对象，再把这个节点插入到头节点的前面，head指向的位置应该指向插入节点的位置
node.next = head
head = node
两个顺序不可交换，插入节点的时候，一般首先绑后面
哪怕你所插入的链表是一个空链表，这个代码也是可以完成的
即我们在创建链表的时候，就可以不用上面createList（）方法（枚举）来创建了，直接只要头插即可
测试类：
7，尾插法
首先还是需要实例化一个节点，在需要找到当前链表的尾巴，然后在把尾巴的next置为你所插入节点的地址即可
但是还需要考虑你的head为空的时候
测试类：
8，任意位置插入
可以把原链表做一个位置标记，然后在某位置前面插入。例如在2位置前面插入一个节点。
首先要找到2位置的前一个节点，cur只需要走2-1步。将插入节点的next改为1位置的next，在把1位置的next改为所插入节点的地址。定义一个count来记录cur的位置
还要考虑其他问题：
index == 0—>头插法 index == size—>尾插法
index < 0 || index > size 位置不合法，抛异常即可
测试类：
9，判断某个关键字是否在链表当中
测试类：
10，删除第一次出现的关键字节点
首先要遍历链表，是否你要删除的val。然后找到val节点的前一个节点cur，不能走到val节点，他是单向链表，不能再回去了。在将你要删除的节点val定义为del，将 cur.next = del.next 或者写成cur.next = cur.next。next 即可。
注意：此代码不能删除头节点，需要另外判断
测试类：
11，删除链表里面所有的key
要求：对其本身就行修改
首先定义两个引用cur（代表当前需要删除的节点）prev（代表cur节点的前驱节点），判断if（cur.val==key），如果成立，让prev.next 等于cur节点的下一个节点（cur.next），再让cur往后走（cur = cur.next），prev还不能走，因为永远要保持是cur的前驱。然后继续判断，如果if条件不成立，则需判断else的情况，因为cur不是你要删除的key，需要让perv走到cur（perv = cur），再让cur走向下一个节点（cur = cur.next）。
但是这种情况没有考虑到头节点也需要删除。我们只需要判断一下头节点是否是你需要删除的key，如果是，删除头节点（head = head.next），如果下个一个头节点还是你要删除的key，则循环判断即可，或者先让上面的代码走完在判断即可。
测试类：
12，清空链表
让每一个节点都被回收掉，最直接的方式将head置为空，意味着head不在引用这个对象，即所有节点都会被回收。还要一种做法，定义cur，将cur.val置为空，将cur.next置为空，cur再往后走。但是要考虑头节点的val
3，LinkedList的模拟实现
LinkedList是Java的一个集合类，这个类可以当作链表来使用。前提是这个链表是一个双向链表
首先这种链表的节点，至少包含3个域，其中val是你存放的值，next是下一个节点的地址，prev是上一个节点的地址。同时LinkedList底层实现的时候，还加了一个last，代表永远指向链表的尾巴
3.1 无头双向链表实现
首先创建MyListedList类用来实现双向链表，在定义一个内部类来创建一个节点，在创建出head，last。
1，实现双向链表的长度
定义一个cur来遍历链表，定义一个count用来记录链表长度。
2，打印链表的val
3，查找链表是否包含关键key
4，头插法
首先new一个节点，将这个节点插入到当前链表的头部，修改head.prve，node.next和head=node即可。
还有可能一个节点都没有，即head和last都为空，让head和last同时指向node即可
5，尾插法
如果是空的来链表，让head和last同时指向node即可
若不空，只需要修改last.next，node.prev和last=node
6，任意位置插入
现在不用在定义一个cur走到需要插入位置的前一个，因为现在的节点里面包含next和prev，直接走到所插入位置即可。
7，删除关键字key
首先找到当前节点，只需要将cur的前一个节点的next等于cur的后一个节点，cur后一个节点的perv等于cur前的一个节点即可
但是呢，这个代码是存在问题的。如果说我们在这要删除头节点12，if条件成立，走if里面的代码，发现cur.prev是null，会出现空指针异常。
那么我们在删除头节点时，只需要将head往后走，在将head的prev置为null即可。
那么此时又会出现一个问题，如果说cur等于last（删除尾巴节点），上面else里面的代码，第一条是没有问题的，将cur的前驱的next置为null。
但是第二行代码就有问题，cur的next为空，空的前驱就会空指针异常。
所以在这种情况下就可以不执行这条代码，让cur的前驱的next置为null以后，让last等于last的前驱即可！！！
还有一个问题，当前链表只有一个节点！
此时的代码对于当前链表是无法执行的，走到红色框框里面的时候，head的next为null，即head等于null，然后head的prev就会空指针异常！！！
所以如果只有一个节点的情况下，走到head = head.next 的时候（head为null），说明只有一个节点，让head的前驱置为null，否则让last置为null。
8，删除所有的值为key的节点
在remove方法中，我们删除一个节点以后直接return出去，我们只需要删完一个之后继续判断即可，不return出去！！！
9，清空（）回收每一个节点
方法一：直接将head和last置为null
方法二：将每一个节点的val，prev，next（假如都是引用类型）置为null，再将head和last置为null，因为把每一个节点置为null后，head和last都还引用着对应的节点
到此，我们自己实现了一个双向链表
4，LinkedList的使用
4.1 什么是LinkedList
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
【说明】：
1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
这里时间复杂度O（1）指的是删除的时候不需要移动元素，但是在找删除元素位置的时候，需要遍历链表，时间复杂度为O（N）。
5. LinkedList比较适合任意位置插入的场景
4.2 LinkedList的使用
写法：
进入LinkedList的源码：实现了这些接口
代表此时我们是以双向链表的形式去使用的
如果是Queue去引用LinkedList，是当作队列去使用（后序会讲的）
1，LinkedList的构造
带参数的构造方法：
在顺序表中讲过，这个？称为通配符，要么为E，要么为E的子类。这个E就是你当前List所指定的泛型类型
还可以用ArrayList来进行传递，因为ArrayList，LinkedList都实现了Collection接口
2. LinkedList的其他常用方法介绍
add：进入add的源码
默认是一个尾插法
3，LinkedList的遍历
foreach循环：
for循环：
有一个问题：如果说是在此时打印一个删除一个，打印一个删除一个，会输出什么？
是不可以的，因为size一直在变化，把1打印之后，有删掉1，只剩下2和3两个元素，且size变成2了，再次打印的时候， i 等于1，就是打印3，即输出1和3。
如果把size变成一个固定的
我们发现，出现了下标越界异常。
所以，一边遍历一遍删，必然会出现问题。当打印完0下标的元素时，删掉0下标的元素，0下标就会指向2元素位置，当 i 等于2时，要打印2下标的元素，此时就会下标越界！！！
使用迭代器遍历：
iterator：
Listiterator：
iterator和Listiterator没有区别，他们是父子关系，只是Listiterator可以倒着打印
Iterator是不具备Previous这个类的，要使用ListIterator
5，ArrayList和LinkedList的区别
