线性表总结 - Xiasm/Java-Android-Learn GitHub Wiki

时间复杂度

O(n) = n^2 + xn + y

function1() {
   for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j ++) {
            // dosomething;
        }   
    }

    for(int i = 0; i < n; i++) {
    //dosomething   
    }

   // dosomething
}

function1的时间复杂度为n^2 + n + k = n^2

数据的逻辑结构

1.线性结构 2.集合结构 3.树形结构 4.图形结构

线性表

线性表分为两种：顺序存储结构---链式存储结构

顺序表
  • 顺序表--代表：数组 ArrayList

顺序表的内存结构是连续的一块内存，所以中间插入或删除元素的效率非常低，尾插效率高，随机访问效率高

ArrayList源码解析

顺序表的代表就是ArrayList了，ArrayList的源码中，如下关键可知其为顺序存储结构(因为数组就是一块连续的存储空间)：

transient Object[] elementData;
private int size;
//顺序表默认大小
private static final int DEFAULT_CAPACITY = 10;
  • 添加元素，即插入操作

我们先看末尾添加一个元素，即 add() 方法：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

//确保添加的元素不会越界
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

//如果添加的元素的序号大于数组长度，将数组增大
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//可以看到，grow方法是通过拷贝来实现数组大小改变的
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);
}

我们来看下内部插入一个元素的实现，即 add(int index, E element) 方法：

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

插入的过程调用了本地方法arraycopy，内部实现原理为插入的index前边的元素保持不动，后边的元素通通往后移了一位，总之看得出来，插入的操作非常耗性能。

  • 删除元素
//首先遍历一次数组，找到要删除的元素，然后调用fastRemove()
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

//fastRemove()方法会调用System.arraycopy重新对数组进行位移操作，把index后面的所有元素往前面挪一位
private void fastRemove(int index) {
    modCount++;
    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
}

可见，删除元素也会很耗性能，时间复杂都是n^2。

链表

链表有单链表、单循环链表、双链表、双循环链表等。链表的逻辑结构是相连的，内存结构是离散的，在C语言中有指针的概念，指针指向的是一块内存的地址，而java中将指针封装了，大家可以把一个对象的引用理解为指向这个对象的内存区域，为什么要谈起指针，是因为链需要用到指针的概念。

  • 链表的优缺点：

链表的优点是插入或删除一个元素非常简单，时间复杂度为O1，缺点是查找一个元素需要遍历找到，耗性能，随机访问需要遍历。

  • 应用场景：MessageQueue、LinkedList
LinkedList源码解析

LinkedList内部是如何使用指针(或者理解为java中的引用)呢？下面我们来看源码：

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

这是LinkedList的内部类，就是存储LinkedList中一个节点的指针域与数据域的类，Node类里有三个属性，分别是item、next、prev，item就可以理解为数据域，prev就是这个节点的前驱，next就是这个节点的后继。由此可见这是一个双向链表，有前驱和后继。

  • 添加元素
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

可以看到，add方法就是将要添加的节点添加到LinkedList的最后一个节点，如果LinkedList的尾节点为空，则将新添加的元素同时作为头节点和尾节点。

  • 获取元素
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

可以看到，得到一个元素必须要通过遍历，所以链表查找一个元素要比顺序表耗性能。可以看到遍历的时候有个小优化，如果要查找的元素在前半段，则从头节点开始遍历，否则从尾节点遍历。

思考

既然我们知道了顺序表和链表的优缺点，想个问题，QQ的消息页面是一个RecycleView或ListView，有新消息就会到第一个位置，那么这种数据结构是顺序表还是链表呢？肯定是链表，如果是顺序表，不断的将新消息移到首位，进行数组元素的位移，那将会非常的耗性能。

⚠️ **GitHub.com Fallback** ⚠️