数据结构，一切结构都来自于两个基础:数组与链表01

数据结构其实只有两种，那就是数组与链表。所有其他的复杂结构，都是在此之上构造出来的。

数组：

Object[] objArray = new Object()[16];

链表：

    private class Node{
        public E e;
        public Node next;
    }

链表需要一个类，类中需要有一个指针指向下一个对象，如：Node next；

代码中只有一个E e,则能存储一个元素。

有了这两个基础结构之后，就可以衍生出其他的结构。

如我们在java中新建一个

List<String> list1 = new ArrayList<>();

点开查看ArrayList的内部结构：

最主要的当然说就是这个Object[] elementData数组，这也是为什么数组叫做ArrayList

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

对比之下，咱们可以看一个LinkedList，显然它的实现方式就是链表。

List<String> list2 = new LinkedList<>();

链表之中，需要有一个承载数据的节点，这里使用了java的静态内部类

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

有了承载数据的Node，再看linkList中的构造函数

/**
     * Constructs an empty list.
     */
    public LinkedList() {
    }
/**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

可以看到链表，天然是个无限容量的容器，除了把内存撑爆。链表并不需要像数组一样，一开始就开辟内存空间。而是在每次增加元素的时候，增加内存消耗。

如：add方法

/**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

在每一次增加元素时，new一个Node。

java中这两个最常用List容器，就是应用了数组和链表。

后续，咱们再看通过数组和链表的构造的其他数据结构。