算法与数据结构(1),List

习惯了,深夜更新博客,夜色虽美,但无心光顾。静谧的夜,带给属于我的,安静的王国。

算法,设计模式,数据结构,我是有所了解的,但是关于git,简直菜到了谷底。

哦,对了,记得前一阵子,遇到一个问题,大概的意思就是说,不使用List集合,实现对象的增加和删除,我之所要写这篇博,是因为我现在仍然不能写出满意的结果,希望你能在看过之后,有所灵感,然后实现它。

本篇,依然从我的知识和思路出发,带大家了解List数据结构。

List类族

可以说三种List均来自AbstractList,而AbstractList又实现了List接口,并继承了AbstractCollection。

ArrayList和Vector底层实现为数组,可以说这两种List内部封装了数组的操作,几乎使用了同样的算法,唯一的区别就是对多线程的支持。ArrayList没有对任何一个方法做线程同步,因此不是线程安全的。Vector中绝大部分方法都做了线程同步,是一种线程安全的实现。因此,ArrayList和Vector的性能特性相差无几,虽然从理论上来说,没有实现线程同步的ArrayList要稍好于Vector,但是我依然查看了很多其他技术文章,得出的结论是,他俩在实际生产环境中的差异并不明显,几乎可以忽略不计。

LinkedList使用了循环双向列表数据结构,由一系列表项连接而成。一个表项总是包括三个部分:元素内容,前驱表项和后驱表项。(为了节省图片宽度,严格意义上的前驱表项应该指向前方,与后驱表项方向相反,在此不做修改。)

LinkedList表项结构

下图展示了一个包含了三个元素的LinkedList,元素之间各个表项的连接关系。无论LinkedList是否为空,链表内部都有一个header表项,它既表示链表的开始,也表示链表的结尾。表项header,的后驱表项表示第一个元素,前驱表项表示链表中最后一个元素。

LinkedList表项关系

由于没能拿到libcore的源码,这里只能贴出JDK的实现,通过比较,个人感觉还是JDK的实现更好一些。

增加元素到列表尾端

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);//确保内部数组有足够的空间
    elementData[size++] = e;         //将元素添加到数组末尾
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    modCount++;                     //修改次数加一
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); //扩容到原始容量的1.5倍
    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);//完成扩容,并复制数组
}

当ArrayList对容量的需求超过当前数组大小时,才需要扩容,扩容过程中,会进行大量的数组复制操作,最终调用是本地方法System.arraycopy( ),虽然本地复制效率较高,速度较快,但是,如果ArrayList,内部数组增长过快,频繁的进行扩容,add( )操作还是较慢的,但一般情况我们并不会疯狂的向ArrayList中塞数据,因此,ArrayList.add( ),效率还是不错的。

LinkedList构造函数中初始化了一个header表项,前驱表项和后驱表项均是自己,是一个只有一个元素的,闭合的链表结构。

LinkedList.add( ),将元素添加至链表末端。header元素的前驱表项正是List中最后一个元素,因此将新元素创建出来的同时增加到header之前,就相当于在List最后插入元素。

/**
 * Constructs a new empty instance of {@code LinkedList}.
 */
public LinkedList() {
    voidLink = new Link<E>(null, null, null);
    voidLink.previous = voidLink;
    voidLink.next = voidLink;
}

@Override
public boolean add(E object) {
    return addLastImpl(object);
}

private boolean addLastImpl(E object) {
    Link<E> oldLast = voidLink.previous;
    Link<E> newLink = new Link<E>(object, oldLast, voidLink);
    voidLink.previous = newLink;
    oldLast.next = newLink;
    size++;
    modCount++;
    return true;
}

虽然,LinkedList使用了链表结构,不需要考虑容量的大小,从这一点上说效率是高于ArrayList,然而每次元素的增加都需要新建一个Link对象,并进行赋值操作,如果频繁使用,依然会消耗资源,对效率产生一定影响,在JDK中(SDK中由于没能拿到libcore源码,初始容量未知)ArrayList的初始容量是10,所以绝大情况下的追加操作,ArrayList不需要频繁扩容,效率还是蛮高的。

