浅谈线性表——链表
文章目录
- 一、ArrayList的缺陷
- 二、什么是链表？
- 三、自我实现一个单向不带头非循环结构的链表
- 3.1、实现代码
- 3.2、代码解析
- 四、自我实现一个双向不带头非循环结构的链表
- 4.1、实现代码
一、ArrayList的缺陷
前面学习了顺序表，顺序表在知道下标时可以快速的查找元素，但是：
a、顺序表尾插、尾删的时间复杂度为O(1)，但是中间/头部的插入删除时间复杂度为O(N)；
b、扩容时需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
c、 扩容一般是呈2倍的增长，势必会有一定的空间浪费。
因此引入了一种新的数据结构——链表，能够解决上述的问题。
二、什么是链表？
链表(LinkedList)：将数据以链式形式进行存储。链表中的每一个元素称为节点(结点)，节点中由2部分组成，一部分存放数据元素，一部分存放下一个数据元素的地址。
链表逻辑上是连续的，物理上不一定连续，是因为链表的连续性是通过地址连接起来，并不像顺序表那样是一段物理地址连续的存储单元依次存储数据元素。
三、自我实现一个单向不带头非循环结构的链表
3.1、实现代码
代码链接
3.2、代码解析
（1）、createMyLinkedList()方法
（2）、display()方法(遍历链表)
（3）、头插法：public void addFirst(int data)
时间、空间复杂度皆O(1)
（4）、尾插法：public void addLast(int data)
时间复杂度O(n)、空间复杂度O(1)
（5）、 随机插入：public void addIndex(int index,int data)
时间复杂度O(n)、空间复杂度O(1)
（6）、删除第一个出现的指定key节点： public void remove(int key)
时间复杂度O(n)、空间复杂度O(1)
（7）、删除链表中所有等于val值的节点：public void removeAllKey(int key)
四、自我实现一个双向不带头非循环结构的链表
4.1、实现代码
代码链接