链表3（LinkedList）

1、双向不带头链表的实现

1.1 节点成员和构造方法

双向不带头链表相比于单向多了一个prev域，它能使链表获得前驱节点。

如上图是双向不带头链表的一个节点，它可以直接找到前驱和后继节点。

由上面的讲解可得到代码：（注意：节点的类为静态内部类）

//静态内部类  
static class ListNode {
        private int val;//值域
        private ListNode prev;//前驱
        private ListNode next;//后继
        //构造方法
        public ListNode(int val) {
            this.val = val;
        }
    }

相比于单向链表的头节点，在双向链表中，多了一个尾巴节点last，方便了尾插法。

1.2 size（）、display（）、contains（）

求链表长度、打印链表、查找链表中是否包含该元素

这三个方法与单链表相同都是通过头节点遍历链表，这里就不做过多赘述。

代码如下：

 //得到双链表的长度
 public int size(){
            int length = 0;
            ListNode cur = head;
            while(cur != null){
                length++;
                cur = cur.next;
            }
            return length;
        }

 // 打印链表
 public void display(){
            ListNode cur = head;
            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;
        }

1.3 addFirst（）

头插法

相比于单链表的头插法，双链表的头插法又有什么不同呢？

如图，要将33头插入当前双链表中，在单链表中，我们只需要绑定后面的元素，然后再把头节点给到node，而双链表则还需要改掉原来头节点的前驱。

由此，有代码如下：

                    node.next = head;
                    head.prev = node;
                    head = node;

此时，观察代码我们会想：如果我的链表中没有元素，那这里的不就发生空指针异常了吗？

因此，我们需要判断，当head==null的时候，我们把链表的头节点和尾巴节点都给到node，代码如下：

 if(head == null){
                    head = node;
                    last = node;
                }

完整代码：

public void addFirst(int data){
                ListNode node = new ListNode(data);
                if(head == null){
                    head = node;
                    last = node;
                }else{
                    node.next = head;
                    head.prev = node;
                    head = node;
                }
        }

1.4 addLast （）

尾插法

与头插法大同小异，只需要把原来的last的next改为node，再把当前节点的前驱改为last，再让last = node即可，如果链表中没有元素，就把头和尾巴都给到head。

完整代码：

   public void addLast(int data){
            ListNode node = new ListNode(data);
            if(head == null){
                head = node;
                last = node;
            }else{
                node.prev = last;
                last.next = node;
                last = node;
            }
        }

1.5 addIndex（）

在下标位置插入

在单链表中，addIndex方法需要找到下标的前一个元素。而在双链表中则可以直接找到该下标的元素（因为我们可以通过前驱来找到前一个元素）。

如图所示，我们需要改动4处位置，这里一定要注意这4处的顺序：建议最先改node的prev和next，然后改cur.prev.next,前面的顺序可以改变，但是cur的prev一定是最后改的。因为是任意位置插入，在0位置我们直接调用头插法函数；在size（）位置直接调用尾插法函数；下标不合法，抛异常。

完整代码：

//任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
            ListNode listNode = new ListNode(data);
            if(index < 0 ||index > size()){
                throw new IndexErrorException(index+"下标错误，无法插入");
            }
            if(index == 0){
                addFirst(data);
                return;
            }
            if(index == size()){
                addLast(data);
                return;
            }
            int count = 0;
            ListNode cur = head;
            while(count != index){
                cur = cur.next;
                count++;
            }
            listNode.next = cur;
            listNode.prev = cur.prev;
            cur.prev.next = listNode;
            cur.prev = listNode;
        }

1.6 remove（）

删除第一次出现值为key的节点

例如：要删除的key为34。

因为有了前驱和后继，我们可以直接让cur遍历到值为key节点，然后让cur.next.prev = cur.prev; cur.prev.next = cur.next;

细心的同学此时会发现问题:那我如果要删除的元素是头节点或尾节点，不发生空指针异常了吗？

是的，所以我们需要写两个if语句进行判断来单独删除头节点和尾巴节点：删除头节点：head = head.next; head.prev = null;此外，还应考虑链表只有一个节点的情况：只需将last置空即可。删除尾节点：cur.next.prev = null; last = last.prev;

代码如下

1.7 removeAllKey（）

删除所有值为key的节点

删除所有值为key的元素，只需要把remove（）代码中的return删去，让cur继续走下去即可。

代码如下：

//删除所有值为key的节点
        public void removeAllKey(int key){
            ListNode cur = head;
            while(cur != null){
                if(cur.val == key){
                    //删除头结点
                    if(cur == head){
                        head = head.next;
                        if(head != null) {
                            head.prev = null;
                        }else{//只有一个节点的情况
                            last = null;
                        }

                    }else {//删除中间和尾巴
                        //删除尾巴
                        if(cur.next == null){
                            cur.prev.next = cur.next;
                            last = last.prev;

                        }else {//删除中间
                            cur.prev.next = cur.next;
                            cur.next.prev = cur.prev;

                        }
                    }
                }
                cur = cur.next;
            }
        }

1.8 clear（）

清空链表

清空链表的所有节点，有两种方法：

1、暴力清空（将head和last直接置空）

public void clear(){
    head = null;
    last = null;
}

2、将所有节点的前驱和后继置空

   public void clear(){
            ListNode cur = head;
            while(cur != null){
                ListNode curNext = cur.next;
                cur.prev = null;
                cur.next = null;
                cur = curNext;
            }
            head = null;
            last = null;
          }