测试基础 2.数组、链表、跳表的基本实现和特性 (7 天掌握算法面试必考知识点)

在路上 · 2020年07月18日 · 2371 次阅读

全文内容主要源于极客大学的算法课，仅作为笔记使用。

1、数组

数组：在内存中，占用连续内存空间的，有序的元素序列。
数组元素的类型没有要求，即为泛型。

底层原理

当申请数组时，内存管理器分配一个连续的内存地址。每一个地址可以直接通过内存管理器进行访问。
如下图所示，即为数组相应的内存地址：

直接访问的话，访问第一个元素和访问任意一个元素，时间复杂度都是一样的，为 O(1)。

数组特性

访问速度快

访问数组时，其实是利用指针，即内存地址，直接访问对应内存地址中的数值，所以访问速度非常快。
访问数组的时间复杂度：常数复杂度 O(1)

删除和插入: O(n)

如下图所示：
当向数组中插入元素 D 时，首先要将 E、F、G 都向下挪动一个位置，然后将 index=3 的地址值赋值为 D。
同理：

最慢的插入操作：插入位置为第一个元素位置，要挪动 n 个元素，时间复杂度为 O(n)
最快的插入操作：插入位置为最后一个元素位置，不需要挪动元素，时间复杂度为 O(1)
平均要挪动一半元素

Array 各操作时间复杂度

prepend: O(n)，正常情况下是 O(n)，但是可以进行特殊优化到 O(1)。初始化时申请稍大一些的内存空间，然后在数组最开始预留一部分空间，然后 prepend 操作只需要把头下标千一一个位置即可。
append: O(1)
lookup: O(1)
insert: O(n)
delete: O(n)

2、链表（LinkedList）

概念

链表：元素由 Value 和 next 组成，next 指向下一个元素，在内存中是非连续空间。链表元素一般由 class 定义。
单向链表：如果只有一个 next 指针，是单向链表。
双向链表：如果由两个指针，next 指向下一个元素，先前指针 prev 或 previous 指向上一个元素。一般头叫做 Head，尾叫做 Tail。
循环链表：如果 next 指向 Head，叫做循环链表。

LinkedList 定义

最简单的链表定义：

class LinkedList {
    Node head;  // head of list

    /* Linked List Node */
    class Node {
        int data;
        Node next;

        Node(int d) { data = d; }
    }

}