LinkedList的模拟实现

什么是双向链表

增加数据

头插法：

尾插法：

指定的下标插入：

删除数据

删除双向链表中出现的第一个key

置空所有数据

LinkedList和ArrayList的区别

顺序表对应的集合类是ArrayList；链表对应的集合类是LinkedList，在Java集合框架中，它们是两种最基础也是最常用的数据结构实现，它们的底层实现原理和性能差异是怎么样的呢？这里我们先来模拟实现LinkedList；

LinkedList的模拟实现

什么是双向链表

首先，我们要知道的是LinkedList的底层使用了双向链表，那么什么是双链表呢？我们前面学过单链表是由一个个节点组成，节点中包括数据域和指针域的一个链表其中指针域存放着下一个节点的地址值：

双向链表同样也是由一个个节点组成，多了个prev指针，指向前驱节点的地址，和一个last指针指向最后一个节点；那么我们如何构建一个双向链表呢？基于单链表的学习，双向链表我们模仿单链表的样式去写就简单很多了：

    //1.想构成链表的是？->节点由什么组成？定义变量 一个节点为一个对象定义成内部类static class ListNode{public int val;public ListNode next;public ListNode prev;//构造一个节点，只需要实例化public ListNode(int val) {this.val = val;}}//指向节点的一些指针public ListNode head;public ListNode last;//始终指向最后一个节点

这样写好一个链表的基本结构我们就可以为这个链表写一些操作方法了；双向链表有一些操作时不太涉及prev指针域的，这些操作是跟前面学习的单链表一致的，比如：链表打印display、表长size、查找链表的元素contains、这里就不重复记录了；具体看单链表的手动实现+相关习题，这里主要介绍与单链表有点区别的操作。

增加数据

头插法：

    public void addFirst(int data) {//1.实例化一个节点ListNode node = new ListNode(data);//2.链表尾空if (head == null){head = node;last = node;}else {node.next = head;//先绑定后面head.prev = node;head = node;}return;}

双向链表中有两个指针域，操作节点是要尤其注意操作指针域的顺序，要避免数据丢失的情况。

尾插法：

    public void addLast(int data) {ListNode node = new ListNode(data);if (head == null){head = node;last = node;}else {last.next = node;node.prev = last;last = node;//注意要更新last节点，保证last是最后一个节点}}

指定的下标插入：

在指定下标位置进行插入时，我们重点要关注的是中间插入元素是的操作顺序

    public void addIndex(int index, int data) {ListNode node = new ListNode(data);//1.判断index合法性if (index < 0 && index > size()){throw new IndexException("index非法" + index);}//2.index为0时，头插if (index == 0){addFirst(data);return;}//index为size时，尾插if (index == size()){addLast(data);return;}//3.找indexListNode cur = findIndex(index);//注意顺序node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}private ListNode findIndex(int index){ListNode cur = head;int count = 0;while (count != index){//因为是双向链表，可以访问到节点的前驱和后继，所以不用跟单链表一样找index-1cur = cur.next;count++;}return cur;}

删除数据

删除双向链表中出现的第一个key

注意：删除时要考虑到所有特殊的情况，比如删除头结点、尾结点、链表只有一个节点的情况：

    public void remove(int key) {//遍历找keyListNode cur = head;while (cur != null){if (cur.val == key ){//1.要删的节点是头结点if (cur == head){head = head.next;if (head != null){head.prev = null;}else {//链表只有一个节点且是需要删除的节点,也得置空last = null;}return;}else {if (cur.next == null){//删除尾结点cur.prev.next = null;last = last.prev;}else {//删除中间节点cur.prev.next = cur.next;cur.next.prev = cur.prev;}}return;}cur = cur.next;}}

删除第一个key值得代码我们写出来了，那么删除所有key值也非常得简单了，把return去掉让他继续往下遍历往下删除即可；

置空所有数据

我们可以直接简单粗暴的分别把head和last置空，导致整个表置空；也可以把每个节点的指针域依次置空，本质上两种方法时一样的：

    public void clear() {//循环把节点依次置空ListNode cur = head;while (cur != null){//定义一个指针指向即将被删除的节点，记录下下一个要被删除的节点ListNode curNext = cur.next;cur.prev = null;cur.next = null;cur = curNext;}this.head = null;this.last = null;}