1.双向链表
2.模拟实现双向链表
(一).构造节点类
首先我们要明白，双向链表的每一个节点都包含一个数据域和两个指针域，一个指针域为前指针域，表示指向当前节点的前一个节点，一个指针域为后指针域，表示指向当前节点的后一个节点，所以每一个节点都是一个完整的对象，所以我们可以通过定义一个内部类
static class ListNode{ public int val; public ListNode prev; public ListNode next; public ListNode(int val) { this.val = val; } }(二).明确要写的功能
要写的功能基本和单链表一样，所以我依旧是将他们放到了一个接口中，然后重写这些方法
(三).创建头节点和尾节点
public ListNode head; public ListNode tail;我们需要创建一个头节点来指向我们的第一个节点，同时创建一个尾节点来指向我的双向链表的尾节点
(四).头插法
@Override public void addFirst(int data) { ListNode node=new ListNode(data); if (head==null){ head=tail=node; }else{ node.next=head; head.prev=node; head=node; } }首先我们要先创造一个节点
然后判断head是否为空，如果head为null，说明整个链表就是空的，也就是说该节点是整个链表的第一个节点，此时该节点既是头节点，也是尾节点
如果head不为空
那就让要插入的节点的next指向头节点，同时将头节点的前驱设置为node，最后将node节点设置为新的头节点
(五).尾插法
@Override public void addLast(int data) { ListNode node=new ListNode(data); if(head==null){ head=tail=node; }else{ node.prev=tail; tail.next=node; tail=node; } }首先我们先判断链表是否为空，即head是否为空
当链表为不空的时候，我们直接让tail指向的节点的后驱next指向node，同时将node的前驱prev指向tail，最后将新插入的节点node置为新的尾
(六).任意位置插入,第一个数据节点为0号下标
@Override public void addIndex(int index, int data) { //首先判断index的合法性 try { ListNode node=new ListNode(data); if_index(index); if (index==0){ addFirst(data); return; } if (index==size()){ addLast(data); return; } ListNode cur=head; while (index-->0){ //找到要插入位置的后一个节点 cur=cur.next; } //将要插入的节点的后驱改为cur node.next=cur; //将要插入的节点的前驱改为cur的前驱 node.prev=cur.prev; //将原本cur的前一个节点的后驱改为node cur.prev.next=node; //将cur的前驱改为node cur.prev=node; }catch (indexException e){ e.printStackTrace(); } }private void if_index(int index)throws indexException{ if (index<0||index>size()){ throw new indexException("index下标异常"); } }首先我们先判断index的合法性，同样我们可以用异常来解决这个问题
如果不合法则直接抛出异常
如果合法，则我们需要找到要插入数据位置的后一个节点
然后我们让cur.prev.next指向node
我们要明白，cur.prev表示cur的前一个节点，让前一个节点的next指向node
同时让node的前驱指向cur的前一个节点，即node.prev=cur.prev
让node的后驱指向cur，即node.next=cur.next
让cur的前驱指向node，即cur.prev=node
上图就是经过我们插入之后的链表
(七).查找是否包含关键字key是否在双链表当中
@Override public boolean contains(int key) { ListNode cur=head; while(cur!=null){ if(cur.val==key){ return true; } cur=cur.next; } return false; }这个方法相对于来说比较简单，我们只需要遍历这个双向链表即可，一旦值一样，则返回ture，但当链表循环完之后，没有找到与key相等的值，则返回false
(八).删除第一次出现关键字为key的节点
@Override public void remove(int key) { ListNode cur=head; while(cur!=null){ if (cur.val==key){ //判断头节点的val值是否和key相同 if (cur==head){ //head走向下一个节点 head=head.next; //如果head不为null，那么说明这个链表不止1个头节点 //如果head为null，那么此时说明这个链表就1个头节点，那么如果执行head.prev=null就会报空指针异常 if (head!=null){ head.prev=null; } }else{ //将要删除的节点的前一个节点的前驱改为要删除节点的后驱 cur.prev.next=cur.next; //判断cur节点是否是尾节点 if (cur.next!=null){ cur.next.prev=cur.prev; }else{ //如果是尾节点，则需要tail节点往前挪一个位置 tail=tail.prev; } } return; } cur=cur.next; } if (cur==null){ System.out.println("没有你要删除的数据"); return; } }首先如果我们找到了要删除的节点
判断是否为头节点
我们要先进行判断，判断是不是头节点，如果是头节点，那么我们让头节点指向头节点的下一个节点
同时我们要将新的头节点的前驱置为空
但是当链表只有一个头节点的时候，我们会发现问题
此时head已经空了，当我们再执行head.prev=null时，就会报出空指针异常，此时程序就会报错
所以我们在判断cur是否是头节点的时候，我们要再加一层判断
既然已经执行了head=head.next了，那么head已经指向了下一个节点，所以我们只需要判断
此时的head是否为空即可，如果不为空执行head.prev=null
判断其他节点
如果不是头节点，那么剩下的节点我们就可以平常处理了
我们可以看上面的图，我们可以看到，假设我要删除cur这个节点，我应该如何做？
1.让cur前一个节点的后驱指向cur的下一个节点
首先，我先要找到cur的前一个节点，即cur.prev，再找到他的后驱，即cur.prev.next，
此时我们已经找到了cur的前一个节点的后驱，然后我们再找到cur的下一个节点、即cur.next
然后我们将cur前一个节点的后驱指向cur的下一个节点
即cur.prev.next=cur.next
2.让cur的下一个节点的前驱指向cur的前一个节点
首先，先要找到cur的下一个节点，即cur.next，然后找到他的前驱，即cur.next.prev
再找到cur的前一个节点，即cur.prev，让后一个节点的前驱指向cur的前一个节点
即cur.next.prev=cur.prev
这样我们将该节点删除了
但是还有一种情况，如果要删除的节点是尾节点我们这样写代码还可以吗？
不可以
为什么？
因为当cur是尾节点的时候我们确实可以执行cur.prev.next=cur.next，但是cur.next.prev=cur.prev还是否可行？
答案肯定是不行的，因为想一想，cur已经是尾节点了，我执行cur.next.prev，就会报空指针异常，因为cur.next已经是空了，空的前驱肯定是会报错的
所以我们在进行删除其他节点的时候，我们要进行判断，判断是否是尾节点，如果不是尾节点，我们可以正常删除，如果是尾节点，则我们可以直接对tail进行处理
直接让tail=tail.prev即可，让链表的尾指向链表的前一个节点
(九).删除所有值为key的节点
@Override public void removeAllKey(int key) { ListNode cur=head; while (cur!=null){ if (cur.val==key){ if (cur==head){ head= head.next; if (head==null){ }else{ head.prev=null; } }else { cur.prev.next=cur.next; if (cur.next==null){ tail=tail.prev; }else{ cur.next.prev=cur.prev; } } } cur=cur.next; } }这个方法和上一个第八个方法类似，第八个方法我们只是删除了一个等于key的节点，然后我们就return返回了
这个是将所有等于key的节点都删除，所以我们只需要将第八个代码中的return删掉即可
(十).计算链表的长度
@Override public int size() { ListNode cur=head; int count=0; while(cur!=null){ count++; cur=cur.next; } return count; }这个相对于来说比较简单，我们只需要比例链表然后统计个数即可
(十一).打印链表中的值
@Override public void display() { ListNode cur=head; while(cur!=null){ System.out.print(cur.val+" "); cur=cur.next; } System.out.println(); }同样也是遍历链表，然后打印每个节点的val值即可
(十二).清除链表
@Override public void clear() { ListNode cur=head; while(cur!=null){ ListNode curNext=cur.next; cur.next=null; cur.prev=null; cur=curNext; } head=null; tail=null; }清空链表，我们需要把每个节点的next域和prev域都置为null
在清空的同时，我们要记录cur的下一个节点，这样链表才能遍历起来
最后我们要将head和tail也置为空
3.链表的打印
public static void main(String[] args) { LinkedList<Integer> list=new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); System.out.println("========直接打印============"); System.out.println(list); System.out.println("=======for循环打印========="); for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i)+" "); } System.out.println(); System.out.println("======for-each打印========="); for (Integer x:list) { System.out.print(x+" "); } System.out.println(); System.out.println("=======迭代器Iterator打印========"); //先判断是否有下一个，如果有则打印下一个，并往下走一步 Iterator<Integer> iterator=list.iterator(); while(iterator.hasNext()){ System.out.print(iterator.next()+" "); } System.out.println(); System.out.println("=====迭代器ListIterator打印======="); ListIterator<Integer> listIterator=list.listIterator(); while (listIterator.hasNext()){ System.out.print(listIterator.next()+" "); } System.out.println(); System.out.println("===迭代器ListIterator倒序打印======"); ListIterator<Integer> listIterator1=list.listIterator(list.size()); while (listIterator1.hasPrevious()){ System.out.print(listIterator1.previous()+" "); } }4.ArrayList和LinkedList的区别
ArrayList底层是一个数组，所以在存储空间上，他们是连续的
LinkedList是由一个一个的节点组成，他们通过地址进行连接，所以他们是在逻辑上是连续的，在物理上不连续
当ArrayList想要随机访问数据时，我们可以直接通过下标进行访问，所以时间复杂度是O(1)
当LinkedList想要随机访问数据时，需要从头开始遍历，所以时间复杂度是O(N)
当要插入数据时，ArrayList需要移动数据，效率很低
LinkedList只需要修改引用的指向即可，时间复杂度是O(1)
同时LinkedList不需要进行扩容，而ArrayList需要进行扩容
