算法与数据结构（线性表 - 链表）链表是一种采用链式存储对线性表

1.以缺陷提出新的解决思路

1.动态数组有个明细的缺点，可能会造成内存空间的大量浪费
而链表可以做到用多少就申请多少。

2.链表的概念

1.链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的，如下所示，链表包含头节点
尾结点 ，节点之间通过节点地址进行连接。

链表实例

3.链表的创建

根据链表的结构进行创建链表对象：
1. 一个节点中含有节点元素（任意类型） 和下一个节点的地址。
2.头节点，头节点不包含元素，只有下一个节点地址和整个链表的大小。

所以根据需要就可以创建出对应链表对象。

链表创建图示

//    链表长度
    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;
        }
    }

4.链表接口方法

链表常用的接口方法与动态数组（ArrayList）大致相同，所以采用实现接口的方式：

public interface PublicInterface<E> {
    int size(); //元素的数量
    boolean isEmpty(); //是否为空
    boolean contains(E element); // 是否包含某个元素
    void add(E  element);  // 添加元素到最后面
    E  get(int index); // 返回index位置对应的元素
    E set(int index,E element); // 设置index位置添加元素
    void add(int index,E element); // 往index位置添加元素
    E remove(int index); // 删除index位置对应的元素
    int indexOf(E element); //查看元素的位置
    void clear(); // 清除所有的元素
}

5.提取动态数组与链表相同代码

动态数组和链表中如查看动态数组/链表数量 、是否为空的实现方式相同，所以采用继承的方式提取
相同的代码：

public abstract class AbstructList<E> implements PublicInterface<E> {
    //    链表长度
    protected int size ;


    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(E element) {
        return   indexOf(element) != NOT_DATA_FIND;
    }

    @Override
    public void add(E element) {
        add(size,element);
    }
}

其中： 1. AbstructList 实现接口，但却不重写所有方法，采用抽象类方式。
           2. 将size 提取到抽象类中 ，设置为 protected。
           3.动态数组和链表来继承这个抽象类。

6.通过索引获取节点对象

1.在进行链表节点添加、删除等功能实现时都需要获取到某个节点对应的节点或者节点元素，所以创建
一个私有的方法来通过索引获取到对应的节点对象：
  /**
     * 通过索引获取节点
     * @param index
     * @return
     */
    private Node getNode(int index){
        if(index < 0 || index >= size){
            throw  new IndexOutOfBoundsException("Index:" + index + " " +   "Size" + size);
        }
        Node<E> node = first;
        for(int i =0 ; i < index ; i++){
            node = node.next;
        }
        return node;
    }

7.节点元素获取、通过索引设置节点元素

通过刚刚创建的通过索引获取节点对象的方法来进行实现：
// 获取索引对应的节点元素值
  @Override
    public E get(int index) {
        Node<E> node = getNode(index);
        return node.element;
    }
// 根据索引设置元素值
  @Override
    public E set(int index, E element) {
        Node<E> node = getNode(index);
        E old = node.element;
        node.element = element;
        return old;
    }

8.链表在指定索引添加节点

如图所示，如果我们要添加1号节点到0、2节点之间，需要进行的步骤：
  1. 通过索引找到指定索引的上一个节点 定义为prev。
  2.创建一个节点newNode，使节点的next为 prev.next.
  3.prev的下一个节点为newNode 。
  
  其中如果索引为零的特殊情况，通过first解决，即可实现指定索引添加节点。

链表节点添加

  @Override
    public void add(int index, E element) {
        if(index == 0 ){
           first = new Node<>(element,first);
        }else{
            //       找到index的上一个节点
            Node prev = getNode(index - 1);
      //        创建一个节点 设置下一个节点为index上一个节点的next，prev的next要指向它
            prev.next = new Node<>(element,prev.next);
        }
        size ++ ;

    }

9.链表节点删除

如图所示，要进行指定索引节点的删除（删除节点1）：
1.通过索引获取到上一个节点 prev。
2.prev的下一个节点为prev.next.next。
3.如果是删除索引为0的节点，即first = first.next。
即可实现指定索引删除节点的功能。

链表节点删除

   @Override
    public E remove(int index) {
        Node<E> node = first;
        if(index == 0){
            first = first.next;
        }else{

            //        先找出index上一个节点
            Node<E> prev = getNode(index-1);
            node = prev.next;
            prev.next = prev.next.next;

        }
        size --;
        return node.element;
    }

10.链表的清空

链表的清空，只需要将断开LinkedList指向的节点即可实现链表的清空，然后0节点被销毁，依次
进行，所有节点被销毁。

链表的清空

// 链表的清空
    @Override
    public void clear() {
      size = 0;
      first = null;
    }