网站建设资讯

NEWS

网站建设资讯

Java中ArrayList与LinkedList的作用是什么

Java中ArrayList与LinkedList的作用是什么,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:域名与空间、网页空间、营销软件、网站建设、高青网站维护、网站推广。

1.1,链表

链表:linked list,由一系列结点node(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。我们常说的链表结构有单向链表与双向链表,那么这里给大家介绍的是单向链表。

简单的说,采用该结构的集合,对元素的存取有如下的特点:

多个结点之间,通过地址进行连接。例如,多个人手拉手,每个人使用自己的右手拉住下个人的左手,依次类推,这样多个人就连在一起了。

查找元素慢:想查找某个元素,需要通过连接的节点,依次向后查找指定元素。

增删元素快:

增加元素:只需要修改连接下个元素的地址即可。

删除元素:只需要修改连接下个元素的地址即可。

1.2,红黑树

红黑树是一种自平衡二叉查找树,是计算机科学领域中的一种数据结构,典型的用途是实现关联数组,存储有序的数据。

红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。

红黑树的约束:

节点可以是红色的或者黑色的。  根节点是黑色的。  叶子节点(特指空节点)是黑色的。  每个红色节点的子节点都是黑色的。  任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同。

红黑树的特点:

速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍。

二,List接口

2.1,简介

java.util.List接口继承自Collection接口,是单列集合的一个重要分支,习惯性地会将实现了List接口的对象称为List集合。在List集合中允许出现重复的元素,所有的元素是以一种线性方式进行存储的,在程序中可以通过索引来访问集合中的指定元素。另外,List集合还有一个特点就是元素有序,即元素的存入顺序和取出顺序一致。

那么List接口有什么特点。

它是一个元素存取有序的集合。例如,存元素的顺序是1、2、3。那么集合中,元素的存储就是按照1、2、3的顺序完成的)。  它是一个带有索引的集合,通过索引就可以精确的操作集合中的元素(与数组的索引是一个道理)。  集合中可以有重复的元素,通过元素的equals方法,来比较是否为重复的元素。

2.2,常用方法

List接口继承Collection接口,因此在父类接口中的方法,List子接口全部都有,并且还增加通过索引的方式操作数据。

public void add(int index, E element) : 将指定的元素,添加到该集合中的指定位置上。  public E get(int index) :返回集合中指定位置的元素。  public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。  public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