增加元素到列表任意位置

由于实现不同,ArrayList和LinkedList在这个方法上存在很大差异,由于ArrayList是基于数组实现的,而所谓的数组就是一块连续的内存空间,如果在数组的任意位置插入元素,必然导致在该位置后的所有元素都要重新排列,因此,效率会相对较低。

/**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index   index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,  size - index);
    elementData[index] = element;
    size++;
}

/**
 * A version of rangeCheck used by add and addAll.
 */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

可以看到每次插入操作,都会进行一次数组复制。而这个操作在增加元素到List尾端的时候是不存在的。大量的数组操作会导致系统性能低下。并且,插入的元素在List中的位置越靠前,数组充足的开销也越大。所以,使用ArrayList应尽可能的将元素插入List尾端附近,有助于提高该方法的性能。

LinkedList的插入在此时便显出优势,首先判断插入元素位置,如果处于整个List前半段,则从前向后遍历,若其位置处于后半段,则从后向前遍历,找到插入位置的元素Link,进行链表的重新连接。

/**
 * Inserts the specified object into this {@code LinkedList} at the
 * specified location. The object is inserted before any previous element at
 * the specified location. If the location is equal to the size of this
 * {@code LinkedList}, the object is added at the end.
 *
 * @param location the index at which to insert.
 * @param object   the object to add.
 * @throws IndexOutOfBoundsException if {@code location < 0 || location > size()}
 */

@Override
public void add(int location, E object) {
    if (location >= 0 && location <= size) {
        Link<E> link = voidLink;
        if (location < (size / 2)) {
            for (int i = 0; i <= location; i++) {
                link = link.next;
            }
        } else {
            for (int i = size; i > location; i--) {
                link = link.previous;
            }
        }
        Link<E> previous = link.previous;
        Link<E> newLink = new Link<E>(object, previous, link);
        previous.next = newLink;
        link.previous = newLink;
        size++;
        modCount++;
    } else {
        throw new IndexOutOfBoundsException();
    }
}

可见对LinkedList来说,在List尾端插入数据和在任意位置插入数据是一样的。并不会因为插入数据的位置靠前而导致性能的降低。所以,如果在实际生成环境中,需要频繁的在任意位置插入元素,可以考虑用LinkedList代替ArrayList。

删除任意位置元素

对ArrayList来说,remove( )add( )方法是类似的,在任意位置移除元素之后,都要进行数组的复制和重组。

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 *
 * @param index the index of the element to be removed
 * @return the element that was removed from the list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        //将删除元素所在位置,后面的所有元素往前移动一位
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);

    //最后一个位置元素置null
    elementData[--size] = null; // Let gc do its work

    return oldValue;
}

由源码可以看到,在ArrayList的每一次有效的元素删除操作之后,都要进行数组的复制和重组,并将List队列尾端的元素置null,如果删除的元素越靠前,数组重组时的开销就越大,位置越靠后,开销越小。

LinkedList中的remove( )和添加任意位置元素是类似的,首先通过循环找到要删除的元素,如果要删除的元素处于List位置前半段,则从前往后找;若其位置处于后半段,则从后往前找。因此无论要删除较为靠前或者靠后的元素都是非常高效的:但要移除List中间的元素几乎要遍历完半个List,在List拥有大量元素的情况下,效率很低。

/**
 * Removes the object at the specified location from this {@code LinkedList}.
 *
 * @param location the index of the object to remove
 * @return the removed object
 * @throws IndexOutOfBoundsException if {@code location < 0 || location >= size()}
 */
@Override
public E remove(int location) {
    if (location >= 0 && location < size) {
        Link<E> link = voidLink;
        if (location < (size / 2)) {
            for (int i = 0; i <= location; i++) {
                link = link.next;
            }
        } else {
            for (int i = size; i > location; i--) {
                link = link.previous;
            }
        }
        Link<E> previous = link.previous;
        Link<E> next = link.next;
        previous.next = next;
        next.previous = previous;
        size--;
        modCount++;
        return link.data;
    }
    throw new IndexOutOfBoundsException();
}
List遍历

