AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

《恋上数据结构第1季》单向链表、双向链表

2022-05-25 76
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 《恋上数据结构第1季》单向链表、双向链表

我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

动态数组有个明显的缺点：

  • 可能会造成内存空间的大量浪费。

能否用到多少就申请多少内存？

  • 链表可以办到这一点

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的;

在这里插入图片描述

链表的接口设计

在这里插入图片描述
由于链表的大部分接口和动态数组一致，我们抽取出一个共同的 List 接口；

package com.mj;

public interface List<E> {
    static final int ELEMENT_NOT_FOUND = -1;
    /**
     * 清除所有元素
     */
    void clear();

    /**
     * 元素的数量
     * @return
     */
    int size();

    /**
     * 是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    boolean contains(E element);

    /**
     * 添加元素到尾部
     * @param element
     */
    void add(E element);

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    E get(int index);

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     * @return 原来的元素ֵ
     */
    E set(int index, E element);

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    void add(int index, E element);

    /**
     * 删除index位置的元素
     * @param index
     * @return
     */
    E remove(int index);

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    int indexOf(E element);
}

再将一些通用的字段与方法放到一个抽象类中，无论是动态数组还是链表都只需要继承这个抽象类即可。

package com.mj;

public abstract class AbstractList<E> implements List<E>{
    
    protected int size;
    
    // 下标越界抛出的异常
    protected void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }
    // 检查下标越界(不可访问或删除size位置)
    protected void rangeCheck(int index){
        if(index < 0 || index >= size){
            outOfBounds(index);
        }
    }
    // 检查add()的下标越界(可以在size位置添加元素)
    protected void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }
    
    @Override
    public boolean contains(E element) {
        return indexOf(element)!=ELEMENT_NOT_FOUND;
    }
    
    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
    
    @Override
    public void add(E element) {
        add(size, element);
    }

}

单向链表（SingleLinkedList）

单向链表的结构如下图所示：
在这里插入图片描述

public class SingleLinkedList<E> extends AbstractList<E> {

    private Node<E> first;

    // 链表中的节点
    private static class Node<E> {
        E element; // 节点元素
        Node<E> next; // 节点指向下一个节点

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
    
}

获取元素 – get()

@Override
public E get(int index) {
    return node(index).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;
}

清空元素 – clear()

在这里插入图片描述

  • next 不需要设置为 null，因为 first 指向了 null，后面的 Node 没有被指向，在 Java 中会自动被垃圾回收。
@Override
public void clear() {
    size = 0;
    first = null;
}

添加元素 – add(int index, E element)

在这里插入图片描述
添加元素尤其要注意 0 位置，给空链表添加第一个节点是个特殊情况：

@Override
public void add(int index, E element) {
    /*
    * 最好：O(1)
    * 最坏：O(n)
    * 平均：O(n)
    */
    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++;
}

删除元素 – remove(int index)

在这里插入图片描述

@Override
public E remove(int index) {
    /*
    * 最好：O(1)
    * 最坏：O(n)
    * 平均：O(n)
    */
    rangeCheck(index);
    Node<E> node = first;
    if (index == 0) { // 删除第一个元素是特殊情况
        first = first.next;
    } else {
        Node<E> prev = node(index - 1); // 找到前一个元素
        node = prev.next; // 要删除的元素
        prev.next = node.next; // 删除元素
    }
    size--;
    return node.element;
}

单向链表完整源码

package com.mj.single;

import com.mj.AbstractList;

/**
 * 单向链表
 * @author yusael
 */
public class SingleLinkedList<E> extends AbstractList<E> {

    private Node<E> first;

    // 链表中的节点
    private static class Node<E> {
        E element; // 节点元素
        Node<E> next; // 节点指向下一个节点

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }

    /**
     * 根据索引找到节点对象
     */
    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 void clear() {
        size = 0;
        first = null;
    }

    @Override
    public E get(int index) {
        /*
         * 最好:O(1)
         * 最坏:O(n)
         * 平均:O(n)
         */
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        /*
         * 最好:O(1)
         * 最坏:O(n)
         * 平均:O(n)
         */
        E old = node(index).element;
        node(index).element = element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        /*
         * 最好：O(1)
         * 最坏：O(n)
         * 平均：O(n)
         */
        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++;
    }

