（一）链表

• ① 动态数组有个明显的缺点

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

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

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

• ③ 链表的定义

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

链表存储，创建一个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：下次一起开始链表的代码讲解和实现。思考题：作为开发人员的你，上边这种抽象出来的思路，你应用的多吗，接口，抽象父类，子类继承父类的方式。