线性数据结构

基础知识

算法

在计算机领域里，算法是一系列程序指令，用于处理特定的运算和逻辑问题

数据结构

数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据

时间复杂度

• O(1)，O(logn), O(n), O(nlogn), O(n^2), O(2^n), O(n!)

空间复杂度

• 例子：查找一个整数序列中重复的数
  • 双重循环：每遍历一个数就回顾之前遍历的所有整数，判断有没有重复的，O(n^2)
  • 利用散列表：每遍历一个数就把该数放到散列表中，"key"代表整数值，"value"代表出现的次数，没遍历一个整数，value值加一。O(n)
• 常量空间，线性空间，二维空间，递归空间
• 递归空间：计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。
  • “方法调用栈”包括进栈和出栈两个行为
  • 进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中
  • 方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出
  • 执行递归操作所需要的内存空间和递归的深度n成正比

数组

数组

有限个相同类型的变量所组成的有序集合

数组的基本操作

• 读取元素：使用数组下标随机读取
• 更新元素：使用数组下标直接赋值
• 插入元素：尾部插入，中间插入，超范围常插入，数组向后挪动，空间不够需要扩容
• 删除元素：数组向前挪动

数组优缺点

• 数组拥有非常高效的随机访问能力
• 插入、删除元素都会导致大量元素被迫移动，影响效率
• 数组所适合的是读操作多、写操作少的场景

链表

链表

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。

链表的基本操作

• 查找节点:：从头指针根据next依次遍历查找，时间复杂度未O(n)

• 更新节点：找到对应的节点后直接更新数据

• 插入节点：

  • 尾部插入：把最后一个节点的next指针指向新节点
  • 头部插入：把新节点的next指向原先的头节点，把新节点变为头节点
  • 中间插入：把新节点的next指向要插入位置的节点，把插入位置的前一个节点的next指向新节点

• 删除元素：

  • 尾部删除：把倒数第二个节点的next指向空
  • 头部删除：把头节点设为原先头节点的next
  • 中间删除：把要删除节点的前置节点指向要删除节点的后一个节点。

package linkedlist; public class LinkedList { private Node head = new Node(0); private Node last = new Node(0); private int size = 0; /** * 插入节点 * @param data * @param index */ public void insert(int data, int index) throws Exception{ if(index < 0 || index > size) { throw new IndexOutOfBoundsException("数组越界"); } Node insertedNode = new Node(data); Node preNode = get(index - 1); insertedNode.next = preNode.next; preNode.next = insertedNode; size++; if(index == size) { last = insertedNode; } } /** * 删除节点 * @param index * @return */ public Node remove(int index) { if(index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("数组越界"); } Node preNode = get(index-1); Node removeNode = preNode.next; preNode.next = removeNode.next; size--; if(index == (size-1)) { last = preNode; } return removeNode; } /** * 输出链表 */ public void outPut() { Node temp = head.next; while (temp != null) { System.out.println(temp.data); temp = temp.next; } } /** * 获取节点 * @param index * @return */ public Node get(int index) { if(index == -1) { return head; } if(index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("数组越界"); } Node temp = head; for(int i = 0;i <= index;i++) { temp = temp.next; } return temp; } /** * 节点类 */ private static class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } public static void main(String[] args) throws Exception { LinkedList myLinkedList = new LinkedList(); myLinkedList.insert(3, 0); myLinkedList.insert(7, 1); myLinkedList.insert(9, 2); myLinkedList.insert(5, 3); myLinkedList.insert(6, 1); myLinkedList.outPut(); } } 

链表VS数组

栈和队列

物理结构和逻辑结构

栈

栈（stack）是一种线性数据结构，栈中的元素只能先入后出，最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶（top）

栈的基本操作

• 入栈：把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。
• 出栈：把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。
• 入栈、出栈的时间复杂度都是O(1)。

队列

队列（queue）是一种线性数据结构，队列中的元素只能先入先出，队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）

队列的数组实现

队列的链表实现

队列的基本操作

• 入队：把新元素放入队列中，只允许在队尾的位置放入元素
• 出队：把元素移出队列，只允许在队头一侧移出元素
• 队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1

循环队列

• （队尾下标+1）%数组长度 = 队头下标时，代表此队列真的已经满了

• 入队：rear = (rear+1)%length

• 出队：front = (front+1)%length

  

代码示例

