同系列文章导读:【数据结构与算法】导读

所有文章均在本博客首发,其他平台同步更新

如有问题,欢迎指正(评论区留言即可)

发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】

本文参考整理自小码哥的《恋上数据结构和算法》课程,图片转自课程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;
}

复杂度

完整代码

通过上面的分析,我们可以看出:链表和动态数组中的方法大体上一致,并且有很多方法的方法体同样一样

对于这种情况,我们对他们进行抽取,让代码更加简洁

  1. 定义List接口,对所有方法进行抽取(因为链表和动态数组要实现的方法都一样,只是有的方法实现思路不同)
  2. 定义AbstractList抽象类,实现List接口,对二者相同代码进行抽取
  3. 定义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)
  • 可分为单向循环链表和双向循环链表
  • 相比于之前的单向链表和双向链表,主要需要对addremove方法进行重写
这里会比较绕,建议大家自己上手进行代码编写来体会指针指向的变化

单向循环链表

  • 如图,单向循环链表就是在原有的单向链表基础上,对尾结点的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指向首结点
  • 同样的,相比于双向链表,我们需要对addremove方法进行重写

插入结点

  • 需特殊处理添加第一个元素和添加到尾节点两种特殊情况

双向链表

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++;
}

删除结点

  • 删除节点,需要根据删除的节点是首节点或者尾节点来处理firstlast
  • 需要特殊处理只有一个节点的删除操作

双向链表

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;
}

END

本文作者: 文章标题:【数据结构】链表详解(图文)
本文地址:https://www.hellocode.top/archives/101/
版权说明:若无注明,本文皆HelloCode原创,转载请保留文章出处。
最后修改:2022 年 05 月 14 日
如果觉得我的文章对你有用,请随意赞赏