本文共 4645 字，大约阅读时间需要 15 分钟。

双向链表

双向链表都有一个prev和next， 链表最开始的部分都有一个fiest和last 指向第一个元素和最后一个元素。

public class DoubleList {       class ListNode {           public int data;        public ListNode next;        public ListNode prev;        public ListNode(int data) {               this.data = data;        }    }    public ListNode head;    public ListNode last;//尾巴    1 头插法    public void addFirst(int data){           ListNode node = new ListNode(data);        if(this.head == null) {               this.head = node;            this.last = node;        }else {               node.next = this.head;            this.head.prev = node;            this.head = node;        }    }    2 尾插法  又单独定义了一个尾    public void addLast(int data){           ListNode node = new ListNode(data);        if(this.head == null) {               this.head = node;            this.last = node;        }else {               this.last.next = node;            node.prev = this.last;            this.last = node;        }    }        3 打印    public void display(){           ListNode cur = this.head;        while (cur != null) {               System.out.print(cur.data+" ");            cur = cur.next;        }        System.out.println();    }    	找到要插入位置的后一个元素    private ListNode searchIndex(int index) {           if(index < 0 || index >= size()) {               return null;        }        ListNode cur = this.head;        while (index > 0) {               cur = cur.next;            index--;        }        return cur;    }       4 任意位置插入,第一个数据节点为0号下标    public void addIndex(int index,int data){           if(index == 0) {               addFirst(data);            return ;        }        if(index == size()) {               addLast(data);            return ;        }        //中间插入        ListNode node = new ListNode(data);        ListNode cur = searchIndex(index);        if(cur == null) {               return ;        }		//改4个位置        node.next =  cur;        cur.prev.next = node;        node.prev = cur.prev;        cur.prev = node;    }        5 得到单链表的长度    public int size(){           ListNode cur = this.head;        int count = 0;        while (cur != null) {               count++;            cur = cur.next;        }        return count;    }        6 查找是否包含关键字key是否在链表当中    public boolean contains(int key){           ListNode cur = this.head;        while (cur != null) {               if(cur.data == key) {                   return true;            }            cur = cur.next;        }        return false;    }        7 删除第一次出现关键字为key的节点    public int remove(int key){           ListNode cur = this.head;        while (cur != null) {               if(cur.data == key) {   				int oldData = cur.data;                //3种情况                if(cur == this.head) {                       this.head = this.head.next;                    this.head.prev = null;                }else {                       //中间位置和尾巴                    cur.prev.next = cur.next;                    if(cur.next != null) {                           cur.next.prev = cur.prev;                    }else {                           this.last = cur.prev;                    }                }                return oldData;             }            cur = cur.next;        }		return -1;//循环结束都没有返回值，说明没有要删除的节点    }        8 删除所有值为key的节点   public void removeAllKey(int key){          ListNode cur = this.head;       while (cur != null) {              if(cur.data == key) {                  //3种情况               if(cur == this.head) {                      this.head = this.head.next;                   this.head.prev = null;               }else {                      //中间位置和尾巴                   cur.prev.next = cur.next;                   if(cur.next != null) {      //防止空指针异常                       cur.next.prev = cur.prev;                    }else {                          this.last = cur.prev;                   }               }           }           cur = cur.next;       }   }   	9 清空双链表   public void clear(){           while (this.head != null) {               ListNode cur = this.head.next;            this.head.next = null;            this.head.prev = null;            this.head = cur;            //cur = cur.next;        }        this.last = null;   }}

测试：

public class TestDemo {       public static void main(String[] args) {           DoubleList doubleList = new DoubleList();        doubleList.addFirst(99);        doubleList.addFirst(2);        doubleList.addFirst(3);        doubleList.addFirst(99);        doubleList.addFirst(5);        doubleList.addIndex(0,99);        doubleList.addIndex(6,99);        doubleList.addIndex(2,888);        doubleList.display();        doubleList.clear();    }}