目录
添加元素 - add(int index , E element)
链表（Linked List）
- 动态数组有个明显的缺点
- 可能会造成内存空间的大量浪费能否用到多少就申请多少内存？
- 链表可以办到这一点
- 链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
链表的设计
接口设计
- List.java(接口)
package com.mj; public interface List<E> { static final int ELEMENT_NOT_FOUND = -1; /** * 清除所有元素 */ void clear(); /** * 元素的数量 * @return */ int size(); /** * 是否为空 * @return */ boolean isEmpty(); /** * 是否包含某个元素 * @param element * @return */ boolean contains(E element); /** * 添加元素到尾部 * @param element */ void add(E element); /** * 获取index位置的元素 * @param index * @return */ E get(int index); /** * 设置index位置的元素 * @param index * @param element * @return 原来的元素ֵ */ E set(int index, E element); /** * 在index位置插入一个元素 * @param index * @param element */ void add(int index, E element); /** * 删除index位置的元素 * @param index * @return */ E remove(int index); /** * 查看元素的索引 * @param element * @return */ int indexOf(E element); }
- LinkedList实现接口
- 和ArrayList公共代码
- 抽取公共的代码，创建父类
- AbstractList.java
package com.mj; public abstract class AbstractList<E> implements List<E> { /** * 元素的数量 */ protected int size; /** * 元素的数量 * @return */ public int size() { return size; } /** * 是否为空 * @return */ public boolean isEmpty() { return size == 0; } /** * 是否包含某个元素 * @param element * @return */ public boolean contains(E element) { return indexOf(element) != ELEMENT_NOT_FOUND; } /** * 添加元素到尾部 * @param element */ public void add(E element) { add(size, element); } protected void outOfBounds(int index) { throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); } protected void rangeCheck(int index) { if (index < 0 || index >= size) { outOfBounds(index); } } protected void rangeCheckForAdd(int index) { if (index < 0 || index > size) { outOfBounds(index); } } }清空（clear）
添加元素 - add(int index , E element)
- 获取index位置节点对象
- 获取节点元素
- 设置指定位置值
- 添加元素，注意0的位置
- 在编写链表过程中，要注意边界测试，比如index为0、size-1、size时
删除元素 remove(int index)
获取元素下标索引
重写toString
- 遍历链表的另一种方法
算法可视化网站
案例练习：删除节点
案例练习：反转一个链表
递归
非递归
案例练习：判断一个链表是否有环
虚拟头结点
- 有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点（不存储数据）
- node方法
- 增加元素：
- 删除元素：
复杂度分析
- 最好情况复杂度
- 最坏情况复杂度
- 平均情况复杂度
分析数组复杂度：
- O(n) n是数据规模
分析链表复杂度：
动态数组、链表复杂度分析
均摊复杂度
- 什么情况下适合使用均摊复杂度
- 经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况
动态数组的缩容
- 如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作
- 比如剩余空间占总容量的一半时，就进行缩容
复杂度震荡
本文地址：https://blog.csdn.net/baidu_41388533/article/details/107374230
如对本文有疑问， 点击进行留言回复！！
关于在IDEA中SpringBoot项目中activiti工作流的使用详解
视频编辑工具ACDSee Luxea Video Editor安装及激活图文教程
java spring整合junit操作(有详细的分析过程)
我要评论
网友评论