双向链表 1.链表的结点
class Node{ //结点 public int data; public Node prev; public Node next; public Node() { this.data = data; } public Node(int data) { this.data = data; } }2.链表头插
public class DoubleList { //双向链表，不循环 private Node head;//头结点 private Node last;//尾结点 public DoubleList(){ this.head = null; this.last = null; } public void addFirst(int elem){ Node node = new Node (elem); if (head == null){ head = node; last = node; return; } node.next = head; head.prev = node; head = node; } }3.尾插
public void addLast(int elem){ Node node = new Node(elem); if (head == null){ head = node; last = node; return; } last.next = node; node.prev = last; last = node; }4.指定位置插入
public void addIndex(int index, int elem){ if (index < 0 || index > size()){ return; } if (index == 0){ addFirst(elem); return; } if(index == size()){ addLast(elem); return; } Node node = new Node(elem); Node next = search(index);//找出该位置的结点，将给定的结点插入该位置之前 Node prev = next.prev; node.next = next; next.prev = node; prev.next = node; node.prev = prev; }5.是否包含某元素
public boolean contains(int key){ Node cur = this.head; while (cur != null){ if (cur.data == key){ return true; } cur = cur.next; } return false; }6.删除给定元素
public void remove(int key){ Node cur = this.head; while (cur != null){ if (cur.data == key){ if (cur == this.head){ head = head.next; head.prev = null; return;//返回 }else{ if(cur.next != null){ cur.next.prev = cur.prev; cur.prev.next = cur.next; }else{ cur.prev.next = null; last = cur.prev; } } return;//返回 } cur = cur.next; } }7.删除给定值所有结点
public void removeAllKey(int key){ //删除给定值的所有结点 Node cur = this.head; while (cur != null){ if (cur.data == key){ if (cur == head){ head = head.next; if(head != null){ //防止全部删除时空指针异常 head.prev = null; } }else{ if (cur.next != null){//防止删除最后一个结点时空指针异常 cur.prev.next = cur.next; cur.next.prev = cur.prev; }else{ cur.prev.next = null; last = cur.prev; } } } cur = cur.next; } }相比较6，这里只用删掉return，让cur遍历完链表。
8.清空链表
public void clear(){ Node cur = this.head; while (cur != null){ //切断所有结点的联系 Node curNext = cur.next; cur.next = null; cur.prev = null; cur = curNext; } this.head = null; this.last = null; }9.打印链表
public void display(){ //打印链表 Node cur = this.head; while (cur != null){ System.out.print(cur.data + " "); cur = cur.next; } System.out.println(); }10.链表长度
private int size(){ //链表的长度 Node cur = this.head; int size = 0; while (cur != null){ size++; cur = cur.next; } return size; }11.查找给定位置的元素
private Node search(int index){ //查找某位置元素 Node cur = this.head; for (int i = 0; i < index; i++){ //与单链表不同，不用-1（不用找该位置的前一个结点） cur = cur.next; } return cur; }12.在test中测试
public class testDoubleList { public static void main(String[] args) { addF(); } public static void addF(){ DoubleList list = new DoubleList(); list.addLast(4); list.addLast(4); list.addLast(3); list.addLast(4); list.addLast(1); list.addLast(4); list.addLast(4); list.removeAllKey(4); list.display(); } }