    @Override
    public E remove(int index) {
        /*
         * 最好：O(1)
         * 最坏：O(n)
         * 平均：O(n)
         */
        rangeCheck(index);
        Node<E> node = first;
        if (index == 0) { // 删除第一个元素是特殊情况
            first = first.next;
        } else {
            Node<E> prev = node(index - 1); // 找到前一个元素
            node = prev.next; // 要删除的元素
            prev.next = node.next; // 删除元素
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        // 有个注意点, 如果传入元素为null, 则不能调用equals方法, 否则会空指针
        // 因此需要对元素是否为null做分别处理
        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++) {
                if (node.element.equals(element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    @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();
    }

}

带虚拟头结点的单向链表

有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点（不存储数据）。
在这里插入图片描述
带虚拟头结点的单向链表与普通单向链表代码类似：但是 add、reomove 略有不同；

package com.mj.single;

import com.mj.AbstractList;

/**
 * 增加一个虚拟头结点
 * @author yusael
 */
public class SingleLinkedList2<E> extends AbstractList<E> {

    private Node<E> first;

    //**********************************
    public SingleLinkedList2() { // 初始化一个虚拟头结点
        first = new Node<>(null, null);
    };
    //**********************************

    private static class Node<E> {
        E element;
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }

    @Override
    public void clear() {
        size = 0;
        first = null;
    }

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

    @Override
    public E set(int index, E element) {
        E old = node(index).element;
        node(index).element = element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        Node<E> prev = (index == 0) ? first : node(index - 1);
        prev.next = new Node<>(element, prev.next);
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);

        Node<E> prev = (index == 0) ? first : node(index - 1);
        Node<E> node = prev.next;
        prev.next = node.next;

        size--;
        return prev.element;
    }

    @Override
    public int indexOf(E element) {
        // 有个注意点, 如果传入元素为null, 则不能调用equals方法, 否则会空指针
        // 因此需要对元素是否为null做分别处理
        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++) {
                if (node.element.equals(element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    
    /**
     * 根据索引找到节点
     * 
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> node = first.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("[size=").append(size).append(", ");
        Node<E> node = first.next;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            string.append(node.element);
            node = node.next;
        }
        string.append("]");
        return string.toString();
    }

}

动态数组、链表复杂度分析

数组的随机访问速度非常快：elements[n] 的效率与 n 是多少无关；
在这里插入图片描述

双向链表（LinkedList）

双向链表可以提升链表的综合性能；
在这里插入图片描述
双向链表只有一个元素的情况：first、last 指向同一个节点
在这里插入图片描述

/**
 * 双向链表
 * @author yusael
 */
public class LinkedList<E> extends AbstractList<E> {

    private Node<E> first;
    private Node<E> last;

    private static class Node<E> {
        E element;
        Node<E> prev;
        Node<E> next;

        public Node(Node<E> prev, E element, Node<E> next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
        @Override
        public String toString(){
            StringBuilder sb = new StringBuilder();
            if(prev != null){
                sb.append(prev.element);
            }else{
                sb.append("null");
            }
            sb.append("_").append(element).append("_");
            if(next != null){
                sb.append(next.element);
            }else{
                sb.append("null");
            }
            
            return sb.toString();
        }
    }
}

双向链表 – get(int index)

@Override
public E get(int index) {
    return node(index).element;
}
/**
 * 根据索引找到节点
 */
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;
    }
}

双向链表 – add(int index, E element)

在这里插入图片描述

@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    // size == 0
    // index == 0
    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) { // index == 0
            first = node;
        } else {
            prev.next = node;
        }
    }
    size++;
}

双向链表 – remove(int index)

在这里插入图片描述

@Override
public E remove(int index) {
    rangeCheck(index);

    Node<E> node = node(index);
    Node<E> prev = node.prev;
    Node<E> next = node.next;
    
    if (prev == null) { // index == 0
        first = next;
    } else {
        prev.next = next;
    }
    
    if (next == null) { // index == size - 1
        last = prev;
    } else {
        next.prev = prev;
    }
    size--;
    return node.element;
}

双向链表完整源码

package com.mj;

import com.mj.AbstractList;

/**
 * 双向链表
 * @author yusael
 */
public class LinkedList<E> extends AbstractList<E> {

    private Node<E> first;
    private Node<E> last;

    private static class Node<E> {
        E element;
        Node<E> prev; // 指向前驱节点
        Node<E> next; // 指向后继节点

        public Node(Node<E> prev, E element, Node<E> next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
        @Override
        public String toString(){
            StringBuilder sb = new StringBuilder();
            if(prev != null){
                sb.append(prev.element);
            }else{
                sb.append("null");
            }
            sb.append("_").append(element).append("_");
            if(next != null){
                sb.append(next.element);
            }else{
                sb.append("null");
            }
            
            return sb.toString();
        }
    }
    
    @Override
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    @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);

        // size == 0
        // index == 0
        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) { // index == 0
                first = node;
            } else {
                prev.next = node;
            }
        }
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);

