【数据结构】链表详解（图文）

个人博客：www.hellocode.top
⭐所有文章均在上方博客首发，其他平台同步更新
本文专栏：《数据结构与算法》
⚡如有问题，欢迎指正，一起学习~~
文章参考整理自小码哥的《恋上数据结构和算法》课程，图片转载自课程PPT，如有侵权，请联系删除~~

文章目录

- 单链表
- - 接口设计
  - 代码实现
  - - 构造方法
    - 新增
    - 删除
    - 修改
    - 查找
  - 复杂度
  - 完整代码
- 双向链表
- - 接口设计
  - 代码实现
  - - 查找
    - 插入结点
    - 删除
    - 清空
  - 区别
- 循环链表
- - 单向循环链表
  - - 插入结点
    - 删除结点
  - 双向循环链表
  - - 插入结点
    - 删除结点

单链表

链表是一种链式存储的线性表, 所有元素的内存地址不一定是连续的
分类
- 单链表
- 双向链表（java.util.LinkedList）
- 循环链表
- 静态链表（了解）
- …

接口设计

创建LinkedList类，用来管理链表数据。其中的size属性记录存储数据的数量，first属性引用链表的第0个元素。
创建私有类Node，其中的element属性用于存储元素，next属性用于指向链表中的下一个节点。
其中的常用方法和动态数组基本一致

public class LinkedList {
    private int size;
    private Node 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 element;
        Node next;
        // 构造方法
        public Node(E element, Node 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 prev = node(index - 1);     // 找到指定位置的前一个结点
        prev.next = new Node<>(element,prev.next);
    }
    size++;
}

public void add(E element) {
    add(size,element);
}

private Node node(int index) {
    // 判断索引
    rangeCheck(index);
    // 遍历
    Node 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 old = first;       // 拿到被删除的结点
    if(index == 0){
        first = first.next;  // 对特殊情况单独处理
    } else{
        Node 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 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 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;


public interface List {
    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;


public abstract class AbstractList implements List{
    // 元素的数量
    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;


public class SingleLinkedList extends AbstractList{
    private Node first;

    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        Node 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 prev = node(index - 1);     // 找到指定位置的前一个结点
            prev.next = new Node<>(element,prev.next);
        }
        size++;
    }

    private Node node(int index) {
        // 判断索引
        rangeCheck(index);
        // 遍历
        Node node = first;
        for(int i = 0; i < index; i++){
            node = node.next;
        }
        return node;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);      // 索引检查
        Node old = first;       // 拿到被删除的结点
        if(index == 0){
            first = first.next;  // 对特殊情况单独处理
        } else{
            Node 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 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 element;
        Node next;
        // 构造方法
        public Node(E element, Node next) {
            this.element = element;
            this.next = next;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("SingleLinkedList{").append("size=").append(size).append(", [");
        Node 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;


public class LinkedList extends AbstractList{
    private Node first;
    private Node last;

    // 私有类, 链表中的节点
    private class Node {
        E element;
        Node prev;
        Node next;
        // 构造方法
        public Node(E element, Node next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
    }
}

代码实现查找

因为加入了last域，可以通过两个方向对链表进行遍历搜索，我们就需要利用好这个特点，来提高链表的效率
基本思路不变，只是加入一个判断
- 如果要查询的index大于size的一半（在后半部分），就从后往前遍历
- 如果要查询的index小于size的一半（在前半部分），就从前往后遍历

private Node node(int index) {
    // 判断索引
    rangeCheck(index);
    // 前半部分
    if(index <= (size >> 1)){
        Node node = first;
        for(int i = 0; i < index; i++){
            node = node.next;
        }
        return node;
    } else{     // 后半部分
        Node 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 oldLast = this.last;    // 取到原来的最后一个元素
        last = new Node<>(oldLast, element, null);  // 建立连接
        if(oldLast == null){    // 当前是链表添加的第一个元素
            first = last;
        }else{      // 当前为一般位置
            oldLast.next = last;
        }
    }else{
        Node next = node(index);
        Node prev = next.prev;
        Node 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 node = node(index);     // 被删除结点
    Node prev = node.prev;       // prev结点
    Node 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 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 newFirst = new Node<>(element,first);
        Node last = (size == 0) ? newFirst : node(size - 1);  // 获取到最后一个结点
        last.next = newFirst;      // 最后一个next指向新的首结点
        first = newFirst;
    }else{
        Node 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 old = first;       // 拿到被删除的结点
    if(index == 0){
        first = first.next;  // 对特殊情况单独处理
    } else{
        Node prev = node(index - 1);     // 找到index的前一个结点
        old = prev.next;
        prev.next = old.next;       // 断开连接
    }
    size--;
    return old.element;
}

单向循环链表

public E remove(int index) {
    rangeCheck(index);      // 索引检查
    Node old = first;       // 拿到被删除的结点
    if(index == 0){
        if(size == 1){      // 当前链表只有一个元素
            first = null;
        }else{
            Node last = node(size - 1);      // 拿到最后一个结点
            first = first.next;  // 对特殊情况单独处理
            last = first;
        }
    } else{
        Node 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 oldLast = last;    // 取到原来的最后一个元素
        last = new Node<>(oldLast, element, null);  // 建立连接
        if(oldLast == null){    // 当前是链表添加的第一个元素
            first = last;
        }else{      // 当前为一般位置
            oldLast.next = last;
        }
    }else{
        Node next = node(index);
        Node prev = next.prev;
        Node 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 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 next = node(index);
        Node prev = next.prev;
        Node 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 node = node(index);     // 被删除结点
    Node prev = node.prev;       // prev结点
    Node 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 node = node(index);     // 被删除结点
    if (size == 1){     // 只有一个元素
        first = null;
        last = null;
    }else{
        Node prev = node.prev;       // prev结点
        Node next = node.next;       // next结点

        prev.next = next;
        next.prev = prev;
        // 特殊情况判断
        if(node == first){      // 被删除的是第一个元素
            first = next;
        }
        if(node == last){      // 被删除的是最后一个元素
            last = prev;
        }
    }
    size--;
    return node.element;
}

【数据结构】链表详解（图文）

Java相关栏目本月热门文章