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

������������������

���������������Java������������������������������Double Linked List���������������������������������

������������������
���������������������������������������������������������������������������������������������������������������������������������������������������������������
���������������
���������DoubleLinkedNode���������������������������������������������������������������
package com.test;public class DoubleLinkedNode {    private int val;    public DoubleLinkedNode prev = null; // ���������������������������    public DoubleLinkedNode next = null; // ���������������������������    public DoubleLinkedNode(int val) {        this.val = val;    }    public int getVal() {        return this.val;    }}
���������������������
���������DoubleLinkedList���������������������������������������������������������������������������������������������������������
package com.test;public class DoubleLinkedList {    DoubleLinkedNode head = null; // ������������������    public DoubleLinkedList() {        // ���������������������������������������������        head = new DoubleLinkedNode(-1);        head.prev = head;        head.next = head;    }    // ���������������    public void addFirst(int data) {        DoubleLinkedNode node = new DoubleLinkedNode(data);        node.prev = head;        node.next = head.next;        head.next = node;        head.prev = node;    }    // ���������������    public void addLast(int data) {        DoubleLinkedNode node = new DoubleLinkedNode(data);        node.next = head;        node.prev = head.prev;        head.prev = node;    }    // ������������������������0������������������������    public boolean addIndex(int index, int data) {        DoubleLinkedNode node = new DoubleLinkedNode(data);        int size = size();        // ���������������������        if (index < 0 || index > size) {            return false;        }        // ������������        if (index == 0) {            addFirst(data);            return true;        }        // ������������        if (index == size) {            addLast(data);            return true;        }        // ������������������        DoubleLinkedNode cur = toFindIndex(index);        DoubleLinkedNode prevCur = cur.prev;        prevCur.next = node;        node.prev = prevCur;        node.next = cur;        cur.prev = node;        return true;    }    // ������������������    public int size() {        int size = 0;        for (DoubleLinkedNode cur = head.next; cur != head; cur = cur.next) {            size++;        }        return size;    }    // ���������������������������    public DoubleLinkedNode toFindIndex(int index) {        int i = 0;        DoubleLinkedNode cur = head.next;        while (i < index) {            cur = cur.next;            i++;        }        return cur;    }    // ������������������������������������    public boolean contains(int key) {        for (DoubleLinkedNode cur = head.next; cur != head; cur = cur.next) {            if (cur.getVal() == key) {                return true;            }        }        return false;    }    // ���������������������������������������    public void remove(int key) {        DoubleLinkedNode cur = toFindNode(key);        if (cur == null) {            return;        }        DoubleLinkedNode prevCur = cur.prev;        DoubleLinkedNode nextCur = cur.next;        prevCur.next = nextCur;        nextCur.prev = prevCur;    }    // ������������������������������    public void removeAll(int key) {        while (true) {            DoubleLinkedNode cur = toFindNode(key);            if (cur == null) {                return;            }            // ������������������            DoubleLinkedNode prev = cur.prev;            DoubleLinkedNode next = cur.next;            prev.next = next;            next.prev = prev;        }    }    // ������������������������    public DoubleLinkedNode toFindNode(int key) {        for (DoubleLinkedNode cur = head.next; cur != head; cur = cur.next) {            if (cur.getVal() == key) {                return cur;            }        }        return null;    }    // ������������������    public void display() {        System.out.println();        // ������������        System.out.print("������:"),        System.out.print("[");        for (DoubleLinkedNode cur = head.next; cur != head; cur = cur.next) {            if (cur.next != head) {                System.out.print(cur.getVal() + ",");            } else {                System.out.print(cur.getVal() + "]");            }        }        System.out.println();        // ������������        System.out.print("������:"),        System.out.print("[");        for (DoubleLinkedNode cur = head.prev; cur != head; cur = cur.prev) {            if (cur.prev != head) {                System.out.print(cur.getVal() + ",");            } else {                System.out.print(cur.getVal() + "]");            }        }        System.out.println();    }}