数据结构与算法(一)

为什么要学数据结构与算法？

在工作中，我们总是喜欢高谈阔论，谈论高性能、高可用、微服务等，很少有人能潜心钻研基础知识，提升自己代码层面的编程能力。数据结构是一组数据的存储结构，算法是操作数据的方法，简单的说，数据结构是为算法服务的，算法是要作用在特定的数据结构上的。数据结构与算法就像是一座大厦的地基，地基够“坚实”，我们的技术高度才能达到更高。无论你是想在工作中更进一步，还是想寻一份更好的工作，数据结构和算法都是你必修的“内功”。接下来我会根据自己所学加以自己的理解，挑选以下的内容由浅入深地带你进入数据结构与算法的世界。

8 个数据结构：数组、链表、栈、队列、散列表、树(二叉树、堆、多路查找树、Trie树)、跳表、图
10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

那有人说了，这些内容在书上都可以学习到啊，你这个有什么优势呢？

不错，诸如像《算法导论》这些经典书籍，全面却枯燥乏味，脱离实际。而在这里，我会探究它们的定义、特征、适用问题以及实际场景等等，带你一步一步地掌握它们，简洁又高效。

好，话不多说，直入主题！

---

数组

几乎每一种语言，都会有数组这种数据结构。大家应该或多或少都用过数组，这是一种最基础的数据结构，那么让我们来一探究竟。

定义

数组（Array），是一种线性表数据结构。使用一块连续的内存空间，来存储一组具有相同类型的数据。

线性表：是n个具有相同特性的数据元素的有限序列，就像线一样，数据之间是简单的前后关系，包括数组、链表、队列、栈等等。
非线性表：数据之间并不是简单的前后关系，比如二叉树、堆、图等。

连续的内存空间和相同类型的数据。正因为数组有这两个限制，所以具备了“随机访问”的逆天特性，可以根据下标访问任意位置的元素。但要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

数据访问

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)

假设有一个数组，长度为10，即int[] a = new int[10] ，计算机会给其分配了一块连续的内存空间 1000～1039，其中，内存块的首地址为 base_address = 1000。

那么数组是如何实现根据下标随机访问数组元素的呢？众所周知，每个内存单元都会被计算机分配一个地址，而数组元素的地址是连续的，计算机可以通过地址来访问内存中的数据。当我们需要随机访问某个元素时，其实是通过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小,数组a中存储的是 int 类型数据，所以 data_type_size 就为 4 个字节。知道了随机访问的原理，那就衍生出了一个问题：

为什么数组要从 0 开始编号，而不是从 1 开始呢？
根据以上的讲解，我们知道数组的寻址公式是
a[k]_address = base_address + k * type_size
获取第一个元素，就要使 k = 0，a[0] 就是偏移为 0 的位置，即第一个元素
如果数组从 1 开始计数，那我们寻址公式就变为：
a[k]_address = base_address + (k-1)*type_size
从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令，降低效率。

插入

假设数组长度为 n，在数组中的第 k 个位置插入一个数据。我们需要将第 k～n 这部分的元素都顺序地往后挪一位，再把新增数据放在第 k 个位置。

数组末尾插入元素：最好时间复杂度O(1)
数组开头插入元素：最坏时间复杂度O(n)
平均时间复杂度 (1+2+…n)/n=O(n)

改进方法：如果数组只用来存储数据，不要求有序，可以把第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置

删除

删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据

删除末尾数据：最好时间复杂度O(1)
删除开头数据：最坏时间复杂度O(n)
平均时间复杂度O(n)

改进方法：如果删除次数多，可以在每次删除时只进行逻辑删除，然后将多次删除操作集中在一起执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

ArrayList相比数组的优点

• ArrayList 封装了很多数组操作的细节，如数组插入、删除数据时需要搬移其他数据等
• ArrayList 支持动态扩容。每次存储空间不够的时候，ArrayList 会将空间自动扩容为 1.5 倍大小。但是这一过程涉及内存申请和数据搬移，比较耗时。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组，当第 11 个数据需要存储到数组中时，我们就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。

数组的应用场景

• ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而自动装箱、拆箱有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
• 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
• 当要表示多维数组时，用数组往往会更加直观。

链表

链表与数组不同，不需要一块连续的内存空间，它可以通过“指针”将一组零散的内存块串联起来使用，每个内存块称为一个结点。

链表的结构很多，这里重点介绍三种最常见的：单链表、循环链表、双向链表。

单链表

单链表的结点包含存储数据 data 和一个后继指针 next ，next 指向下一个结点地址。

