手写LinkedList

LinkedList是双向链接数据结构，插入和删除快，查询慢，因为他使用了二分查找。

public class ExtLinkedList<E> {

    private Node first;

    private Node last;

    private int size;

    public void add(E o) {
        Node l = last;
        Node node = new Node(o, l, null);
        last = node;
        if(l == null) {
            first = node;
        } else {
            l.next = node;
        }
        size++;
    }

    public Node<E> get(int index) {

        if(index < (size >> 1)) {
            Node x = first;
            for(int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node x = last;
            for(int i = size - 1; i > index; i--) {
                x = x.pre;
            }
            return x;
        }
    }

    public Node remove(int index) {
        Node node = get(index);
        unlink(node);
        return node;
    }

    private void unlink(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        if(pre == null) {
            first = next;
        } else {
            pre.next = next;
            node.pre = null;
        }
        if(next == null) {
            last = pre;
        } else {
            next.pre = pre;
            node.next = null;
        }
        node.item = null;
        size--;
    }

    public static void main(String[] args) {
        ExtLinkedList<String> tests = new ExtLinkedList<String>();
        tests.add("a");
        tests.add("b");
        tests.add("c");
        Node node = tests.get(0);
        System.out.println(node.item);
        node = tests.remove(1);
        for(int i = 0; i < tests.size; i++) {
            System.out.println(tests.get(i).item);
        }
    }


    static class Node<E> {
        E item;
        Node<E> pre;
        Node<E> next;
        public Node(E item, Node pre, Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }

}