今天一起学下链表，英文名Linked List，上次一起学了下动态数组，动态数组动态的扩容，当数组的空间不够的时候，但是它有个明显的缺点，填满后重新创建一个原来1.5倍的新数组，扩容完毕后需要将原来的数组的元素拷贝过来，但是新扩容的还有一部分用不上，增加了扩容后增加了内存的空间，什么时候能用的完，这不好根据业务。

（一）链表① 动态数组有个明显的缺点

可能会造成内存空间的大量浪费。

② 能否用到多少就申请多少内存

添加新元素，就分配新的存储空间，用多少申请多少。 链表就可以办到这一点。

③ 链表的定义

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的。不按照顺序存储，所有的元素都是链式的，

链表存储，创建一个Node节点，Node节点的内部存储元素， 下一个Node的地址。来一个分配一个内存地址就可能不连续。地址肯定肯定是随机。一般最后的元素，提示的下一个Node的地址为null。

④ 链表的设计

1.至少有2个东西：size存储元素的长度多少个节点，first指向第一个元素。

2.每个节点内部有2个元素：element，next ，element负责存储元素的数据，next服务指向下个元素的地址。

3.所有都是用到的时候才分配存储空间。

⑤ 链表的接口

package com.idig8;public class LinkedList<E> {    private int size;    private Node<E> first;    private static class Node<E>{        E element;        Node<E> next;        public Node(E element,Node<E> next){            this.element = element;            this.next = next;        }    }}

清空链表，添加获得链表个数，链表的长度，是否为空，获取链表，这些基本跟之前说的动态数组很类似，链表和动态数组都属于线性表，它们两个很多东西都是一样的很多时候可以直接想到的是继承。存一个一个问题，动态数组和链表它们添加，获取的方式都是不一样的，继承父类的话，它们暂且认为没有公共的代码，只是需要实现的功能一致，在java里面一般都是搞一个接口。接口有个特点只申明不实现，都有的接口进行申明。

接口

 public interface List {   static final int ELEMENT_NOT_FOUND = -1;   /**  * 清除所有元素  */	void clear();   /**   * 元素的数量   * @return   */  int size();  /**   * 是否为空   * @return   */  boolean isEmpty();  /**   * 是否包含某个元素   * @param element   * @return   */  boolean contains(E element);  /**   * 添加元素到尾部   * @param element   */  void add(E element);  /**   * 获取index位置的元素   * @param index   * @return   */  E get(int index);  /**   * 设置index位置的元素   * @param index   * @param element   * @return 原来的元素ֵ   */  E set(int index, E element);  /**   * 在index位置插入一个元素   * @param index   * @param element   */  void add(int index, E element);  /**   * 删除index位置的元素   * @param index   * @return   */  E remove(int index);  /**   * 查看元素的索引   * @param element   * @return   */  int indexOf(E element);}

一定会存在公共代码的问题，接口一般不只是一个地方使用，例如：List接口可以供ArrayList 和 LinkedList，对于他们公共的部分可以抽离出来，做一个抽象的父类。抽象类里面的接口有一部分可以不实现的，可以交给他下面的子类来进行实现。抽象类无法进行new，父类不对外公开，符合开发思路。

public abstract class AbstractList<E> implements List<E>  {    /**     * 元素的数量     */    protected int size;    /**     * 元素的数量     * @return     */    public int size() {        return size;    }    /**     * 是否为空     * @return     */    public boolean isEmpty() {         return size == 0;    }    /**     * 是否包含某个元素     * @param element     * @return     */    public boolean contains(E element) {        return indexOf(element) != ELEMENT_NOT_FOUND;    }    /**     * 添加元素到尾部     * @param element     */    public void add(E element) {        add(size, element);    }    protected void outOfBounds(int index) {        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);    }    protected void rangeCheck(int index) {        if (index < 0 || index >= size) {            outOfBounds(index);        }    }    protected void rangeCheckForAdd(int index) {        if (index < 0 || index > size) {            outOfBounds(index);        }    }}

LinkedList 集成这个父类AbstractList

public class LinkedList<E> extends AbstractList<E>{    private Node<E> first;    private static class Node<E>{        E element;        Node<E> next;        public Node(E element,Node<E> next){            this.element = element;            this.next = next;        }    }}

PS：下次一起开始链表的代码讲解和实现。思考题：作为开发人员的你，上边这种抽象出来的思路，你应用的多吗，接口，抽象父类，子类继承父类的方式。