线性表（ArrayList 和 LinkedList）

在学习线性表之前我们先来看看下面几个问题

1、什么是数据结构？

• 数据之间相互存在的一种或多种特定的关系的元素的集合

2、什么是逻辑结构？

• 数据对象中数据元素之间的相互关系
• 逻辑结构包括以下几类
  1、 线性结构
  2、 树形结构
  3、 图形结构
  4、 集合结构

3、学习数据结构有什么用？

工作这么久了本人感觉压根就没怎么用过数据结构，什么二叉树啊，队列啊，堆栈啊等等的感觉并没用怎么使用过，但是别人又强调数据结构很重要是内功，细细回味其实自己还是蛮多地方在无形之中应用了这些东西，只是没有深究而已，简单来说之前做一个项目需要实时上传硬件接收过来的数据到服务端，怎么做来？直接就用起来的队列来一个数据加进去，上传一个就移除一个，其实感觉数据结构跟多的是教会我们一个思维方式，如何把现实的问题转换成机器语言来表示。所以学好数据结构能让我们去更合理的利用计算机解决现实的问题。

---

• 接下来我们就开始正式学习线性表

1、概念：

• 线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列

  
  线性表.png

• a1是a2的前驱，ai+1 是ai的后继，a1没有前驱，an没有后继

• n为线性表的长度 ，若n==0时，线性表为空表

2、分类：

• 顺序存储方式线性表 （ArrayList）

顺序存储方式线性表.png

优点：查询快
缺点：删除插入慢（牵一发而动全身 插入一个后边整体要后移） 需要一段连续的存储空间

• 链式存储方式线性表 (单向链表 和双向链表 LinkedList-双向不循环列表)

链式存储方式线性表.png 双向循环链表.png

优点：删除插入快
缺点：查询慢（需要一个个遍历） 不需要一段连续的存储空间

---

ArrayList ——源码分析

个人理解：ArrayList 是一个可以动态扩容的数组，简单来说是对数组的拓展。

ArrayList 变量说明

private static final Object[] EMPTY_ELEMENTDATA = {}; //创建一个空数组 用于 判断数组是否为空或初始化空数组
transient Object[] elementData; //

ArrayList 构造函数有三个分别为

• ArrayList() //实例化一个空数组

public ArrayList(){
    super();
    this.elementData = EMPTY_ELEMENTDATA;
}

• ArrayList(int initialCapacity) //传入一个指定的大小长度 实例化内部数组

  public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

• ArrayList(Collection<? extends E> c) // 将c 赋值给内部数组

ArrayList 添加

• void add(int index, E element)

  public void add(int index, E element) {
        if (index > size || index < 0) //index 是否正确
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // Increments modCount!!  扩容  具体做了检查是否需要扩容 按照什么样的大小扩容

        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

• void add(E element)

• boolean addAll(Collection<? extends E> c)

• boolean addAll(int index, Collection<? extends E> c)

ArrayList 移除

• E remove(int index)

  public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) elementData[index]; //记录删除的 数据

        int numMoved = size - index - 1;//
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

• boolean remove(Object o)
• boolean removeAll(Collection<?> c)
• boolean removeIf(Predicate<? super E> filter)

ArrayList 修改

• E set(int index, E element)

public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

---

LinkedList——源码分析

个人理解：LinkedList是一个双向不循环列表，易于增加和删除

LinkedList变量说明

 //构成的基本数据单元
  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;
        }
    }

  transient Node<E> first;
  transient Node<E> last;
  transient int size = 0;

LinkedList 构造函数有两个 （不存在指定长度 因为是链表）

• LinkedList()

 public LinkedList() {
 }

• LinkedList(Collection<? extends E> c)

 public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
}

LinkedList 添加

• boolean add(E e)
• void add(int index, E element)

  public void add(int index, E element) {
        checkPositionIndex(index); //判断index是否合法 --> index >= 0 && index <= size

        if (index == size)//添加到结尾 直接 添加
            linkLast(element);
        else
            linkBefore(element, node(index));//node(index)遍历出节点
    }

  //对应下图
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;  //pred 为 ai   succ 为 ai+1
        final Node<E> newNode = new Node<>(pred, e, succ); //完成了图中 3 4 步骤 具体看源码
        succ.prev = newNode; // 完成了图中 2步骤
        if (pred == null)// succ 为头节点 只需要头节点first 指向 newNode
            first = newNode; 
        else  //完成了 图中 1步骤
            pred.next = newNode;
        size++;
        modCount++;
    }

添加元素.png

• boolean addAll(Collection<? extends E> c)
• boolean addAll(int index, Collection<? extends E> c)
• void addFirst(E e)
• void addLast(E e)
• boolean offer(E e)
• boolean offerFirst(E e)
• boolean offerLast(E e)

注：

1. offer属于 offer in interface Deque<E>，add 属于 add in interface Collection<E>。
2. 当队列为空时候，使用add方法会报错，而offer方法会返回false。
3. 作为List使用时,一般采用add / get方法来 压入/获取对象。
4. 作为Queue使用时,才会采用 offer/poll/take等方法作为链表对象时,offer等方法相对来说没有什么意义这些方法是用于支持队列应用的。

LinkedList 移除

• boolean remove(Object o)
• E remove(int index)

  public E remove(int index) {
        checkElementIndex(index);  //判断index是否合法 --> index >= 0 && index <= size
        return unlink(node(index));
    }

// unlink 从字面意思上来看 是断开连接的 意思，也就是说移除以为这 把这个节点的头尾给弄断 指向新的 代码对应下图
 E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item; //节点数据
        final Node<E> next = x.next; /对应图中 ai+1
        final Node<E> prev = x.prev;//对应图中 ai-1

        if (prev == null) {//判断 x是不是头节点 是头节点 只需要把 ai+1 指向头节点
            first = next;
        } else {
            prev.next = next;// 对应图中 步骤1 
            x.prev = null;
        }

        if (next == null) {/判断 x是不是尾节点 是尾节点 只需要把 ai-1 指向尾节点
            last = prev;
        } else {
            next.prev = prev;;// 对应图中 步骤2 
            x.next = null;
        }

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

删除元素.png

• E remove()
• E removeFirst()
• E removeLast()
• boolean removeFirstOccurrence(Object o)
• boolean removeLastOccurrence(Object o)
• boolean removeIf(Predicate<? super E> filter)
• E poll()
• E pollFirst()
• E pollLast()

LinkedList 修改

• E set(int index, E element)

public E set(int index, E element) {
        checkElementIndex(index);//判断index是否合法 --> index >= 0 && index <= size
        Node<E> x = node(index); //查找下标为 index的节点
        E oldVal = x.item; //保存旧的数据 
        x.item = element;//赋值新的数据
        return oldVal;
    }

---

在这里我仅仅把源码中的一部分拿出来 做了解释 其中还有大量的方法，需要各位大神自己观看源码，看完这些源码让我们不得不感叹谷歌程序员的思维和对代码的封装，本人自己也刚开始着手写文章，很多地方都有不足，很多时候想写但又不知道从哪里下手，感觉写的乱七八糟的，最终还是下定决心写，就算乱七八糟也写写吧，至少可以提升自己，如果有什么地方写的不对，请大家指正，或者有什么地方写的不好的也请大家提供宝贵的意见