package linkedlist; public class Queue { private int[] array; private int front; private int rear; /** * 构造函数 * @param capacity */ public Queue(int capacity) { this.array = new int[capacity]; } /** * 入队 * @param element * @throws Exception */ public void enQueue(int element) throws Exception { //队列满 if((rear + 1)%array.length == front) { throw new Exception("队列已满！"); } array[rear] = element; rear = (rear + 1)%array.length; } /** * 出队 * @return * @throws Exception */ public int deQueue() throws Exception { if(rear == front) { throw new Exception("队列空！"); } int deElement = array[front]; front = (front + 1)%array.length; return deElement; } /** * 输出队列 */ public void output() { for(int i = front;i != rear;i = (i+1)%array.length) { System.out.println(array[i]); } } /** * 测试 * @param args * @throws Exception */ public static void main(String[] args) throws Exception { Queue myQueue = new Queue(6); myQueue.enQueue(3); myQueue.enQueue(5); myQueue.enQueue(6); myQueue.enQueue(8); myQueue.enQueue(1); myQueue.deQueue(); myQueue.deQueue(); myQueue.deQueue(); myQueue.enQueue(2); myQueue.enQueue(4); myQueue.enQueue(9); myQueue.output(); } } 

栈的应用

• 栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”。
• 栈还有一个著名的应用场景是面包屑导航，使用户在浏览页面时可以轻松地回溯到上一级或更上一级页面。

队列的应用

• 队列的输出顺序和输入顺序相同，所以队列通常用于对“历史”的回放，也就是按照“历史”顺序，把“历史”重演一遍。
• 在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。
• 网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，再按照存入队列的顺序来依次抓取和解析的。
• 双端队列：把栈和队列的特点结合起来，既可以先入先出，也可以先入后出。从队头一端可以入队或出队，从队尾一端也可以入队或出队。

哈希表

散列表也叫作哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1)。

哈希函数

• 数组只能根据下标，像a[0]、a[1]、a[2]、a[3]、a[4]这样来访问，而哈希表的Key则是以字符串类型为主的。
• 我们需要一个“中转站”，通过某种方式，把Key和数组下标进行转换。这个中转站就叫作哈希函数。

Java中的HashMap

在Java及大多数面向对象的语言中，每一个对象都有属于自己的hashcode，这个hashcode是区分不同对象的重要标识。无论对象自身的类型是什么，它们的hashcode都是一个整型变量。

• 最简单的转化方式是按照数组长度进行取模运算：
  • index = HashCode (Key) % Array.length
• JDK中的哈希函数并没有直接采用取模运算，而是利用了位运算的方式来优化性能。
• 通过哈希函数，我们可以把字符串或其他类型的Key，转化成数组的下标index。

哈希表的读写操作

• 写操作：hashMap.put(“002931”, “哈哈”)，通过哈希函数将key转换为index
• 哈希冲突：当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的。
• 解决哈希冲突的方法：
  • 开放寻址法：当一个key通过哈希函数获得的数组下标被占用时，按某种策略寻找一个新的下标。(在Java中，ThreadLocal所使用的就是开放寻址法)
  • 链表法(HashMap采用这种方法)：HashMap数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。
• 读操作：读操作就是通过给定的Key，在散列表中查找对应的Value，以链表法为例，调用hashMap.get(“002936”)：
  • 第1步，通过哈希函数，把Key转化成数组下标2。
  • 第2步，找到数组下标2所对应的元素，如果这个元素的Key是002936，那么就找到了；如果不是，顺着链表慢慢往下找，看看能否找到与Key相匹配的节点。

哈希表的扩容

• 对于JDK中的散列表实现类HashMap来说，影响其扩容的因素有两个。

  • Capacity：即HashMap的当前长度
  • LoadFactor：即HashMap的负载因子，默认值为0.75f

• 衡量HashMap需要进行扩容的条件：HashMap.Size >= Capacity×LoadFactor

• 扩容操作：

  1. 扩容，创建一个新的Entry空数组，长度是原数组的2倍。
  2. 重新Hash，遍历原Entry数组，把所有的Entry重新Hash到新数组中。为什么要重新Hash呢？因为长度扩大以后，Hash的规则也随之改变。

小结

• 数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。利用下标查找数组元素的时间复杂度是O(1)，中间插入、删除数组元素的时间复杂度是O(n)。
• 链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一节点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查找链表节点的时间复杂度是O(n)，中间插入、删除节点的时间复杂度是O(1)。
• 栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。栈包含入栈和出栈操作，遵循先入后出的原则（FILO）。
• 队列也是一种线性逻辑结构，可以用数组实现，也可以用链表实现。队列包含入队和出队操作，遵循先入先出的原则（FIFO）。
• 散列表也叫哈希表，是存储Key-Value映射的集合。对于某一个Key，散列表可以在接近O(1)的时间内进行读写操作。散列表通过哈希函数实现Key和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。