LinkedList浅析

LinkedList浅析LinkedList简介LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList实现List接口,能对它进行队列操作。LinkedList实现Deque接口,即能将LinkedList当作双端队列使用。LinkedList实现了Cloneable接口,即覆盖了函数clon…

大家好,又见面了,我是你们的朋友全栈君。


LinkedList是Collection下的一个list实现,就像ArrayList一样。

和ArrayList不同的是它是链表结构,而ArrayList是顺序结构。我们平常使用的list是一样的,理论上来说一种list就可以完成我们所有的需求。但是它们在运行过程中有区别的,完成需求所需要的资源也不相同,至于什么情况下使用哪种list就看需求和当前情况了。


视频:


LinkedList 是一个继承于AbstractSequentialList的双向链表
LinkedList 可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口,所以能对它进行队列操作
LinkedList 实现 Deque 接口,能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
LinkedList 实现java.io.Serializable接口,所以LinkedList支持序列化,能通过序列化去传输。
LinkedList 是非同步的。

java集合

构造函数

// 默认构造函数
LinkedList()

// 创建一个LinkedList,保护Collection中的全部元素。
LinkedList(Collection<? extends E> collection)

LinkedList的本质是双向链表

  1. LinkedList继承于AbstractSequentialList,并且实现了Dequeue接口。
  2. LinkedList包含两个重要的成员:header 和 size。
      header是双向链表的表头,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量: previous, next, element。其中,previous是该节点的上一个节点,next是该节点的下一个节点,element是该节点所包含的值。
      size是双向链表中节点的个数。

##双向链表结构

  • 链表:链表是一种重要的数据结构,有单链表和双链表之分

单链表:

单链表(单向链表):由两部分组成 数据域(Data)和结点域(Node),单链表就像是一条打了很多结的绳子,每一个绳结相当于一个结点,每个节结点间都有绳子连接,这样原理的实现是通过Node结点区的头指针head实现的,每个结点都有一个指针,每个节点指针的指向都是指向自身结点的下一个结点,最后一个结点的head指向为null,这样一来就连成了上述所说绳子一样的链,对单链表的操作只能从一端开始,如果需要查找链表中的某一个结点,则需要从头开始进行遍历。

双向链表结构

双链表(双向链表):双链表和单链表相比,多了一个指向尾指针(tail),双链表的每个结点都有一个头指针head和尾指针tail,双链表相比单链表更容易操作,双链表结点的首结点的head指向为null,tail指向下一个节点的tail;尾结点的head指向前一个结点的head,tail 指向为null,是双向的关系;
在单链表中若需要查找某一个元素时,都必须从第一个元素开始进行查找,而双向链表除开头节点和最后一个节点外每个节点中储存有两个指针,这连个指针分别指向前一个节点的地址和后一个节点的地址,这样无论通过那个节点都能够寻找到其他的节点。

  • 插入删除不需要移动元素外,可以原地插入删除
  • 可以在结构的前后插入数据
  • 可以双向遍历

###链表


AbstractSequentialList

Linklist是AbstractSequentialList的子类

AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数。这些接口都是随机访问List的,LinkedList是双向链表;既然它继承于AbstractSequentialList,就相当于已经实现了“get(int index)这些接口”。
此外,我们若需要通过AbstractSequentialList自己实现一个列表,只需要扩展此类,并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表,则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。

LinkedList的继承关系:

java.lang.Object
   ↳ java.util.AbstractCollection<E>
         ↳ java.util.AbstractList<E>
               ↳ java.util.AbstractSequentialList<E>
                     ↳  java.util.LinkedList<E>

    public class LinkedList<E>
         extends AbstractSequentialList<E>
            implements List<E>, Deque<E>, Cloneable, java.io.Serializable { …… }

LinkedList与Collection关系

Collection:

Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的“子接口”如List和Set。

LinkedList浅析


LinkedList的本质是双链表,实现 List 和 Deque接口:

LinkedList浅析

在LinkedList中,每个节点都用内部类Node表示:

LinkedList浅析

具体的过程可以看下面这张图:
点我

每个node都是节点,里面有三个属性,分别指向上一个节点、下一个节点、实际储存元素开辟的内存空间

而对linkedlist里元素的操作方法都是对这些节点进行操作:

add()操作:

 /**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    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++;
    }

remove()操作

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

	//查找对应索引
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * Unlinks non-null node x.
     */
    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;
    }


可以看到都是对node节点进行操作,真实的实例内存并没有任何改变,等着jvm回收。


List使用场景