public class ListDemo { public static void main(String[] args) { // 创建List集合对象 List list = new ArrayList<>(); // 往尾部添加 指定元素 list.add("ABC"); list.add("张三"); list.add("李四"); System.out.println(list); // add(int index,String s) 往指定位置添加 list.add(1,"DEF"); System.out.println(list); // String remove(int index) 删除指定位置元素 返回被删除元素 // 删除索引位置为2的元素 System.out.println("删除索引位置为2的元素"); System.out.println(list.remove(2)); System.out.println(list); // String set(int index,String s) // 在指定位置进行元素替代(改) // 修改指定位置元素 list.set(0, "三毛"); System.out.println(list); // String get(int index) 获取指定位置元素 // 跟size() 方法一起用来遍历的 for(int i = 0;i

三,Array List(JDK8)

Array List底层是基于动态数组实现的,何以动态。在于它是一个可变的数组,根据实际情况它的容量可自动扩充,类似于在C语言中动态申请内存的原理。(题外话:记得有一次面试,面试官问我arraylist是怎么实现的,我说是一个动态数组。然后把他吓一跳,说一句让我想清楚再说。我还以为说错了,接着沉淀5秒钟,就是一个可自动扩容的动态数组)。

其特点是增删慢,查询快。因为是基于数组实现那么就会存在索引,增删就是对数据的更新,导致索引也会发生相应变化。但是存在索引值,所以对于查询数据来说就很快了。如图:

3.1,数组实现

为什么说底层是一个数组,请看源码:

ArrayList在初始化时默认的数组容量为10,源码如下:

3.2,构造方法

1,定义无参构造方法,初始化默认为10的空列表。

2,有参构造,并且自定义初始化容量的大小。

3,将数据类型转换为数组类型。

分析:

1,elementData = c.toArray();将元素转化成数组。

2,判断数组大小是否为0,否则将默认EMPTY_ELEMENTDATA赋值给数组。

3,接着里面的if判断,判断elementData是否成功转换为数组,如果成功则调用Arrays.copyOf方法将元素值,数组大小,及数组类复制值到elementData数组中。

完成以上初始化步骤之后,接着我们可以调用add方法完成数据添加。

3.3,add方法

先介绍没有指定索引的数据添加,请看add源码:

分析:

1,ensureCapacityInternal(size + 1);这个方法是判断在添加数据之前,数组的容量是否够用。这里就看下源码的实现吧。

判断是否要扩容。

说明:

首先size默认为0,然后size+1将参数传过来。判断if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)是不是第一次添加元素,如果是,则选取默认的容量大小10,正式将数组容量初始化为10.接着调用ensureExplicitCapacity(minCapacity);这里是判断是否需要进行扩容。这里我们假设不需要扩容,接着说完add方法最后一步。

2,elementData[size++] = e;最后执行这一步,将元素e添加到elementData数组中,并且大小加1,并完成元素添加。

3.4,扩容机制

上面我们说到在数组不扩容情况下元素是如何进行添加的,再来说说如何进行扩容。接着上面ensureExplicitCapacity(int minCapacity)这个方法,判断如果超出默认容量大小时,便调用grow(minCapacity);方法开始进行扩容。

在这里先指出扩容的机制其实就是数组的复制,创建一个新的数组,将小容量数组的元素复制到容量较大的数组中,以此完成数组的扩容。

接着我们看源码的实现:

分析:

1,获取旧数组的大小。

2,将大小扩大1.5倍。

3,新容量小于参数指定容量,修改新容量。

4,新容量大于最大容量,并指定新容量。

5,调用copyOf进行复制。

完成扩容。

四,线程不安全

Array List是线程不安全的,这点很重要,也是面试最常问的问题。那为什么是不安全的呢,下面简单总结以下。

情况一:

假设现在有A,B两个线程同时执行add方法,而现在size = 9,于是:

1,A经过以上步骤发现初始化容量为10,不需要进行数组扩容。

2,同时B也在执行add方法,它判断数组初始化容量也是10(size的值还是9),于是不进行数组扩容。接着A便执行add方法,元素添加成功后,size = 10;此时B开始执行add方法,但这个时候数组元素已经添加满了,B再添加就会造成数组下标越界异常。

情况二:

elementData[size++] = e;这一步也有可能出现问题。

列表大小为0,即size=0。 线程A开始添加一个元素,值为A。此时它执行第一条操作,将A放在了elementData下标为0的位置上。 接着线程B刚好也要开始添加一个值为B的元素,且走到了第一步操作。此时线程B获取到size的值依然为0,于是它将B也放在了elementData下标为0的位置上。 而最终size大小为:

线程A开始将size的值增加为1线程B开始将size的值增加为2

针对这种情况,可以使用以下方式解决:

List list1 = Collections.synchronizedList(new ArrayList());

五,Linked List

linked list数据存储的结构是双向链表结构。方便元素添加、删除的集合,但是查询较慢。

LinkedList中常用方法:

public void addFirst(E e):将指定元素插入此列表的开头。  public void addLast(E e):将指定元素添加到此列表的结尾。  public E getFirst():返回此列表的第一个元素。  public E getLast():返回此列表的最后一个元素。  public E removeFirst():移除并返回此列表的第一个元素。  public E removeLast():移除并返回此列表的最后一个元素。  public E pop():从此列表所表示的堆栈处弹出一个元素。  public void push(E e):将元素推入此列表所表示的堆栈。  public boolean isEmpty():如果列表不包含元素,则返回true。

public class LinkedListDemo { public static void main(String[] args) { LinkedList link = new LinkedList(); //添加元素 link.addFirst("abc1"); link.addFirst("abc2"); link.addFirst("abc3"); System.out.println(link); // 获取元素 System.out.println(link.getFirst()); System.out.println(link.getLast()); // 删除元素 System.out.println(link.removeFirst()); System.out.println(link.removeLast()); while (!link.isEmpty()) { //判断集合是否为空  System.out.println(link.pop()); //弹出集合中的栈顶元素 } System.out.println(link); }}

关于Java中ArrayList与LinkedList的作用是什么问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注创新互联行业资讯频道了解更多相关知识。


新闻名称:Java中ArrayList与LinkedList的作用是什么
分享URL:http://njwzjz.com/article/jidegi.html