由于动态数组有个明显得缺点：可能会造成内存空间的大量浪费（动态数据实现动态扩容）。
能否做到用多少内存就申请多少内存呢？链表就可以做到这一点，链表是一种链式存储的线性表，所有元素的内存地址都不一定是连续的。
1. 接口设计
链表的大部分接口和动态数组是一致的，可以在接口中定义统一需要实现的方法。将链表和动态数组需要公共实现的部分放在抽象类中进行实现。有差异的方法再通过抽象类的子类进行实现;
1.1 设计一个公共的接口 List
List:
/**
* Description: dsai
* Created by itLu on 2021/6/19 15:17
* 定义动态数组 + 链表 + 双向链表 需要 实现的方法
* @author yanpeng.lu
*/
public interface List<T> {
final static int ELEMENT_NOT_FOUND = -1;
int size();
boolean isEmpty();
boolean contains(T element);
void add(T element);
void add(int index, T element);
T get(int index);
T set(int index, T element);
T remove(int index);
int indexOf(T element);
void clear();
}
1.2 AbstractLinkedList 抽象类中实现一些公共的方法
AbstractLinkedList:
/**
* Description: dsai
* Created by itLu on 2021/6/26 10:45
*
* @author yanpeng.lu
*/
public abstract class AbstractLinkedList<T> implements List<T> {
/**
* 链表中元素的个数
*/
protected int size;
/**
* 获取当前链表中元素的个数
*
* @return
*/
@Override
public int size() {
return size;
}
/**
* 判断当前链表是否为空
*
* @return
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* 判断链表中是否存在某个元素
*
* @param element
* @return
*/
@Override
public boolean contains(T element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 向链表的末尾添加一个节点
*
* @param element
*/
@Override
public void add(T element) {
add(size, element);
}
/**
* 校验 index 是否合法
*
* @param index
*/
protected void rangeCheckIndex(int index) {
if (index < 0 || index >= size) {
outOfBound(index);
}
}
/**
* 统一处理 index 越界
*
* @param index
*/
private void outOfBound(int index) {
throw new IndexOutOfBoundsException("index : " + index + " size : " + size);
}
/**
* @param index
* 针对添加节点的index校验
*/
protected void rangeCheckIndexForAdd(int index) {
if (index < 0 || index > size) {
outOfBound(index);
}
}
}
1.3 在抽象类子类中实现自己独有的方法
SingleCircleLinkedList
/**
* Description: dsai
* Created by itLu on 2021/6/26 13:26
* 单向循环链表
*
* @author yanpeng.lu
*/
public class SingleCircleLinkedList<E> extends AbstractLinkedList<E> {
private Node<E> first;
/**
* 创建一个节点实体
*
* @param <E>
*/
static class Node<E> {
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
/**
* 重写节点的 toString 方法
*
* @return
*/
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append(element).append("_");
if (next != null) {
str.append(next.element);
} else {
str.append("null");
}
return str.toString();
}
}
/**
* 在链表中指定 index 位置添加一个节点
* @param index
* @param element
*/
@Override
public void add(int index, E element) {
// 校验当前的index是否合法
rangeCheckIndexForAdd(index);
// 在插入第一个元素 或 在 第一个位置插入元素的时候需要改变 最后一个元素的 next 的指向
if (index == 0) {
// 新的节点
Node<E> newFirst = new Node<>(element, first);
// 需要获取到最后一个节点 这里需要注意的是 在node中需要使用到first的指向
// 还有 当链表中一个元素都没有的时候 需要进行处理
Node<E> oldLast = size == 0 ? newFirst : node(size - 1);
// 实现循环
oldLast.next = newFirst;
// 这里需要在以上三步进行完成之后再改变first的指向
first = newFirst;
} else {
// 找到需要插入节点的前一个节点
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
/**
* 获取指定 index 处节点的元素值
*
* @param index
* @return
*/
@Override
public E get(int index) {
return node(index).element;
}
/**
* 覆盖指定 index 位置处节点的元素值
*
* @param index
* @param element
* @return
*/
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E oldElement = node.element;
node.element = element;
return oldElement;
}
/**
* 删除链表中指定 index 位置处的节点
* @param index
* @return
*/
@Override
public E remove(int index) {
rangeCheckIndex(index);
// 默认是删除第一个节点
Node<E> node = first;
if (index == 0) {
if (size == 0) {
first = null;
}else {
Node<E> last = node(size - 1);
first = node.next;
last.next = first;
}
} else {
// 删除中间节点都不会影响到最后一个节点的指向
// 需要获取需要删除节点的前一个节点
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
size--;
return node.element;
}
/**
* 获取指定元素在链表中的位置
*
* @param element
* @return
*/
@Override
public int indexOf(E element) {
if (element == null) {
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (node.element == null) {
return i;
}
node = node.next;
}
} else {
Node<E> node = first;
for (int i = 0; i < size; i++) {
// 需要注意的 是 这里element需要写在前面 因为 node.element 可能出现 null 的情况 会造成空指针异常
if (element.equals(node.element)) {
return i;
}
node = node.next;
}
}
// 上面都不满足则表示没有找到 返回 -1
return ELEMENT_NOT_FOUND;
}
/**
* 清空链表
*/
@Override
public void clear() {
first = null;
size = 0;
}
/**
* 获取指定位置的节点
*
* @param index
* @return
*/
public Node<E> node(int index) {
rangeCheckIndex(index);
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
/**
* 重写 toString 方法
*
* @return
*/
@Override
public String toString() {
StringBuilder str = new StringBuilder();
str.append(" size : ").append(size).append(" [ ");
Node<E> node = first;
for (int i = 0; i < size; i++) {
if (i != 0) {
str.append(" , ");
}
str.append(node);
node = node.next;
}
str.append(" ] ");
return str.toString();
}
}
2. add 方法实现思路
在实现循环链表的过程中，添加方法是核心，需要进行与单链表区别的处理。处理需要在 index == 0 位置，也就是链表的头节点位置，因为这里会改变到 index == size -1位置下一个节点的指向。如果是在中间插入，不会影响到链表循环，所以处理方式和单链表一致。
/**
* 在链表中指定 index 位置添加一个节点
* @param index
* @param element
*/
@Override
public void add(int index, E element) {
// 校验当前的index是否合法
rangeCheckIndexForAdd(index);
// 在插入第一个元素 或 在 第一个位置插入元素的时候需要改变 最后一个元素的 next 的指向
if (index == 0) {
// 新的节点
Node<E> newFirst = new Node<>(element, first);
// 需要获取到最后一个节点 这里需要注意的是 在node中需要使用到first的指向
// 还有 当链表中一个元素都没有的时候 需要进行处理
Node<E> oldLast = size == 0 ? newFirst : node(size - 1);
// 实现循环
oldLast.next = newFirst;
// 这里需要在以上三步进行完成之后再改变first的指向
first = newFirst;
} else {
// 找到需要插入节点的前一个节点
Node<E> prev = node(index - 1);
prev.next = new Node<>(element, prev.next);
}
size++;
}
3. remove方法实现思路
在实现循环链表的删除节点操作时，在删除头节点时也会影响到循环链表。所以在 index == 0时需要对删除节点进行特殊处理。还有就是当链表中size == 0的时候需要进行特殊处理:
/**
* 移除指定位置处的元素
*
* @param index
* @return
*/
@Override
public E remove(int index) {
// 需要对 index 进行合法性校验
rangeCheckIndex(index);
Node<E> node = first;
if (index == 0) {
if (size == 0) {
first = null;
} else {
Node<E> last = node(size - 1);
// 需要处理 index == 0 的情况 当 index = 0 时 可能出现 index - 1 = -1 的情况
first = first.next;
last.next = first;
}
} else {
// 首先需要获取到需要删除节点的前一个节点
Node<E> prev = node(index - 1);
node = prev.next;
prev.next = node.next;
}
// 对链表中的元素个数减 1 操作
size--;
return node.element;
}