ArrayList在随机访问方面比较擅长,LinkedList在随机增删方面比较擅长
对于需要快速插入,删除元素,使用LinkedList。因为ArrayList要想在数组中任意两个元素中间添加对象时,数组需要移动所有后面的对象。
对于需要快速随机访问元素(get()),应该使用ArrayList,因为LinkedList要移动指针、遍历节点来定位,所以速度慢。
对于“单线程环境” 或者 “多线程环境,但List仅仅只会被单个线程操作”,此时应该使用非同步的类(如ArrayList)。
对于“多线程环境,且List可能同时被多个线程操作”,此时,应该使用同步的类(如Vector)。

对于插入数据使用时间的对比:

  public static void addTest(){

        //批量插入,每次都向首位插入数据;

        LinkedList linkedList = new LinkedList();

        long time1 = new Date().getTime();

        for(int m=0;m<300000;m++){
            linkedList.add(0,null);
        }

        long time2 = new Date().getTime();

        System.out.print("linkedList批量插入时间:"+(time2 - time1)+"ms\n");




        ArrayList arraylist = new ArrayList();

        long time3 = new Date().getTime();

        for(int n=0;n<300000;n++){
            arraylist.add(0, null);
        }

        long time4 = new Date().getTime();
        System.out.print("arrayList批量插入时间:"+(time4 - time3)+"ms\n");

    }

结果:

linkedList批量插入时间:9ms
arrayList批量插入时间:3696ms


那么问题就来了:

Q:什么时候使用Arraylist,什么时候使用LinkedList?
A:当你需要频繁查询数组的时候使用ArrayList比较快,当你需要频繁操作数组进行增删插入操作的时候使用LinkList比较合适。当然直接在末尾添加数据ArrayList用时也不是特别多,因为在末尾操作后面没有数据。

Q:那什么时候适合用list呢
A:涉及到“栈”、“队列”、“链表”等操作,应该考虑用List,具体的选择哪个List,根据下面的标准来取舍

  • 对于需要快速插入,删除元素,应该使用LinkedList。
  • 对于需要快速随机访问元素,应该使用ArrayList。
  • 对于“单线程环境” 或者 “多线程环境,但List仅仅只会被单个线程操作”,此时应该使用非同步的类(如ArrayList)。
  • 对于“多线程环境,且List可能同时被多个线程操作”,此时,应该使用同步的类(如Vector)。

Q:线程安全的数组,什么是线程安全?
A:线程安全就是当前资源只能被单独一个线程访问,也就是加同步锁的线程。默认的线程安全的list是Vector;


以上,如果有哪里不对或者不清楚的地方欢迎勾搭,多谢指正

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/148212.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • vmware15最新激活码2021-激活码分享

    (vmware15最新激活码2021)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html92U4ILM59M-eyJsa…

  • springboot框架简介_springboot工作原理

    springboot框架简介_springboot工作原理springboot介绍1、springboot概述springboot对spring的缺点进行改善和优化,基于约定优化配置的思想,可以让开发人员不必在配置与逻辑业务之间进行思维的切换,全身心的投入到逻辑业务的代码编写中,从而大大提高了开发效率,也可以缩短项目周期。2、springboot特点为基于spring开发提供更快的入门体验。开箱即用,不需要代码生成,也不需要xml配置,同时也可以修改默认值来满足特定的需求。提供了一些大型项目中常见的非功能特性,如嵌入式服务器、安全、指标,健康检测、外部

  • mysql添加字段的sql语句_mysql增加字段的语句

    mysql添加字段的sql语句_mysql增加字段的语句myesl是一个关系型数据库管理系统,也是目前最流行的管理系统之一,目前网页设计方面对一个系统的使用频率是比较高的,因此想要学会网页设计,那么有关myesl的基础知识以及应用就一定要掌握。而今天我们就来看一看myesl增加字段是如何操作的。mysql增加字段——mysql数据库更新字段语句一、UPDATE:UPDATE的功能是更新表中的数据。这的语法和INSERT的第二种用法相似。必须提供表名以及…

    2022年10月26日
  • Laravel5中使用阿里大于(鱼)发送短信验证码

    Laravel5中使用阿里大于(鱼)发送短信验证码

    2021年10月13日
  • [Java基础]StringUtils.join()方法与String.join()方法的使用

    [Java基础]StringUtils.join()方法与String.join()方法的使用StringUtils.join()和String.join()用途:将数组或集合以某拼接符拼接到一起形成新的字符串。1.StringUtils.join()方法:(1)使用前需先引入common-lang3的jar包,可去官网下载:apache官网下载页面(2)方法如下图:(3)基本上此方法需传入2个参数,第一个参数是传入一个任意类型数组或集合,第二个参数是拼接符。…

  • EPPLUS 分组

    EPPLUS 分组使用EPPLUS,导出的EXCEL文件中分组publicvoidRow_Col_Grouping_Test(){//http://stackoverflow.com/questions/32760210/how-to-group-rows-columns-in-epplus//Throwinsomedatavardatatable=newDa

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号