本文参考整理自小码哥的《恋上数据结构和算法》课程，图片转自课程ppt，如有侵权，请联系删除~
单链表
- 链表是一种链式存储的线性表, 所有元素的内存地址不一定是连续的
分类
- 单链表
- 双向链表（java.util.LinkedList）
- 循环链表
- 静态链表（了解）
- .....
接口设计
- 创建
LinkedList类，用来管理链表数据。其中的size属性记录存储数据的数量，first属性引用链表的第0个元素。 - 创建私有类
Node，其中的element属性用于存储元素，next属性用于指向链表中的下一个节点。 - 其中的常用方法和动态数组基本一致
public class LinkedList<E> {
private int size;
private Node<E> first;
// 元素的数量
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();
// 私有类, 链表中的节点
private class Node<E> {
E element;
Node<E> next;
// 构造方法
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
}代码实现
构造方法
在动态数组中，构造方法需要指定初始容量。而链表不需要提前分配内存空间，因此不需要指定构造方法
在Java中，如果没有指定构造方法，虚拟机会自动提供一个无参构造方法
如果提供了有参构造，虚拟机将不再提供无参构造，如果有要用到无参构造的地方，需要手动提供无参构造方法
新增
新增可分为尾插和指定位置两种插入方式
- 其中尾插法可以看作是指定位置插入的一种情况（
inde = size） - 链表中新增元素，需要找到index位置的上一个结点prev，然后让prev.next指向新结点，让新结点的next指向原index处的结点
- 需要注意的是，涉及到索引的代码，需要首先对传入的索引进行合法性判断(和动态数组中一样)
指定位置添加，可以先不考虑特殊位置，先完成一般位置代码实现，然后再考虑一般情况能否处理特殊位置的问题
- 在单链表中，对应的特殊位置就是首和尾
- 因为新增是需要先找到index位置的前一个结点，如果需要添加的位置是0，那么找前一个结点就是null，此时不进行单独处理的话，就会报错
- 如果需要添加的位置是size的话，还是可以找到前一个结点的，也就是说一般情况能处理尾插情况，不用单独处理
public void add(int index, E element) {
rangeCheckForAdd(index); // 索引合法检查
if(index == 0){
first = new Node<>(element,first);
}else{
Node<E> prev = node(index - 1); // 找到指定位置的前一个结点
prev.next = new Node<>(element,prev.next);
}
size++;
}public void add(E element) {
add(size,element);
}private Node<E> node(int index) {
// 判断索引
rangeCheck(index);
// 遍历
Node<E> node = first;
for(int i = 0; i < index; i++){
node = node.next;
}
return node;
}因为在增、删、改、查等操作中都需要查找对应位置的结点，所以我们把它抽成一个方法，设置为private权限，不对外界开放
删除
remove
删除可以分为指定索引删除和指定元素删除
- 删除指定位置元素同样需要找到index的前一个结点prev
- 让prev指向index.next（断开prev与index的连接），Java外语言需要考虑是否需要手动释放内存（动态数组中提到过这个问题）
- 如果是删除指定元素，可以先通过indexOf方法查到该元素的索引，再调用指定位置删除的方法进行删除
- 同样的，先考虑一般位置，再对特殊位置进行分析，判断是否需要对特殊位置单独处理
- 和增加一样，删除只需要对
index==0时进行处理
public E remove(int index) {
rangeCheck(index); // 索引检查
Node<E> old = first; // 拿到被删除的结点
if(index == 0){
first = first.next; // 对特殊情况单独处理
} else{
Node<E> prev = node(index - 1); // 找到index的前一个结点
old = prev.next;
prev.next = old.next; // 断开连接
}
size--;
return old.element;
}public void remove(E element) {
remove(indexOf(element));
}clear
- 在动态数组中，清空元素直接将size置为0即可
- 但是在链表中，除了size置0，还需要将堆空间中为每个结点开辟的空间释放
- Java中直接断开first与这些结点的连接即可（垃圾回收机制），但是其他语言，还需要根据情况手动释放内存
public void clear() {
size = 0;
first = null;
}修改
- 除了增加和删除情况稍微复杂点，链表的其他操作都比较易理解
- 修改元素就是获取到要修改的位置的结点，重新给element赋值即可
public E set(int index, E element) {
Node<E> node = node(index); // 拿到要修改的结点
E old = node.element; // 拿到被修改的值
node.element = element; // 重新赋值
return old;
}这里也涉及到了index，但是并没有对index的合法性进行检查，是因为在node方法中，已经对index做了合法性检查
查找
查找指定元素索引
- 在该方法中，分为两种情况，如果查询null的索引和非null元素的索引
- 当查找不到时返回
ELEMENT_NOT_FOUND（-1）
当然，也可以直接设置不能存储null值，这个具体情况由自己决定
public int indexOf(E element) {
Node<E> node = first;
// 当element==null时
if(element == 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;
}
}
return ELEMENT_NOT_FOUND;
}get方法
比较简单，就不做过多说明了
public E get(int index) {
return node(index).element;
}复杂度
完整代码
通过上面的分析，我们可以看出：链表和动态数组中的方法大体上一致，并且有很多方法的方法体同样一样
对于这种情况，我们对他们进行抽取，让代码更加简洁
- 定义List接口，对所有方法进行抽取（因为链表和动态数组要实现的方法都一样，只是有的方法实现思路不同）
- 定义AbstractList抽象类，实现List接口，对二者相同代码进行抽取
- 定义SingleLinkedList和ArrayList类，分别继承AbstractList抽象类
List接口
package top.hellocode.List;
/**
* @author HelloCode
* @site https://www.hellocode.top
* @date 2022年05月14日 13:09
*/
public interface List<E> {
static final int ELEMENT_NOT_FOUND = -1;
// 元素的数量
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);
// 删除对应的元素
void remove(E element);
// 查看元素的位置
int indexOf(E element);
// 清除所有元素
void clear();
}Abstract抽象类
package top.hellocode.List;
/**
* @author HelloCode
* @site https://www.hellocode.top
* @date 2022年05月14日 13:10
*/
public abstract class AbstractList<E> implements List<E>{
// 元素的数量
protected int size;
// 元素的数量
public int size(){
return size;
}
// 是否为空
public boolean isEmpty() {
return size == 0;
}
// 是否包含某个元素
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
// 添加元素到最后面
public void add(E element) {
add(size,element);
}
protected void rangeCheck(int index) {
if(index >= size || index < 0){
outOfBounds(index);
}
}
protected void rangeCheckForAdd(int index) {
if(index > size || index < 0){
outOfBounds(index);
}
}
protected void outOfBounds(int index){
throw new IndexOutOfBoundsException("size:" + size + ", index:" + index);
}
}SingleLinkedList单链表
package top.hellocode.List;
/**
* @author HelloCode
* @site https://www.hellocode.top
* @date 2022年05月14日 13:08
*/
public class SingleLinkedList<E> extends AbstractList<E>{
private Node<E> first;
@Override
public E get(int index) {
return node(index).element;
}
@Override
public E set(int index, E element) {
Node<E> node = node(index); // 拿到要修改的结点
E old = node.element; // 拿到被修改的值
node.element = element; // 重新赋值
return old;
}
@Override
public void add(int index, E element) {
rangeCheckForAdd(index); // 索引合法检查
if(index == 0){
first = new Node<>(element,first);
}else{
Node<E> prev = node(index - 1); // 找到指定位置的前一个结点
prev.next = new Node<>(element,prev.next);
}
size++;
}
private Node<E> node(int index) {
// 判断索引
rangeCheck(index);
// 遍历
Node<E> node = first;
for(int i = 0; i < index; i++){
node = node.next;
}
return node;
}
@Override
public E remove(int index) {
rangeCheck(index); // 索引检查
Node<E> old = first; // 拿到被删除的结点
if(index == 0){
first = first.next; // 对特殊情况单独处理
} else{
Node<E> prev = node(index - 1); // 找到index的前一个结点
old = prev.next;
prev.next = old.next; // 断开连接
}
size--;
return old.element;
}
@Override
public void remove(E element) {
remove(indexOf(element));
}
@Override
public int indexOf(E element) {
Node<E> node = first;
// 当element==null时
if(element == 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;
}
}
return ELEMENT_NOT_FOUND;
}
@Override
public void clear() {
size = 0;
first = null;
}
// 私有类, 链表中的节点
private class Node<E> {
E element;
Node<E> next;
// 构造方法
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("SingleLinkedList{").append("size=").append(size).append(", [");
Node<E> node = first;
while(node != null){
sb.append(node.element);
if(node.next != null){
sb.append(",");
}
node = node.next;
}
sb.append("]}");
return sb.toString();
}
}动态数组的抽取大家自己可以试试，思路都一样
拓展： 在新增、删除等操作中，我们对不同情况进行了判断并单独处理。那有没有什么方法，能够统一这些不同的情况，让他们的实现代码都一致呢？
答案是有的，可以通过增加虚拟头结点（element为null，next指向头结点），这样的话可以将实现逻辑统一化，但是因为新增加了一个结点，又会浪费一些存储空间。具体实现思路大家可以自行查询了解
双向链表
- 单链表只能通过next单向遍历链表，完成搜索
- 为了提高效率，可以在原有基础上，再为每个结点增加一个prev域，指向当前结点的上一个结点
- 在双向链表中，就可以从first或last两个方向对链表进行遍历搜索
接口设计
- 相较于单链表，双向链表只需要对增加、删除、查找、清空四个方法进行重写
package top.hellocode.List;
/**
* @author HelloCode
* @site https://www.hellocode.top
* @date 2022年05月14日 13:08
*/
public class LinkedList<E> extends AbstractList<E>{
private Node<E> first;
private Node<E> last;
// 私有类, 链表中的节点
private class Node<E> {
E element;
Node<E> prev;
Node<E> next;
// 构造方法
public Node(E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}
}代码实现
查找
- 因为加入了last域，可以通过两个方向对链表进行遍历搜索，我们就需要利用好这个特点，来提高链表的效率
基本思路不变，只是加入一个判断
- 如果要查询的index大于size的一半（在后半部分），就从后往前遍历
- 如果要查询的index小于size的一半（在前半部分），就从前往后遍历
private Node<E> node(int index) {
// 判断索引
rangeCheck(index);
// 前半部分
if(index <= (size >> 1)){
Node<E> node = first;
for(int i = 0; i < index; i++){
node = node.next;
}
return node;
} else{ // 后半部分
Node<E> node = last;
for(int i = size - 1; i > index; i--){
node = node.prev;
}
return node;
}
}插入结点
- 和之前的思想基本一致
不同点
- 找到指定index位置
- 将index处结点的prev.next指向新结点
- 将新结点的prev指向index.prev
- 将新结点的next指向index结点
- 将index结点的prev指向新结点
- size++
public void add(int index, E element) {
rangeCheckForAdd(index); // 索引合法检查
// 往最后添加元素
if(index == size){
Node<E> oldLast = this.last; // 取到原来的最后一个元素
last = new Node<>(oldLast, element, null); // 建立连接
if(oldLast == null){ // 当前是链表添加的第一个元素
first = last;
}else{ // 当前为一般位置
oldLast.next = last;
}
}else{
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node(prev, element, next);
next.prev = node;
if(prev == null){ // 当前位置为0
first = node;
}else{ // 当前为一般位置
prev.next = node;
}
}
size++;
}注意对特殊位置进行特殊处理！！！
删除
和单链表不同点：需要同时断开被删除结点的前后结点引用
- 找到需要删除的结点
- 拿到prev结点和next结点
- 让prev.next指向next
- 让next.prev指向prev
- 注意对特殊位置特殊处理
- size--
public E remove(int index) {
rangeCheck(index); // 索引检查
Node<E> node = node(index); // 被删除结点
Node<E> prev = node.prev; // prev结点
Node<E> next = node.next; // next结点
// 特殊情况判断
if(prev == null){ // 被删除的是第一个元素
first = next;
}else{
prev.next = next;
}
if(next == null){ // 被删除的是最后一个元素
last = prev;
}else{
next.prev = prev;
}
size--;
return node.element;
}清空
- 在清空中，因为引入了last，所以还需要对last进行处理
public void clear() {
size = 0;
first = null;
last = null;
}这部分可能大家有些困惑，双向链表的话，即使切断了first和last对结点的引用，每两个结点之间依然有连接，虚拟机是否能够自动释放内存？
答案是可以的。在虚拟机中，如果一个对象到GC roots对象没有任何引用，没有形成引用链，那么该对象等待GC回收。详细可以自行查询一下相关资料
区别
循环链表
- 循环链表就是通过对next或者prev域的指向进行调整，将链表形成一个环（无指针指向null）
- 可分为单向循环链表和双向循环链表
- 相比于之前的单向链表和双向链表，主要需要对
add和remove方法进行重写
这里会比较绕，建议大家自己上手进行代码编写来体会指针指向的变化
单向循环链表
- 如图，单向循环链表就是在原有的单向链表基础上，对尾结点的next做调整，使其指向首结点，形成环
插入结点
- 插入结点时，单向链表和循环单向链表主要是对0索引处插入时有所区别
- 需要注意的是，当链表中无结点时（当前插入的是第一个结点），需要将first、新结点的next都指向新结点
单向链表
public void add(int index, E element) {
rangeCheckForAdd(index); // 索引合法检查
if(index == 0){ // 插入位置为first时
first = new Node<>(element,first);
}else{
Node<E> prev = node(index - 1); // 找到指定位置的前一个结点
prev.next = new Node<>(element,prev.next);
}
size++;
}单向循环链表
public void add(int index, E element) {
rangeCheckForAdd(index); // 索引合法检查
if(index == 0){
Node<E> newFirst = new Node<>(element,first);
Node<E> last = (size == 0) ? newFirst : node(size - 1); // 获取到最后一个结点
last.next = newFirst; // 最后一个next指向新的首结点
first = newFirst;
}else{
Node<E> prev = node(index - 1); // 找到指定位置的前一个结点
prev.next = new Node<>(element,prev.next);
}
size++;
}注意：在单向循环链表中，加入了newFirst，如果不使用newFirst，直接让first等于新结点，就等于已经将新节点加到了链表中
这时使用node方法获取指定索引的结点就会出现问题（实际链表中元素个数已经加1，但是size还没有进行自增），就会拿到指定索引的前一个结点
删除结点
- 删除结点时，单向和循环的区别主要也是0索引处的处理
- 在循环链表中，删除0索引处结点除了让first指向被删除.next，还需要将最后一个元素的next指向被删除.next
- 除了对特殊位置的处理，还需要对链表中元素个数进行判断：当链表只有一个元素时也需要特殊处理
单向链表
public E remove(int index) {
rangeCheck(index); // 索引检查
Node<E> old = first; // 拿到被删除的结点
if(index == 0){
first = first.next; // 对特殊情况单独处理
} else{
Node<E> prev = node(index - 1); // 找到index的前一个结点
old = prev.next;
prev.next = old.next; // 断开连接
}
size--;
return old.element;
}单向循环链表
public E remove(int index) {
rangeCheck(index); // 索引检查
Node<E> old = first; // 拿到被删除的结点
if(index == 0){
if(size == 1){ // 当前链表只有一个元素
first = null;
}else{
Node<E> last = node(size - 1); // 拿到最后一个结点
first = first.next; // 对特殊情况单独处理
last = first;
}
} else{
Node<E> prev = node(index - 1); // 找到index的前一个结点
old = prev.next;
prev.next = old.next; // 断开连接
}
size--;
return old.element;
}双向循环链表
- 在双向链表中，首结点的prev和尾结点的next都为null
- 而双向循环链表中，首结点的prev指向尾结点，尾结点的next指向首结点
- 同样的，相比于双向链表，我们需要对
add和remove方法进行重写
插入结点
- 需特殊处理添加第一个元素和添加到尾节点两种特殊情况
双向链表
public void add(int index, E element) {
rangeCheckForAdd(index); // 索引合法检查
// 往最后添加元素
if(index == size){
Node<E> oldLast = last; // 取到原来的最后一个元素
last = new Node<>(oldLast, element, null); // 建立连接
if(oldLast == null){ // 当前是链表添加的第一个元素
first = last;
}else{ // 当前为一般位置
oldLast.next = last;
}
}else{
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node(prev, element, next);
next.prev = node;
if(prev == null){ // 当前位置为0
first = node;
}else{ // 当前为一般位置
prev.next = node;
}
}
size++;
}双向循环链表
public void add(int index, E element) {
rangeCheckForAdd(index); // 索引合法检查
// 往最后添加元素
if(index == size){
Node<E> node = new Node<>(last, element, first);
if(size == 0){ // 当前是链表添加的第一个元素
first = node;
last = node;
node.next = node;
node.prev = node;
}else{ // 当前为一般位置
last.next = node;
first.prev = node;
last = node;
}
}else{
Node<E> next = node(index);
Node<E> prev = next.prev;
Node<E> node = new Node(prev, element, next);
next.prev = node;
prev.next = node;
if(next == first){ // 当前位置为0
first = node;
}
}
size++;
}删除结点
- 删除节点，需要根据删除的节点是首节点或者尾节点来处理
first和last。 - 需要特殊处理只有一个节点的删除操作
双向链表
public E remove(int index) {
rangeCheck(index); // 索引检查
Node<E> node = node(index); // 被删除结点
Node<E> prev = node.prev; // prev结点
Node<E> next = node.next; // next结点
// 特殊情况判断
if(prev == null){ // 被删除的是第一个元素
first = next;
}else{
prev.next = next;
}
if(next == null){ // 被删除的是最后一个元素
last = prev;
}else{
next.prev = prev;
}
size--;
return node.element;
}双向循环链表
public E remove(int index) {
rangeCheck(index); // 索引检查
Node<E> node = node(index); // 被删除结点
if (size == 1){ // 只有一个元素
first = null;
last = null;
}else{
Node<E> prev = node.prev; // prev结点
Node<E> next = node.next; // next结点
prev.next = next;
next.prev = prev;
// 特殊情况判断
if(node == first){ // 被删除的是第一个元素
first = next;
}
if(node == last){ // 被删除的是最后一个元素
last = prev;
}
}
size--;
return node.element;
}