LinkedList链表知识点概括(一）_linkedlist最多可以容纳多少个元素

作者：爱塔居的博客_CSDN博客-JavaSE,数据结构领域博主

专栏：数据结构

作者简介：大三学生，希望2023年迎来更优秀的自己！希望跟大家一同进步~

前言

顺序表/ArrayList:

优点：当给定下标的时候，查找速度非常快，适合给定下表的查找，时间复杂度为O（1）；

缺点：插入必须要挪动元素，然后才能插入；删除必须挪动元素，才能删除。另外每次扩容也是浪费资源的。因为扩容的时候是1.5倍扩容。比如已经有10个元素了，要放第11个元素，就要扩容到15个，但只有11个元素，就有4个是浪费的。

ArrayList不适合做任意位置的插入和删除比较多的场景。

为了解决这些问题，我们可以使用链式存储：链表。

例题：关于链表和顺序表间的区别，叙述错误的是（D    ）

A.链表和顺序表都属于线性表

B.链表不能随机访问其中的某个元素，顺序表可以

C.链表能做的事，顺序表都可以完成，只是操作方法不同，效率不同

D.链表在进行插入和删除的时候，速度总是比顺序表快

解析：链表的插入和删除不是所有情况下都比顺序表快，比如尾插尾删，顺序表的时间复杂度为O（1），并且如果是单链表，如果要在中间某个节点的前面插入/删除一个节点，则需要遍历。所以时间的快慢要分情况看待。

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列...
 

---

 

一、链表的基本概念

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 ，就像火车，一节节的车厢可以看作是节点（结点）。

val：存储数据

next：存储下一个节点的地址（作用是连接当前节点和下一个节点）

  本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/863548