其中
头结点是第一个结点，用来记录链表的首地址，通过它可以遍历得到整条链表
尾结点是链表上最后一个结点，指针指向 NULL

插入和删除

在链表中插入和删除不需要像数组那样搬移数据，而是改变相邻结点的指针就行了，时间复杂度为O(1)，如图所示

顺序访问

链表中的数据在内存中时零散的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。需要 O(n) 的时间复杂度。

循环链表

循环链表是一种特殊的单链表，与单链表的区别是尾结点指针指向链表的头结点。从图中看出，循环链表像个环一样首尾相连。

不难看出，循环链表的特点是从链尾到链头比较方便。当我们要解决问题的数据具有环型结构特点时，就特别适合采用循环链表。比如著名的约瑟夫问题，代码会简洁很多。

双向链表

双向链表，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。

双向链表可以在 O(1) 时间复杂度下找到前驱结点，所以双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

删除

分为两种情况：

• 删除结点中“值等于某个给定值”的结点：不管是单链表还是双向链表，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点。总时间复杂度均为 O(n)。
• 删除给定指针指向的结点：已知要删除的结点，但是删除某个结点 b 需要知道其前驱结点，而单链表只能从头结点开始遍历链表，直到 a->next=b，说明 a 是 b 的前驱结点。但是双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。所以单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要 O(1) 的时间复杂。

插入

与删除同理，如果要在链表的某个结点前插入一个结点，双向链表的时间复杂度是O(1)，而单链表需要 O(n) 的时间复杂度。

实际的软件开发中，虽然双向链表比较费内存，但还是比单链表的应用更加广泛的原因，这运用的是用空间换时间的设计思想。当内存空间充足的时候，为了追求代码的执行速度，就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反就要用时间换空间的设计思路。

经典例题：基于链表实现 LRU 缓存淘汰算法

我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中，又可以分为两种情况：
   • 如果此时缓存未满，则将此结点直接插入到链表的头部；
   • 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

不管缓存有没有满，我们都需要遍历一遍链表，所以这种基于链表的实现思路，缓存访问的时间复杂度为 O(n)。引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。

编写链表代码的技巧

1. 留意边界条件处理：编写过程和编写完成之后，检查边界条件是否考虑全面，以及代码在边界条件下是否能正确运行。

   • 如果链表为空时，代码是否能正常工作？
   • 如果链表只包含一个结点时，代码是否能正常工作？
   • 如果链表只包含两个结点时，代码是否能正常工作？
   • 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

2. 举例法、画图法：对于稍微复杂的链表操作，很容易绕晕。写代码时可以找一个具体的例子，画在纸上，这样就会感觉到思路清晰很多。

3. 多写多练：多刷leetcode链表代码

链表 vs 数组

• 数组简单易用，在实现上使用的是连续的内存空间，可以根据下标随机访问，所以访问效率更高，时间复杂度为O(1);但是插入删除需要挪动大量数据，时间复杂度为O(n)。而链表在内存中并不是连续存储，当随机访问一个结点时，要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。需要 O(n) 的时间复杂度。
• 数组大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。

  ArrayList也可以支持动态扩容,当我们往支持动态扩容的数组中插入一个数据时，如果数组中没有空闲空间了，就会申请一个更大的空间，将数据拷贝过去，而数据拷贝的操作是非常耗时的。

栈

定义

栈是一种“操作受限”的线性表，只允许在一端插入和删除数据，这一端被称为栈顶，另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，从一个栈删除元素又称作出栈或退栈。类似于叠盘子，进栈等同于往最上面叠一个盘子，出栈等同于从顶上拿走一个盘子。

“先进后出”是栈的特征之一。

栈用数组实现叫做顺序栈，用链表实现叫做链式栈。

实现一个顺序栈

// 基于数组实现的顺序栈
public class ArrayStack {
  private int[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           // 栈的大小
 
  // 初始化数组，申请一个大小为 n 的数组空间
  public ArrayStack(int n) {
    this.items = new int[n];
    this.n = n;
    this.count = 0;
  }
 
  // 入栈操作
  public boolean push(int item) {
    // 数组空间不够了，直接返回 false，入栈失败。
    if (count == n) return false;
    // 将 item 放到下标为 count 的位置，并且 count 加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public int pop() {
    // 栈为空，则直接返回 null
    if (count == 0) return null;
    // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
    int tmp = items[count-1];
    --count;
    return tmp;
  }
}

实现一个链式栈

public class LinkedListStack {
  private Node top = null;

  public void push(int value) {
    Node newNode = new Node(value, null);
    // 判断是否栈空
    if (top == null) {
      top = newNode;
    } else {
      newNode.next = top;
      top = newNode;
    }
  }

