学习数据结构，我们首先了解一些概念性的知识

什么数据结构

数据项：
一个数据元素可以有若干个数据项组成
数据对象
有相同性质的数据元素的集合，是数据的子集
数据结构
是相互之间存在一种或多种特定关系的数据元素的集合。

逻辑结构和物理结构

逻辑结构：是指数据对象中数据元素之间的相互关系。
物理结构：是指数据的逻辑结构在计算机中的存储形式

线性表

线性表分为顺序表和链表
下面我们看下数组

数组Array

数组是有限个相同数据类型元素的集合
数组的特点：
1、数组是一种最简单的数据结构。
2、数组占据连续的空间。数据空间连续，按照申请的顺序存储，但是必须指定数组长度
3、数组空间效率低。主要原因是数组中经常有空闲的区域没有得到充分的应用
4、数组查询快，增删慢。

为什么数组访问速度快

因为数组都有角标，我们可以通过角标直接获取到数组在该角标位的数据。

为什么数组增删慢

数组在尾部增删快，但是在其他地方就相对较慢。
主要原因是数组增加和删除元素都需要大量的移动元素。

数组增删.png

顺序表

顺序表的节点是严格按照物理地址连续排列的。
顺序表内部的存储结构还是数组
ArrayList就是顺序表，我们看下ArrayLIst的源码

ArrayList的源码

ArrayList增加数据源码分析.png

顺序表的特点

优点：
尾插效率高，支持随机访问。
缺点：
中间插入或者删除效率低。

链表

链表存储空间是不联连续的。虽然物理上是不连续的，但是逻辑上是连续的。
下面，我们解释下为什么链表在逻辑上是连续的。

链表.png

链表有多种类型，下面我们说一说单链表和双链表

单链表

单链表的每个元素都包含了自身的数据data和下一个节点，并且单链表包含了一个头节点

单链表.png

单链表的增加和删除

单链表的增删.png

单链表因为没有角标索引，所以单链表的查询需要从头遍历，知道找到对应的节点

单链表的特点

优点：
随意进行增删改
插入效率高
删除效率高
长度可以随意修改
缺点：
内存不连续
不能随机查找

双链表

双链表的每个元素都包含了自身的数据，前一个节点和后一个节点，并且双链表有一个头节点和一个尾节点

双链表.png

下面我们看看双链表的增删

双链表的增删.png

LinkedList

LinkedList是双链表的一个典型例子，下面我们看下LinkedList的增删源码

 public void add(int index, E element) {
        //检查是否越界
        checkPositionIndex(index);

        //如果index等于size，则代表在双链表结尾添加数据，可以直接添加
        if (index == size)
            linkLast(element);
        else {
            //如果不是在结尾添加，就需要先找到添加的位置，然后再进行插入
            linkBefore(element, node(index));
        }
    }

  void linkLast(E e) {
        //尾节点
        final LinkedList.Node<E> l = last;
        //创建一个新的节点，要插入的节点是新的尾节点，之前的尾节点l是newNode的前节点，尾节点没有下一个节点
        final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
        //newNode节点是新的尾节点
        last = newNode;
        //如果l是空节点，则说明之前是空链表，所以newNode节点也是头节点
        if (l == null){
            first = newNode;
        }
        else{//如果l不是空节点，则需要把newNode指向l的下一个节点
            l.next = newNode;
        }
        size++;
        modCount++;
    }

   /**
     *查找index位置的节点
     */
    LinkedList.Node<E> node(int index) {
        // assert isElementIndex(index);

        //判断index是否小于size的一半，因为双链表节点包含了前后节点，所以两边都可以进行遍历
        //如果index小于size/2，则从头节点开始遍历，可以减少遍历次数
        //如果index大于size/2，则从尾节点开始遍历，可以减少遍历次数
        if (index < (size >> 1)) {
            LinkedList.Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            LinkedList.Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

 void linkBefore(E e, LinkedList.Node<E> succ) {
        // assert succ != null;
        //获取index位置的节点的前一个节点
        final LinkedList.Node<E> pred = succ.prev;
        //新节点的pre指向pre，新节点的next指向succ，新节点的数据是e,创建一个新的节点
        final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);
        //newNode赋值给succ的pre
        succ.prev = newNode;
        //pred为空，则之前是空链表，newNode赋值给头节点
        if (pred == null){
            first = newNode;
        } else{//newNode赋值给pred的next
            pred.next = newNode;
        }

        size++;
        modCount++;
    }

源码的解析都放在代码里的，代码里面添加非常详细的注释。

下面我们看下LinkedList的删除

       public E remove(int index) {
        //判断是否越界
        checkElementIndex(index);
        //node(index)是找到index位置的节点，在add方法中已经解析了，这里就不再重复解析
        return unlink(node(index));
    }


    E unlink(LinkedList.Node<E> x) {
        // assert x != null;
        //获取x节点的数据，作为返回值
        final E element = x.item;
        //获取x节点的后节点
        final LinkedList.Node<E> next = x.next;
        //获取x节点的前节点
        final LinkedList.Node<E> prev = x.prev;

        //如果前节点为空，则之前x节点就是头节点，现在要删除x节点，所以next节点是新的头节点
        if (prev == null) {
            first = next;
        } else {
            //删除x节点之后，x的前节点的next指向x节点的后一个节点next
            prev.next = next;
            //x不再有前节点
            x.prev = null;
        }

        //如果next是空，则之前x是尾节点，删除x之后，x的前节点pre就是新的尾节点
        if (next == null) {
            last = prev;
        } else {
            //将x节点的下一个节点的pre指向x节点的前一个节点pre
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }