Java集合中的 LinkedList

本文主要是在单向不带头链表的基础上，探讨并实现的双向不带头链表 LinkedList。

一、认识 LinkedList

说明：

1、在集合框架中，LinkedList 也实现了List接口；

2、LinkedList 的底层使用了双向链表；

3、LinkedList 没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问；

4、LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)

5、LinkedList比较适合任意位置插入的场景。

        在具体实现 LinkedList 的方法前，我们需要注意，单向链表不能回退找前一个节点，但是双向链表可以通过 prev 引用找到前一个节点，因此定义的临时变量比单向链表少。

二、LinkedList 的模拟实现

        与单向链表的功能一致。其中 display()、size()、contains() 方法一模一样，而其他方法因为不用考虑前一个节点怎么获得的问题，因此需要重写画图思考如何实现。

重点是删除节点的方法：

public class MyLinkedList{static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val){this.val = val;}}public ListNode head;public ListNode last;   // 标志最后一个节点public void display(){ListNode cur = head;while(cur != null){System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}public int size(){int count = 0;ListNode cur = head;while(cur != null){count++;cur = cur.next;}return count;}public boolean contains(int key){ListNode cur = head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}public void addFist(int data){ListNode newNode = new ListNode(data);if(head == null){head = last = newNode;return;}head.prev = newNode;newNode.next = head;head = newNode;}public void addLast(int data){ListNode newNode = new ListNode(data);if(head == null){head = last = newNode;return;}last.next = newNode;newNode.prev = last;last = newNode;}public void addIndex(int index, int data) throws IllegalIndexException{  // 自己编写的异常处理int len = this.size();  // 两次使用size()时用变量进行存储可提高效率if(index < 0 || index > len){throw new IllegalIndexException("指定位置不合法！！！");}if(index == 0){addFist(data);return;}if(index == len){addLast(data);return;}ListNode newNode = new ListNode(data);ListNode cur = findIndex(index);newNode.next = cur;cur.prev.next = newNode;newNode.prev = cur.prev;cur.prev = newNode;}private ListNode findIndex(int index) {ListNode cur = head;while (index != 0) {cur = cur.next;index--;}return cur;}public void remove(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{cur.prev.next = cur.next;  // 中间和结尾的删除if (cur.next == null){     // 尾节点的删除last = last.prev;}else{cur.next.prev = cur.prev;  // 中间节点的删除}}return;   // 删除完毕，循环结束}cur = cur.next;  // cur.val != 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{cur.prev.next = cur.next;if (cur.next == null){last = last.prev;}else{cur.next.prev = cur.prev;}}//return;   // 比remove少了该语句，}cur = cur.next;  // cur.val != key 就前进}}public void clear() {ListNode cur = head;while (cur != null){ListNode perNode = cur.next;cur.prev = null;cur.next = null;cur = perNode;}head = last = null;}
}

三、LinkedList 的方法

与 ArrayList 一致。此处不再赘述。

四、ArrayList 顺序表 与 LinkedList 链表的不同