链表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;}