  /**
   * -1表示栈中没有数据。
   */
  public int pop() {
    if (top == null) return -1;
    int value = top.data;
    top = top.next;
    return value;
  }

  public void printAll() {
    Node p = top;
    while (p != null) {
      System.out.print(p.data + " ");
      p = p.next;
    }
    System.out.println();
  }

  private static class Node {
    private int data;
    private Node next;

    public Node(int data, Node next) {
      this.data = data;
      this.next = next;
    }

    public int getData() {
      return data;
    }
  }
}

不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。
在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

注意，这里存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

支持动态扩容的顺序栈

要实现一个支持动态扩容的栈，我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后，我们就申请一个更大的数组，将原来的数据搬移到新数组中。

应用场景

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。

1. 栈在函数调用中的应用（函数调用栈）
   操作系统给每个线程分配了一块独立的内存空间，即java虚拟机栈，虚拟机栈描述的是java方法执行的内存模型。每个 Java 方法在执行的同时会创建一个栈帧，用于存储局部变量表、操作数栈、动态链接，方法出口等信息。从方法调用直至执行完成的过程，对应着一个栈帧在 Java 虚拟机栈中入栈和出栈的过程。

int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}
 
int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

2. 栈在表达式求值中的应用（来实现表达式求值）
   编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。
   如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。下图是3+5*8-6的演示过程。
   

3. 栈在括号匹配中的应用(检查表达式中的括号是否匹配)
   我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式

队列

队列也是一种操作受限的线性表数据结构。先进先出，是队列的最大特点。

最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。我们在出队时可以不用搬移数据。如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作。借助这个思想，出队函数 dequeue() 保持不变，我们稍加改造一下入队函数 enqueue() 的实现

实现一个顺序队列

public class ArrayQueue {
    // 数组：items，数组大小：n
    private int[] items;
    private int n = 0;
    // head 表示队头下标，tail 表示队尾元素下一位
    private int head = 0;
    private int tail = 0;

    // 申请一个大小为 capacity 的数组
    public ArrayQueue(int n){
        this.items = new int[n];
        this.n = n;
    }

    // 入队
    public boolean enqueue(int item){
        if(n == tail){
            if(head == 0){
                return false;
            }
            for (int i = head; i < tail; i++) {
                items[i-head] = items[i];
            }
            tail -= head;
            head = 0;
        }
        items[tail++] = item;
        return true;
    }

    //出队
    public Integer dequeue(){
        if(head == tail){
            return null;
        }
        int tmp = items[head++];
        return tmp;
    }
}

实现一个链式队列

public class LinkedListQueue {
    private Node head;
    private Node tail;
    private int size;

    public LinkedListQueue(){
        head = new Node();
        tail = head;
        size = 0;
    }

    public boolean enqueue(int val){
        Node tmp = new Node(val);
        if(head.val == null){
            head = tmp;
            tail = tmp;
        }else{
            tail.next = new Node(val);
            tail = tail.next;
        }
        size++;
        return true;
    }

    public Integer dequeue(){
        if(head == null){
            return null;
        }
        int tmp = (int) head.val;
        head = head.next;
        size--;
        return tmp;
    }
}

class Node<E>{
    E val;
    Node next;
    Node(E val, Node next){
        this.val = val;
        this.next = next;
    }

    Node(E val){
        this(val, null);
    }

    Node(){
        this(null, null);
    }
}

循环队列

用数组实现队列时，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。循环队列能够有效避免数据搬移。将队列首尾相连，形成一个环，如图所示。

head指向队首位置
tail指向队尾元素的下一位
队空判定条件：head == tail
队满判定条件：(tail+1)%n==head

public class CircularQueue {
    private int[] items;
    private int n;
    private int head = 0;
    private int tail = 0;

    public CircularQueue(int n){
        this.items = new int[n];
        this.n = n;
    }
    //入队
    public boolean enqueue(int item){
        if((tail+1)%n == head){
            return false;
        }
        items[tail] = item;
        tail = (tail+1)%n;
        return true;
    }
    //出队
    public Integer dequeue(){
        if(head == tail){
            return null;
        }
        int tmp = items[head];
        head = (head+1)%n;
        return tmp;
    }
}

阻塞队列与并发队列

队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。我们可以使用阻塞队列，轻松实现一个“生产者 - 消费者模型”！

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。

应用场景

队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

以上就是数据结构与算法数组、链表、栈以及队列的相关内容啦，喜欢的小伙伴可以关注收藏我的私人博客，这里有你想要的一切哦，兄弟，还等啥呢？