一、双向链表是什么？ 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方
一、双向链表是什么？
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。LinkedList底层就是一个双向链表，我们来实现一个双向链表。
这里多一个尾指针，方便我们对尾插操作从O(n)降到O(1).每个结点多了前驱结点，方便我们对链表进行操作。
二、具体方法实现
定义结点
class ListNode { int value; ListNode next; ListNode prev; public ListNode(int value) { this.value = value; } }下标访问异常
public class IndexWrongException extends RuntimeException{ public IndexWrongException() { } public IndexWrongException(String message) { super(message); }}获取链表长度
class ListNode { int value; ListNode next; ListNode prev; public ListNode(int value) { this.value = value; } }打印链表
class ListNode { int value; ListNode next; ListNode prev; public ListNode(int value) { this.value = value; } }清空链表
public void clear(){ if(this.head == null) { return; } ListNode cur = this.head; while(cur != null) { ListNode curNext = cur.next; cur.prev = null; cur.next = null; cur = curNext; } head = null; tail = null; }头插法
public void addFirst(int data){ ListNode node = new ListNode(data); if(head == null) { this.head = node; this.tail = node; return; } node.next = this.head; this.head.prev = node; this.head = node; }尾插法
public void addLast(int data){ ListNode node = new ListNode(data); if(head == null) { this.head = node; this.tail = node; return; } tail.next = node; node.prev = tail; tail = node; }指定位置插入
public void addIndex(int index,int data) throws IndexWrongException{ if(index < 0 || index > size()) { throw new IndexWrongException("输入下标不合法"); } ListNode node = new ListNode(data); if(index == 0) { addFirst(data); return; } if(index == size()) { addLast(data); return; } ListNode cur = this.head; while(index != 0) { cur = cur.next; index--; } node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; }查找元素
public boolean contains(int key){ if(head == null) { return false; } ListNode cur = this.head; while(cur != null) { if(cur.value == key) { return true; } cur = cur.next; } return false; }删除第一次出现的关键字
public void remove(int key){ ListNode cur = head; while(cur != head) { if(cur.value == key) { if(cur == head) { head = head.next; if(head.next != null) { head.prev = null; }else { tail = null; } }else { cur.prev.next = cur.next; if(cur.next != null) { cur.next.prev = cur.prev; }else { tail = cur.prev; tail.next = null; } } return; } cur = cur.next; } }删除所有值为key的节点
public void removeAllKey(int key){ ListNode cur = head; while(cur != head) { if(cur.value == key) { if(cur == head) { head = head.next; if(head.next != null) { head.prev = null; }else { tail = null; } }else { cur.prev.next = cur.next; if(cur.next != null) { cur.next.prev = cur.prev; }else { tail = cur.prev; tail.next = null; } } } cur = cur.next; } }