[TOC]

线性表-List

list是最简单的数据结构，可分为顺序表与链表，顺序表内部数据存储由数组实现，链表则是由一个个自定义的节点Node进行串联，就像锁链一样

List接口主要方法

• int size();：表长度
• boolean isEmpty();：表是否为空
• boolean add(int index, E element);：添加元素
• boolean remove(int index);：：移除元素

顺序表--实现类ArrayList

因为内部是由数组实现（数组初始化时长度即固定），所有顺序表在增加元素时有动态扩容的需求，且元素发生变换时（物理地址连续），容易频繁引起数组的批量复制修改；

• transient Object[] elementData;：内部存储数组

• 增：元素添加时，如果中间插入还会触发对应位置及后续元素整体后移，如果size不满足增加后大小则会触发动态增长

  public void add(int index, E element) {
      if (index > size || index < 0)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      System.arraycopy(elementData, index, elementData, index + 1,
                       size - index);
      elementData[index] = element;
      size++;
  }
  

  元素添加时，会进行size大小的校验，if (minCapacity - elementData.length > 0) grow(minCapacity);通过后就会触发增长，

  private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       elementData = Arrays.copyOf(elementData, newCapacity);
  }
  

• 删：删除对应位置的元素，后续元素copy并前移

   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;
   }
  

链表--实现类LinkedList

链表内部是由自定义的节点进行连接的，所以能查找上一节点与下一节点的称为双链表，只能查找下一节点的称为单链表。单链表由于只能从头往尾查询，在节点查找上效率比双链表低一半（双链表可以通过位置与长度比较判断离头尾哪个更近）

• Node：自定义存储节点

  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;：尾节点

• 增：触发指定位置的Node 及前Node的断裂与再连接

  public void add(int index, E element) {
      checkPositionIndex(index);
  
      if (index == size)
          linkLast(element);
      else
          linkBefore(element, node(index));
  }
  

  前节点preNode，指定位置节点node，添加节点newNode；

  1. newNode.prev = preNode;
  2. newNode.next = node;
  3. preNode.next = newNode;
  4. node.prev = newNode;

  在实际中要注意引用的变化，perNode一般是用node.prev来代替，如果node引用改变容易引起错误指向。同时注意前后节点不存在的情况（即头尾节点操作）

• 删：触发指定位置的Node 与前后Node的断裂与再连接

  public E remove(int index) {
      checkElementIndex(index);
      return unlink(node(index));
  }
  E unlink(Node<E> x) {
      // assert x != null;
      final E element = x.item;
      final Node<E> next = x.next;
      final Node<E> prev = x.prev;
  
      if (prev == null) {
          first = next;
      } else {
          prev.next = next;
          x.prev = null;
      }
  
      if (next == null) {
          last = prev;
      } else {
          next.prev = prev;
          x.next = null;
      }
  
      x.item = null;
      size--;
      modCount++;
      return element;
  }
  

  前节点preNode，指定位置节点node，后节点nextNode；

  1. preNode.next = nextNode;
  2. nextNode.prev = preNode;
  3. node.next = null;
  4. node.prev = null;
  5. node.item = null;

  同样注意：在实际中要注意引用的变化，perNode，nextNode一般是间接引用，如果node引用改变容易引起错误指向。同时注意前后节点不存在的情况（即头尾节点操作）

  链表的其他形式

  • 循环链表 ： 将单链表中终端节点的指针端由空指针改为指向头节点，就使整个单链表形成一个环，这种头尾相连的单链表称为单循环链表，简称循环链表
  • 双向循环链表 ： 双向循环链表是单向循环链表的每个节点中，再设置一个指向其前驱节点的指针域
    与双向链表的区别：双向链表没有闭合形成环，头节点、尾节点并不互相连接指向

对比

List	优点	缺点	应用
顺序表	存储空间连续、允许随机访问、尾插，尾删方便	插入效率低 删除效率低 长度固定	普遍在用(Android中基本存储查询操作较多，不涉及太多中间增删)
单链表	随意进行增删改、插入效率高、删除效率高、长度可以随意修改	内存不连续、不能随机查找、查询效率低	MessageQueue、HashMap
双链表	随意进行增删改、插入效率高、删除效率高、长度可以随意修改	内存不连续、不能随机查找、查询效率比单链表快一倍	LinkedList

相关算法题

1. 反转单链表 https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
2. 合并两个有序链表 https://leetcode-cn.com/problems/merge-two-sorted-lists/
3. 两数相加 https://leetcode-cn.com/problems/add-two-numbers/
4. 两两交换 https://leetcode-cn.com/problems/swap-nodes-in-pairs/