数据结构与算法学习笔记：单向链表

程序员文章站 2022-05-14 20:50:15

写在前面：记录学习《恋上数据结构与算法》的过程。课程链接地址：https://ke.qq.com/course/385223目录链表（Linked List）链表的设计接口设计清空（clear）添加元素 - add(int index , E element)删除元素 remove(int index)获取元素下标索引重写toString算法可视化网站案例练习：删除节点案例练习：反转一个链表递归非递归案例练习：判断一个链表是否有环虚拟头结点...

写在前面：记录学习《恋上数据结构与算法》的过程。
课程链接地址：https://ke.qq.com/course/385223

链表（Linked List）

链表的设计

接口设计

清空（clear）

添加元素 - add(int index , E element)

删除元素 remove(int index)

链表（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

遍历链表的另一种方法

算法可视化网站

https://visualgo.net/zh

案例练习：删除节点

案例练习：反转一个链表

递归

非递归

案例练习：判断一个链表是否有环

虚拟头结点

有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点（不存储数据）

node方法

增加元素：

删除元素：

复杂度分析

最好情况复杂度

最坏情况复杂度

平均情况复杂度

分析数组复杂度：

O(n) n是数据规模

分析链表复杂度：

动态数组、链表复杂度分析

均摊复杂度

什么情况下适合使用均摊复杂度

经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况

动态数组的缩容

如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作

比如剩余空间占总容量的一半时，就进行缩容

复杂度震荡