【恋上数据结构与算法一】(三)链表

作者: AlanGe | 来源:发表于2021-04-01 22:48 被阅读0次

数据结构和算法（三）双向链表与双向循环链表的实现
数据结构和算法（五）栈的操作和实现
数据结构和算法（四）链表相关面试题
【恋上数据结构与算法一】(三)链表
数据结构和算法（6）队列的操作和实现
数据结构之栈
数据结构之队列
数据结构之二分查找的概念
数据结构之二叉树
数据结构之二叉搜索树

1、链表(Linked List)

◼ 动态数组有个明显的缺点
可能会造成内存空间的大量浪费

◼ 能否用到多少就申请多少内存?
链表可以办到这一点

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

2、链表的设计

3、接口设计

◼ 链表的大部分接口和动态数组是一致的

4、清空元素 – clear()

size = 0;
first = null;
思考:next 需要设置为 null 么？

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

5、添加元素 - add(int index, E element)

node方法用于获取index位置的节点

注意0位置

在编写链表过程中，要注意边界测试，比如 index 为 0 、size – 0 、size 时

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

6、删除元素 - remove(int index)

size--

注意0位置

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

测试
public static void main(String[] args) {

    List<Integer> list = new LinkedList<Integer>();
    list.add(20);
    list.add(0, 10);
    list.add(30);
    list.add(list.size(), 40);
    
    list.remove(1);
    
    System.out.println(list);
}

打印结果：size=3, [10, 30, 40]

7、练习

练习 – 删除链表中的节点
◼ leetcode-cn.com/problems/delete-node-in-a-linked-list/

练习 – 反转一个链表

◼ leetcode-cn.com/problems/reverse-linked-list/

◼ 请分别用递归、迭代(非递归)两种方式实现

练习 – 反转一个链表 – 递归

练习 – 反转一个链表 – 非递归 – 头插法

练习 – 判断一个链表是否有环
◼ leetcode-cn.com/problems/linked-list-cycle/

8、虚拟头结点

◼ 有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点(不存储数据)

9、虚拟节点 – node方法

10、虚拟节点 – 添加、删除

11、复杂度分析

◼ 最好情况复杂度
◼ 最坏情况复杂度
◼ 平均情况复杂度

12、数组的随机访问

◼ 数组的随机访问速度非常快
◼ elements[n]的效率与n是多少无关

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

size 是数组规模 n

14、动态数组add(E element)复杂度分析

◼ 最好:O(1)
◼ 最坏:O(n)
◼ 平均:O(1)
◼ 均摊:O(1)

假设最大容量是4

相当于每次 add 的操作次数是 2，也就是 O(1) 复杂度

◼ 什么情况下适合使用均摊复杂度
经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况

15、动态数组的缩容

◼ 如果内存使用比较紧张，动态数组有比较多的剩余空间，可以考虑进行缩容操作
比如剩余空间占总容量的一半时，就进行缩容
◼ 如果扩容倍数、缩容时机设计不得当，有可能会导致复杂度震荡

16、双向链表

◼ 此前所学的链表，也叫做单向链表
◼ 使用双向链表可以提升链表的综合性能

17、双向链表 – 只有一个元素

18、双向链表 – node方法

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

20、双向链表 – remove(int index)

21、双向链表 vs 单向链表

◼ 粗略对比一下删除的操作数量
单向链表:

除以n平均一下是

双向链表：

除以n平均一下是

操作数量缩减了近一半

22、双向链表 vs 动态数组

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

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

◼ 有了双向链表，单向链表是否就没有任何用处了?
并非如此，在哈希表的设计中就用到了单链表
至于原因，在哈希表章节中会讲到

23、LinkedList源码分析

◼ JDK 中的 java.util.LinkedList
双向链表
clear 分析
多出来的接口
✓ ...First
✓ ...Last

24、单向循环链表

25、单向循环链表 – 只有1个节点

26、单向循环链表 – add(int index, E element)

27、单向循环链表 – remove(int index)

28、双向循环链表

29、双向循环链表 – 只有1个节点

30、双向循环链表 – add(int index, E element)

31、双向循环链表 – remove(int index)

32、练习 – 约瑟夫问题(Josephus Problem)

33、如何发挥循环链表的最大威力？

◼ 可以考虑增设1个成员变量、3个方法
current :用于指向某个节点
void reset() :让 current 指向头结点 first
E next() :让 current 往后走一步，也就是 current = current.next
E remove() :删除 current 指向的节点，删除成功后让 current 指向下一个节点