线性表

要想知道它们俩的区别，首先就得明白ArrayList和LinkList都属于线性表。

1.它们都属于线性表，那么线性表的定义是什么？

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

上方标蓝的就是它的第一个不同点：

• ArrayList（数组列表）：在物理结构上连续的线性表。例如火车车厢

• LinkList （链接列表）：在逻辑结构上连续的，在物理结构不一定连续的线性表。例如排名册中同性别的不一定都是排在一起的。

访问和修改的时间复杂度

1. 随机查找访问ArrayList

假设我们要访问5，那么我们能直接去访问吗？

可以的，直接通过下标访问arraylist[4]就行了。

• ArrayList 内部是通过数组实现的，数组在内存中是连续存储的因此可以直接通过索引来访问任意位置的元素。
• 由于数组是连续存储的，无论是访问第一个元素还是最后一个元素，都可以在常数时间内完成，即时间复杂度为** O(1)**。

2. 随机查找访问LinkList

• 假设我们要访问3，那么我能直接去访问吗？

好像不行，我们要访问3，3的地址0x33的话，2存着的；那么就需要通过访问2来访问3，而2的地址0x22，1存着。那么我们就得从1（头节点） 开始。这时候我们是不是明白了为什么不能直接访问——这就是第二个区别-访问和修改的时间复杂度不同。

• LinkedList 内部是通过链表实现的，链表中的每个节点都包含一个指向下一个节点的引用。
• 对于 LinkedList，要想访问第 n 个元素，需要从链表的头节点开始，依次沿着指针往后遍历 n 次，直到找到第 n 个节点。
• 因此，访问 LinkedList 中第 n 个元素的时间复杂度是 O(n)，因为需要遍历整个链表。

插入和删除的时间复杂度

众所周知，表格都是动态变化的，我们可以任意的添加东西进去。

那么对ArrayList和LinkList这两个表来说，能任意添加东西进去也是基本的功能。

对于ArrayList

在排队的时候，第一个人的前面插进去了一个人，那么我们整体都得往后挪一挪，牵一发而动全身。对于ArrayList来说就是头部插入了一个元素，数组长度+1，其他元素往后挪一位。

删除也是同理，所以这就造成了插入和删除的时间复杂度为O(n)

对于LinkList

头部插入或删除一个元素，我们只需要将修改相邻节点的指针，而不需要移动其他节点，所以插入和删除的时间复杂度为 O(1)。

容量范围的区别

ArrayList 内部是通过数组实现的，那么只要是数组，就会出现不够用的情况，容量不够就需要扩容了。

而对于LinkList，它就像是排长龙一样，可以一直往后面接，来一个接一个，没有限制，它没有容量这一说法。

使用情况

根据二者的复杂度情况，我们分为两种：

1. 插入和删除

LinkList的时间复杂度为O(1)，ArrayList的时间复杂度为O(n)；所以我们在频繁使用插入和删除的场景下常常使用LinkList。

1. 访问和修改

LinkList的时间复杂度为O(n)，ArrayList的时间复杂度为O(1),所以我们在频繁访问的场景下常常使用ArrayList。

总结