本篇是恋上数据结构与算法(第一季)的学习笔记, 使用JAVA语言
动态数组有个明显的缺点, 可能会造成内存空间的大量浪费
链表可以做到用多少就申请多少内存
一、链表
- 链表是一种
链式存储
的线性表, 所有元素的内存地址不一定是连续的
二、链表的设计
- 创建类
LinkedList
, 用来管理链表数据, 其中的size
属性记录存储数据的数量,first
属性引用链表的第0
个元素 - 创建私有类
Node
, 其中的element
属性用于存储元素,next
属性用于指向链表中的下一个节点
public class LinkedList<E> {
private int size;
private Node<E> first;
// 私有类, 链表中的节点
private class Node<E> {
E element;
Node<E> next;
// 构造方法
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
}
三、链表接口设计
- 与动态数组一样, 链表也需要提供增删改查
// 元素的数量
int size();
// 是否为空
boolean isEmpty();
// 是否包含某个元素
boolean contains(E element);
// 添加元素到最后面
void add(E element);
// 返回index位置对应的元素
E get(int index);
// 设置index位置的元素
E set(int index, E element);
// 往index位置添加元素
void add(int index, E element);
// 删除index位置对应的元素
E remove(int index);
// 查看元素的位置
int indexOf(E element);
// 清除所有元素
void clear();
四、链表接口实现
1、索引越界的判断
- 在操作链表数据时,需要防止索引越界,到时程序异常的问题
- 当查找和删除数据时, 需要检查索引的范围是
0到size-1
之间,所以方法如下
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
}
- 当插入数据时,因为可以将数据加到所有数据的最后,所以需要检查索引的范围是
0到size
之间
private void rangeCheckForSize(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
}
2、根据索引查找指定节点
- 因为链表中的数据都是存在节点中, 所以操作数据时需要找到对应的节点
- 我们可以实现一个根据索引, 来查找指定节点的方法
private Node<E> node(int index) {
rangeCheck(index);
// 头结点,就是first指向的那个节点
Node<E> node = first;
// 根据索引遍历,查找对应的节点
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
3、添加数据
- 添加数据时, 需要创建一个节点存储数据, 并将该节点拼接到最后节点的后面, 然后
size
加1
- 两种情况
- 第一种: 当前链表没有数据, 新节点拼接到first
- 第二种: 当前链表有数据, 新节点拼接到最后的节点
public void add(E element) {
// 当first等于null时, 说明此事没有节点, 所以first引用新节点
if (first == null) {
first = new Node<E>(element, null);
}else {
// 当fitst不等于null时, 说明链表中有节点, 此时获取最后一个节点, 并将该节点的next指向新节点
Node<E> node = node(size - 1);
node.next = new Node<E>(element, null);
}
size++;
}
4、插入元素
- 插入链表时, 只需要创建新节点保存元素, 然后插入指定位置即可
- 两种情况
- 第一种: 插入到0的位置, 需要使用first指向新节点
- 第二种: 插入到非0位置,直接找到前一个节点进行处理
public void add(int index, E element) {
// 检查索引是否越界
rangeCheckForSize(index);
// 当插入到0的位置时
if (index == 0) {
// 将first指向新节点, 新节点的next指向first之前指向的节点
first = new Node<E>(element, first.next);
}else {
// 找到指定位置前面的节点
Node<E> prev = node(index - 1);
// 将前面节点的next指向新节点, 新节点的next指向prev之前指向的节点
prev.next = new Node<>(element, prev.next);
}
size++;
}
- 添加元素的方法可以简写
public void add(E element) {
// 元素添加到size位置, 即添加到最后面
add(size, element);
}
5、删除元素
- 删除元素, 找到指定节点前面的节点, 然后直接指向需要删除节点的下一个节点即可, 然后
size
减1
- 两种情况
- 第一种: 删除第0个元素, 需要使用first指向第1个节点
- 第二种: 删除非0索引的元素, 找到前一个节点, 然后直接指向下一个节点即可
public E remove(int index) {
// 检查索引是否越界
rangeCheck(index);
// 记录需要删除的节点
Node<E> old = first;
// 当删除第0个元素时, 将first的next指向索引为`1`的节点即可
if (index == 0) {
first = first.next;
}else {
// 找到前一个元素
Node<E> prev = node(index - 1);
// 记录需要删除的节点
old = prev.next;
// 将prev的next指向需要删除节点的后一个节点
prev.next = old.next;
}
// size-1
size--;
// 返回删除的元素
return old.element;
}
6、清空元素
- 清空元素, 直接将
first
指向null
即可, 同时size
置为0
public void clear() {
first = null;
size = 0;
}
7、修改元素
- 修改元素, 找到对应节点, 直接修改元素即可
public E set(int index, E element) {
// 找到对应节点, node方法中已经判断了索引是否越界
Node<E> node = node(index);
// 记录旧元素
E old = node.element;
// 覆盖元素
node.element = element;
// 返回旧元素
return old;
}
8、查找元素
- 查找元素, 直接找到对应的节点, 取出元素即可
public E get(int index) {
// node方法中已经判断了索引是否越界
return node(index).element;
}
9、查找元素索引
- 查找指定元素的索引, 需要遍历所有节点, 找到节点对应的元素与执行元素相等即可
- 因为元素可以是
null
, 所以需要分两种情况处理
private static final int ELEMENT_ON_FOUND = -1;
public int indexOf(E element) {
// 取出头结点
Node<E> node = first;
// 当element为null时的处理
if (element == null) {
// 遍历节点, 找到存储为null的节点, 返回索引
for (int i = 0; i < size; i++) {
if (node.element == null) return i;
node = node.next;
}
}else {
for (int i = 0; i < size; i++) {
// 遍历节点, 找到存储的元素与指定元素相等的节点, 返回索引
if (element.equals(node.element)) return i;
node = node.next;
}
}
// 没有找到元素对应的节点, 返回ELEMENT_ON_FOUND
return ELEMENT_ON_FOUND;
}
10、获取链表存储元素的个数
- 获取链表存储元素的个数, 就是
size
的值
public int size() {
return size;
}
11、链表是否为空
- 链表是否为空, 只需要判断
size
是否等于0
即可
public boolean isEmpty() {
return size == 0;
}
12、判断元素是否存在
- 判断元素是否存在, 只需要判断元素的索引是否为
ELEMENT_ON_FOUND
即可
public boolean contains(E element) {
return indexOf(element) != ELEMENT_ON_FOUND;
}
13、打印链表中存储的数据
- 只需要重写
toString
方法即可
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("size = ").append(size).append(", [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
string.append(",");
}
string.append(node.element);
node = node.next;
}
string.append("]");
return string.toString();
}