List接口常用实现类的特点和底层实现

你的名字 2021-09-14 02:00 318阅读 0赞

List接口常用的实现类有3个：ArrayList、LinkedList、Vector。

那么它们的特点和底层实现有哪些呢？

**ArrayList特点和底层实现**

**ArrayList**底层是用数组实现的存储。

特点：查询效率高，增删效率低，线程不安全。我们一般使用它。

![20170802154252508][]

![Image 1][]

图1

查看源码，我们可以看出ArrayList底层使用Object数组来存储元素数据。所有的方法，都围绕这个核心的Object数组来开展。

ArrayList是可以存放任意数量的对象，数组长度是有限的，那么是怎么实现的呢？

本质上就是通过定义新的更大的数组，将旧数组内容拷贝到新数组，来实现扩容。

ArrayList的Object数组初始化长度为10，如果我们存储满了这个数组，需要存储第11个对象，就会定义新的数组长度长度更大的数组，并将将原数组内容和新的元素一起加入到新数组中，源码中代码如下：

**public void**   ensureCapacity(**int**   minCapacity) \{

modCount++;

**int**   oldCapacity = elementData.length;

**if**   (minCapacity > oldCapacity) \{

Object oldData\[\] =   elementData;

**int**   newCapacity = (oldCapacity \* 3)/2 + 1;

**if**   (newCapacity < minCapacity)

newCapacity = minCapacity;

//   minCapacity is usually close to size, so this is a win:

elementData =   Arrays.copyOf(elementData, newCapacity);

\}

\}

**LinkedList特点和底层实现**

LinkedList底层用双向链表实现的存储。

特点：查询效率低，增删效率高，线程不安全。

双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。 所以，从双向链表中的任意一个节点开始，都可以很方便地找到所有节点。

![Image 1][]

每个节点都应该有3部分内容：

**class**  Node \{

Node  previous;   //前一个节点

Object  element;    //本节点保存的数据

Node  next;       //后一个节点

\}

我们查看LinkedList的源码，可以看到里面包含了双向链表的相关代码：

![20170802154257804][]

![Image 1][]

图2

注：entry在英文中表示“进入、词条、条目”的意思。在计算机英语中一般表示“项、条目”的含义。

**Vector向量**

Vector底层用数组实现的List，相关的方法都加了同步检查，因此“线程安全,效率低”。 比如，indexOf方法就增加了synchronized同步标记。

![Image 1][]

![20170802154305209][]

【图3】Vector的源码(indexOf方法)

**建议**

如何选用ArrayList、LinkedList、Vector?

·线程安全时，用Vector。

**· **局部变量不存在线程安全问题时，并且查找较多用ArrayList（一般使用它）

**·**局部变量不存在线程安全问题时，增加或删除元素较多用LinkedList。

[20170802154252508]: /images/20210813/58abbcd1c8b64162ad78c6ff883dbfd8.png
[Image 1]: 
[20170802154257804]: /images/20210813/c74d4bf0215c4fb297d907cfd9bf36cf.png
[20170802154305209]: /images/20210813/8eccf2c954ef453ba9aa2b20a7ae9196.png

发表评论取消回复

表情：

评论列表（有 0 条评论，318人围观）

还没有评论，来说两句吧...

相关阅读

相关【C++】String的语法及常用接口的底层实现详解

在C++中，string 是一个标准库类（class），用于处理字符串。它提供了一种更高级、更便捷的字符串操作方式，string 类提供了一系列成员函数和重载运算符，以便...

迈不过友情╰/ 2024年04月22日 22:17/ 0 赞/ 11 阅读

相关 C++ string类和常用接口的实现

*目录** C++ string类 string类的常用接口说明 string类(实现常用接口) --...

朱雀/ 2024年04月19日 10:17/ 0 赞/ 7 阅读

相关 [C++] string类常用接口的模拟实现

![在这里插入图片描述][afbb78f1d81f445f8c0a26aea0717753.gif_pic_center] 文章目录 1、前言 2、遍

短命女/ 2023年10月15日 08:18/ 0 赞/ 75 阅读

相关接口List常用实现类分析

List<E>常用的实现类包括：ArrayList<E>，LinkedList<E>，Stack<E>和Vector<E>。 ArrayList<E>：List 接

阳光穿透心脏的1/2处/ 2022年07月28日 04:09/ 0 赞/ 174 阅读

相关列表—List 底层实现

列表的元素构成一个线性逻辑次序，元素的物理地址可以任意。链表(linked list)是一种典型的动态存储结构，其中的数据分散为一系列节点单位。节点之间通过指针相互索引和访

Myth丶恋晨/ 2022年05月21日 11:10/ 0 赞/ 139 阅读

相关 Python list 底层实现

本文将介绍列表在 CPython中的实现，因为毕竟Cpython 又是 Python 最为常用的实现。 Python 中的列表非常强大，看看它的内部实现机制是怎么样的，一定非

柔情只为你懂/ 2022年04月18日 00:56/ 0 赞/ 261 阅读

相关 List接口和Set接口及其常用实现类概述

一、List接口 List:有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位

小灰灰/ 2021年11月19日 13:20/ 0 赞/ 294 阅读

相关向量类Vector （实现了List接口）的常用方法

<table style="width:600px;"> <span style="color:f33b45;"><strong>描述方法</strong></span>

野性酷女/ 2021年11月01日 15:50/ 0 赞/ 265 阅读

相关 List接口常用实现类的特点和底层实现

List接口常用的实现类有3个：ArrayList、LinkedList、Vector。那么它们的特点和底层实现有哪些呢？ ArrayList特点和底层实现

你的名字/ 2021年09月14日 02:00/ 0 赞/ 319 阅读

相关 java集合框架子接口List和list的常用实现类

List接口和它的实现类们 List 常用方法(这里只介绍较于Collection接口新增加的方法) 1添加

「爱情、让人受尽委屈。」/ 2021年07月24日 19:53/ 0 赞/ 459 阅读