List集合,三种遍历方式。

        List<String> list = null;
        String temp;

        /*迭代器循环*/
        for (Iterator iterator = list.iterator(); iterator.hasNext(); ) {
            temo= (String) iterator.next();
        }

        /*ForEach*/
        for (String string : list) {
            temp = string;
        }

        /*for循环,随机访问*/
        for (int i = 0; i < list.size(); i++) {
            temp = list.get(i);
        }

迭代器:ArrayList和LinkedList在迭代器模式中都表现出良好的性能。

ForEach:ArrayList和LinkedList在该遍历模式中效率不及迭代器,通过度娘,找到了ForEach反编译后的样子,性能降低原因是,多余的一步字符串赋值操作。

        /*ForEach反编译解析*/
        for (Iterator iterator = list.iterator(); iterator.hasNext(); ) {
            String s = (String) iterator.next();
            String s1 = s;          //多余的操作
        }

fot循环:基于数组的List都实现了RandomAccess接口,如ArrayList和Vector,没有实现的以LinkedList为代表。实现RandomAccess接口的List,当元素数量较多时,通过直接的随机访问比通过迭代的方式,可提升大约10%的性能(谢谢度娘)。如果LinkedList采用随机访问,总是要进行一次遍历查找,虽然通过双向循环链表的特性,将平均查找的次数减半,但是其遍历过程依然会消耗大量cpu资源。

片尾Tip:通过RandomAccess可知道List是否支持快速随机访问。同时,需要记住,如果程序需要使用通过下标对List进行随机访问,尽量不要使用LinkedList,ArrayList和Vector都是不错的选择。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏冷冷

ArrayList foreach 循环里进行元素的 remove add 操作有什么现象?

先来看看《阿里巴巴Java开发手册》中的一段 【强制】不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Itera...

31080
来自专栏Java爬坑系列

【Java入门提高篇】Day34 Java容器类详解(十五)WeakHashMap详解

在Java容器详解系列文章的最后,介绍一个相对特殊的成员:WeakHashMap,从名字可以看出它是一个 Map。它的使用上跟HashMap并没有什么区别,所以...

14340
来自专栏包子铺里聊IT

How to find the lowest common ancestor in a tree 最近公共祖先

[题目] 求二叉树的任意两个节点的最近公共祖先。 此题有多个扩展问题: 如果只查询一次,二叉树给出向上(parent)链接和不给向上链接时分别有什么解法,最佳空...

28440
来自专栏mathor

线性表(一)

12620
来自专栏决胜机器学习

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十三) ——动态查找表(二叉排序树) (原创内容,转载请注明来源,谢谢) 一、概念 1、动态查找表特点 当对动态查找表进行查...

557100
来自专栏JavaQ

HashMap死循环精简说

在JDK1.8之前的版本中,HashMap的底层实现是数组+链表。当调用HashMap的put方法添加元素时,如果新元素的hash值或key在原Map中不存在,...

12130
来自专栏算法channel

图解用栈数据结构对树的遍历

本公众号主要推送关于如何构思算法使之应用到我们的工作中。计算机常用算法思想大致来说有,分而治之,动态规划,贪心算法,搜索算法,回溯 ,训练这些思维的一个很好的平...

385110
来自专栏机器学习与自然语言处理

二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历

  对于一种数据结构而言,遍历是常见操作。二叉树是一种基本的数据结构,是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下: 1 typedef str...

37160
来自专栏Android机动车

Java 基础(五)——集合源码解析 Set

前面我们学了 List 集合。我们知道 List 是一个有序的集合,可以根据元素的整数索引访问元素,并且允许重复。

10810
来自专栏数据结构笔记

数据结构(三):线性表

该序列中所含的元素个数叫做线性表的长度,用 n表示(n>=0)。当 n=0时,表示线性表是一个空表,即表中不包含任何数据元素。

21560

扫码关注云+社区

领取腾讯云代金券