用 Java 实现一个链表

链表是一种在计算机科学中十分重要的数据结构，他是很多高级数据结构的实现基础，可以这样说，没有链表，就会少很多在计算机科学领域大放异彩的优秀数据结构。

本文提供了一种由 Java 语言实现链表的方法：

public class DoubleLinkedList {

    private class Node {
        private Object value;
        private Node prev;
        private Node next;

        public Node(Object value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return this.value.toString();
        }

    }

    private int size = 0;

    private Node head = null;

    /**
     * Get length of this list.
     *
     * @return length
     */
    public int length() {
        return this.size;
    }

    @Override
    public String toString() {
        if (size == 0) {
            return null;
        } else {
            StringBuffer result = new StringBuffer();
            result.append("[");
            Node node = head;
            for (int i = 0; i < size; i++) {
                result.append(node.value + ", ");
                node = node.next;
            }
            String s = result.substring(0, result.length() - 2) + "]";
            return s;
        }
    }

    /**
     * <b>Insert</b> value into exact position.
     *
     * @param value Add value.
     * @param index The index of the position.
     */
    public void insert(Object value, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("下标越界");
        } else {
            Node newNode = new Node(value);
            if (size == 0) {
                head = newNode;
            } else if (size == index) {
                Node node = head;
                for (int i = 0; i < index - 1; i++) {
                    node = node.next;
                }
                node.next = newNode;
                newNode.prev = node;
            } else {
                Node node = head;
                for (int i = 0; i < index; i++) {
                    node = node.next;
                }
                // 新插入进来的节点
                newNode.next = node;
                node.prev.next = newNode;
                newNode.prev = node.prev;
                node.prev = newNode;
            }
            size++;
        }
    }

    /**
     * <b>Add</b> value at the last of this list.
     *
     * @param value Add value.
     */
    public void add(Object value) {
        this.insert(value, size);
    }

    /**
     * Delete the first value of been inputted.
     *
     * @param value
     * @return
     */
    public Object remove(Object value) {
        if (size == 0) {
            throw new IndexOutOfBoundsException("没有该参数");
        } else {
            if (size == 1) {
                head = null;
                return head.value;
            } else {
                Node node = head;
                boolean flag = false;
                for (int i = 0; i < size; i++) {
                    if (value.equals(node.value)) {
                        if (i == 0) {
                            node.next.prev = null;
                            head = node.next;
                        } else if (i == size - 1) {
                            node.prev.next = null;
                        } else {
                            node.prev.next = node.next;
                            node.next.prev = node.prev;
                        }
                        flag = true;
                        size--;
                        break;
                    } else {
                        node = node.next;
                    }
                }
                if (!flag) {
                    throw new IndexOutOfBoundsException("没有该参数");
                } else {
                    return value;
                }
            }
        }
    }

    /**
     * Delete the value
     *
     * @param index
     * @return
     */
    public Object remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("下标越界");
        } else {
            Object value = null;
            if (size == 0) {
//                throw new NoSuchFieldException("链表长度为空");
            } else if (size == 1) {
                value = head.value;
                head = null;
                size--;
            } else {
                if (index == 0) {
                    value = head.value;
                    head.next.prev = null;
                    head = head.next;
                } else {
                    Node node = head;
                    for (int i = 0; i < index; i++) {
                        node = node.next;
                    }
                    if (index == size - 1) {
                        node.prev.next = null;
                        value = node.value;
                    } else {
                        node.prev.next = node.next;
                        node.next.prev = node.prev;
                        value = node.value;
                    }
                }
                size--;
            }
            return value;
        }
    }

    /**
     * Check this list is empty.
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0 ? true : false;
    }

    /**
     * Set this list empty
     *
     * @return
     */
    public DoubleLinkedList empty() {
        head = null;
        size = 0;
        return this;
    }

    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add("100");
        doubleLinkedList.insert("200", 1);
        doubleLinkedList.add("1221");
        doubleLinkedList.remove(0);
        System.out.println(doubleLinkedList);
    }

}