        Node<E> node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        
        if (prev == null) { // index == 0
            first = next;
        } else {
            prev.next = next;
        }
        
        if (next == null) { // index == size - 1
            last = prev;
        } else {
            next.prev = prev;
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == element) return i;
                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element.equals(element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 根据索引找到节点
     * 
     * @param index
     * @return
     */
    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;
        }
    }
    
    @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);
            node = node.next;
        }
        string.append("]");
        return string.toString();
    }

}

双向链表 vs 单向链表

粗略对比一下删除的操作数量：操作数量缩减了近一半
在这里插入图片描述
有了双向链表，单向链表是否就没有任何用处了？

  • 并非如此，在哈希表的设计中就用到了单链表
  • 至于原因，在哈希表章节中会讲到

双向链表 vs 动态数组

动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可以通过缩容解决）
双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存空间的浪费

  • 如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择
  • 如果频繁在头部进行添加、删除操作，建议选择使用双向链表
  • 如果有频繁的 （在任意位置）添加、删除操作，建议选择使用双向链表
  • 如果有频繁的查询操作（随机访问操作），建议选择使用动态数组

练习题

练习 – 删除链表中的节点

237_删除链表中的节点：https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

练习 – 反转一个链表（递归、非递归解法）

206_反转链表：https://leetcode-cn.com/problems/reverse-linked-list/
在这里插入图片描述
递归解法：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null; // 空链表
        if(head.next == null) return head; // 只有一个节点
        ListNode newHead = reverseList(head.next);
        head.next.next = head; // newHead->1->2->3->4->5->null
        head.next = null;
        return newHead;
    }
}

非递归解法 - 头插法：
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }
        return newHead;
    }
}

练习 – 判断一个链表是否有环（快慢指针）

141_环形链表：https://leetcode-cn.com/problems/linked-list-cycle/
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
快慢指针解法：
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next; // 快指针每次都比慢指针快一步(包括开始)
        while (fast != null && fast.next != null) {
            if (slow.val == fast.val) return true;
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }
}
文章标签：
Java
C++
存储
关键词：
数据结构链表
链表双向链表
数据结构双向链表
单向链表
数据结构单向
萌宅鹿同学
目录
相关文章
2的n次方_
|
15天前
|
存储 Java 索引
【数据结构】链表从实现到应用，保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同，其元素在内存中非连续分布，通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念，包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表，说明了其拥有前后两个指针的特点，并展示了相关操作的代码实现。最后，对比了ArrayList与LinkedList的不同之处，包括它们底层实现、时间复杂度以及适用场景等方面。
2的n次方_
32 10
【数据结构】链表从实现到应用，保姆级攻略
wljslmz
|
29天前
|
存储 Java
Java 中的 LinkedList 是单链表还是双向链表？
【8月更文挑战第22天】
wljslmz
21 1
aliyun6365824167
|
1月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点，然后把后半部分逆置，最近前后两部分一一比对，如果节点的值全部相同，则即为回文。
aliyun6365824167
16 0
aliyun6365824167
|
1月前
|
存储 测试技术
【初阶数据结构篇】双向链表的实现（赋源码）
因为头结点的存在，plist指针始终指向头结点，不会改变。
aliyun6365824167
20 0
aliyun6365824167
|
1月前
|
存储 测试技术
【初阶数据结构篇】单链表的实现（附源码）
在尾插/尾删中，都需要依据链表是否为空/链表是否多于一个节点来分情况讨论，目的是避免对空指针进行解引用造成的错误。
aliyun6365824167
18 0
国中之林
|
1月前
|
算法
【数据结构与算法】共享双向链表
【数据结构与算法】共享双向链表
国中之林
11 0
国中之林
|
1月前
|
算法
【数据结构与算法】双向链表
【数据结构与算法】双向链表
国中之林
10 0
小徐在进步
|
9天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
28 8
小徐在进步
|
11天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
46 3
2的n次方_
|
13天前
|
Java
【数据结构】栈和队列的深度探索，从实现到应用详解
本文介绍了栈和队列这两种数据结构。栈是一种后进先出（LIFO）的数据结构，元素只能从栈顶进行插入和删除。栈的基本操作包括压栈、出栈、获取栈顶元素、判断是否为空及获取栈的大小。栈可以通过数组或链表实现，并可用于将递归转化为循环。队列则是一种先进先出（FIFO）的数据结构，元素只能从队尾插入，从队首移除。队列的基本操作包括入队、出队、获取队首元素、判断是否为空及获取队列大小。队列可通过双向链表或数组实现。此外，双端队列（Deque）支持两端插入和删除元素，提供了更丰富的操作。
2的n次方_
14 0
【数据结构】栈和队列的深度探索，从实现到应用详解