1. 链表概念

使用数组存储数据的缺陷:

插入和删除需要移动数据 复杂度为O(N) 不好

那么，是否有一种存储结构 可以在插入删除数据时不需要移动数据 ？

答案是链表

什么是链表 ?

链表是一种在逻辑上连续存储 但是在物理上(内存空间)中不一定连续的存储结构, 如下图

链表中的每一个元素都是一个节点对象

每个节点对象由两部分组成:

1. val 数值域，存储数据

2. next 指针域，存储下一个节点的地址

链表的分类

链表以单向/双向，带/不带头，循环/非循环分为8类

在这8种中，重点掌握单向不带头非循环链表和双向不带头非循环链表

因为笔试面试都是考单向不带头非循环（单链表），而双向不带头非循环链表是LinkList底层实现（双向链表）

什么是带头/不带头 ?

什么是循环和非循环 ?

单向/双向会在后序介绍双向链表时说明

2. 单链表结构及实现

单链表结构:

单链表的实现:

https://github.com/znxcmakhsd/DS/tree/main/12-14/MySingleList

一些重要操作的思路:

头插:

尾插:

index位置插入:

删除操作:

3. 双向链表结构及实现

结构:

实现:

https://github.com/znxcmakhsd/DS/tree/main/12-18/MyLinkedList

一些重要操作的实现思路:

4. ArrayList和LinkedList的区别

1. 从插入 删除 查找 修改来说

如果数据需要频繁的插入或者是删除，使用LinkedList

因为LinkedList底层是用双向链表存储数据，插入删除数据只需要修改指向 不用移动数据，所以效率很高

如果数据需要被快速查找，使用ArrayList

因为ArrayList底层用数组存储数据，给定下标就能找到数据

2. 从底层实现来说

ArrayList底层用数组实现，以1.5倍扩容，可以会浪费空间

LinkedList底层用双向链表实现，数据节点随用随建，不需要扩容不会浪费空间