共计 10351 个字符，预计需要花费 26 分钟才能阅读完成。
在学习本系列的文章之前，倡议看看本篇的前作《杂感(一)》，该篇探讨了如何进行学习，以及学习策略，置信会对数据结构系列的学习会有所帮忙。
前言
在写本篇的时候，我想起大学外面，我刚学数据结构这门课程的时候，我过后对这门课是下定决心去听，然而我疏忽的有几点，大学课程是承前启后的，学习数据结构则须要对一门高级语言比拟相熟还须要有肯定的编码量，学习数据结构这门课程，阻碍才不那么的大，然而我对我过后惟一学过的 C 语言还不那么相熟还没有肯定的编码量，导致我学习这门课程的时候处于一种朦胧的状态，对数据结构这门课程处于一种似懂非懂的状态，起初代码量飞速增长之后，学习数据结构才感觉得心应手一点。所以我的倡议是在学习本系列的文章之前，也倡议对一门高级语言有大抵的理解。
再聊聊文风吧，我不大喜爱写那种书籍的笔记，将书中外围的概念记下来，我更喜爱的是以我本人的形式将这些概念组合起来，退出我本人的了解。
日常生活中的 ” 线性表 ”
排队是咱们日常生活中比拟常见的场景，除了队头和队尾的人，每个人的前后相邻者都只有一个，一个人能够看成一个结点，则称这样的结点之间的关系是一对一，即除了第一个和最初一个数据元素之外，其余数据元素都是首尾相接的。由此咱们就引出了数据结构中的线性表, 在数据结构中，把这种数据元素之间是一对一关系的构造成为线性表，线性表除了第一个和最初一个数据元素之外，其余元素都是首尾相接的。
照之前咱们所探讨的，探讨数据结构个别是探讨逻辑构造、存储构造、基于该构造的运算。
咱们首先来探讨线性表的逻辑构造，其实在介绍下面的逻辑构造下面曾经介绍过了，咱们这里来讨论一下线性表的逻辑特色:
- 存在惟一的一个被称为 ” 第一个 ” 的结点，即开始结点，队头。
- 存在惟一的一个被称为 ” 最初一个 ” 的结点，即终端结点，队尾。
- 除第一个之外，汇合中的每个结点均只有一个前驱，每个排队的人后面只有一个人
-
除最初一个之外，汇合中的每个结点均只有一个后继。从日常生活中的排队来是的话，就是每个排队的人，前面就有一个人
你看咱们将这些形象的数据结构和事实对应的场景做对照，这些绝对形象的货色是不是也不是那么难以了解了。
再议数据结构的三要素
咱们这里回顾一下《数据结构与算法剖析(一)》中咱们提到的数据结构的基本概念中的数据结构三要素:
- 数据的逻辑构造
- 数据的存储构造
- 数据的运算
数据的逻辑构造形容的是数据之前的分割，是独立于计算机的，咱们下面探讨的线性表的逻辑构造属于线性逻辑构造，属于 ” 一对一 ” 的，这里所说的一对一指的就是下面所提到的逻辑特色所形容的。数据结构从逻辑构造上划分大抵上就能够分成线性构造和非线性构造，其实还能够做更为粗疏的划分，像上面这样:
那看来当咱们谈起数据结构的时候，次要说的还是数据结构的逻辑构造呀。
接下来咱们来讨论一下数据的存储构造，数据的存储构造又称物理构造，是数据及其逻辑构造在计算机中的示意形式，指数据该如何在计算机中寄存，事实上是内存单元调配，在具体实现时用计算机语言中的数据类型来形容。
咱们思考一下存储数据应该存些什么? 怎么去存，存数据不仅仅要保留数据自身的值，还要保留数据间的分割，这样能力把相干问题的所有信息都存储残缺。保留数据间分割的目标，是能够通过这种分割找到与之相连的元素。其次咱们在计算机存储数据的目标是为了对它们进行解决，如果存进机器了但要用的时候找不到，数据的存储就失去了意义，这里 ” 找到 ” 的含意是一个是可能找到能与之相连的数据元素，所以，数据结构的存储构造的设计应该基于上面两个准则:
- 存数值，存分割
- 存的进，取的出
家喻户晓，咱们的程序在运行之后，是被加载进入内存的，大多数状况下程序运行时的数据都驻留在内存中，那么咱们该如何扫视内存呢，我的想法是咱们应该对内存进行形象，能够将内存了解为一个数组，数组的下标是该内存的地址，有的高级语言一开始就像操作系统申请了一大份内存空间 (像 Java、C#)，而有的语言则是须要了再向操作系统所申请像(C,C++)。
所以咱们能够了解为操作系统向咱们提供的最后的就是顺序存储构造，在这个根底上衍生了链式存储构造、索引存储构造、散列存储构造等。 - 顺序存储构造: 间断程序地存放数据元素，物理内存构造上，数据之间是相邻的。若数据的逻辑构造也是程序(线性的)，则逻辑构造和存储构造齐全对立了。间断寄存的数据元素能够很容易地在内存中找到。
- 链式存储构造: 链式存储构造很像火车，将每节车厢视作一个数据元素，那每节车厢还持有指针项(即铁索)。元素在内存中不肯定间断寄存，在元素中附加指针项，通过指针能够找到与之逻辑相连的数据元素的理论地位。
- 索引存储构造: 索引存储办法是存储结点信息的同时，建设一个附加的索引表。索引表中的每一个索引项，索引项的个别模式是: (关键字，地址)
- 散列存储构造: 散列处处形式，以结点的关键字做自变量，通过函数关系 F，间接算出该结点的存储地址: 结点地址 = F(关键字)，这个有的时候也被称为散列算法。
线性表的存储构造—程序表
将线性表中的元素顺次放在放在一个间断的存储空间中，这样的线性表叫程序表(Sequential List)。间断的存储空间，想到了什么，就是数组，数组中的元素就是在一个间断的存储空间中，因而能够采纳一维数组来存储线性表的各个结点。依据 ” 存结点存分割 ” 的存储准则，程序表的存储形式尽管并没有间接存储结点之间的逻辑关系，然而结点通过物理地址即存储相邻体现了逻辑相邻。
C 语言的话，通常是借助于构造体来体现线性表，实现数据结构的各种运算，比方初始化、插入、删除遍历等。但对于面向对象系的高级语言咱们通常能够借助类来表白。如果你相熟 Java 中的 ArrayList 的话，Java 中的 ArrayList 的就是一个实现即好的线性表，存储构造是线性表是数组，所以咱们看源码也是可能增进咱们对数据结构的了解，学习他人是如何设计的。在程序表上的操作通常有:
- 初始化: 给线性表一些默认参数, 一些高级语言会内置一些曾经写好了的数据结构，咱们在学习数据结构的时候能够去参考。
- 求长度: 求线性表元素的个数
- 取元素: 取给定地位的元素值
- 定位: 查找给定元素值的地位
- 插入: 在指定的地位插入给定的值
- 删除: 在指定的地位删除值，删除给定的值
线性表的英文是 SequenceList, 咱们建个类来实现以下:
/**
* @author XingKe
* @date 2021-07-24 15:04
*/
public class SequenceList{private int[] elementData;
/**
* 定义一个变量来返回给调用者
*/
private int size;
/**
* 默认数组大小
*/
private int DEFAULT_SIZE = 15;
/**
* 咱们要不仅仅满足于实现一个简略的数据结构
* 还要设计一个良好的接口、函数。给调用者一个良好的应用体验。* 发现 Java 泛型不能间接初始化, 这里就间接用 int 举例了。* @param initSize
*/
public SequenceList(int initSize) {if (initSize > 0){elementData = new int[initSize];
}else {// 抛一个异样进去 或者拒绝执行初始化}
}
/**
* 这里咱们也给出一个无参的, 不强制要求调用者肯定给定出初始大小
*/
public SequenceList() {elementData = new int[DEFAULT_SIZE];
}
/**
* 该办法默认将元素增加至数组已增加的最初一个元素之后
* @param data
*/
public void add(int data){
// 首先咱们判断元素是否放满了, 如果放满了, 再放就放不下了
// 咱们执行就须要对数组进行扩容, 然而咱们晓得数组一开始就要执行初始化.
// 所谓的扩容就是产生一个新数组
// 这里咱们先按扩容两倍来解决, 事实上这也是一种衡量
ensureCapacity(size + 1);
if (size + 1 > elementData.length){
// 阐明以后须要扩容
elementData = new int[elementData.length * 2];
}else{elementData[size++] = data;
}
}
/**
* 取指定地位的元素
* @param index
*/
public int get(int index){rangeCheck(index);
return elementData[index];
}
/**
* 取给定元素的地位, 默认返回第一个, 不存在则返回 -1
* @param data
* @return
*/
public int indexOf(int data){for (int i = 0; i < elementData.length; i++) {if (data == elementData[i]){return i;}
}
return -1;
}
/**
* 向指定地位插入元素
* @param index
* @param data
*/
public void add(int index, int data){
// 先查看地位, 有这么多查看地位的, 事实上咱们能够做一个通用的办法进去
// 这里我就不做了
// 范畴查看, 如果数组元素不够 执行扩容
rangeCheck(index);
ensureCapacity(size + 1);
// index 到 size - 1 这个地位上的元素都向后平移一位
for (int i = size - 1; i >= index; i--) {elementData[ i + 1] = elementData[i];
}
elementData[index] = data;
++size;
}
/**
* 查看是否超出了数组的包容
* 超出了执行扩容
* @param minCapacity
*/
private void ensureCapacity(int minCapacity) {if (minCapacity > elementData.length){elementData = new int[elementData.length * 2];
}
}
private void rangeCheck(int index) {if (index < 0 || index > elementData.length){throw new IndexOutOfBoundsException();
}
}
/**
* 移除指定元素的地位
* @return
*/
public int remove(int index){
// 先查看地位
rangeCheck(index);
int data = elementData[index];
// index+ 1 到 size - 1 往前挪动一个地位
for (int i = index + 1; i < size ; i++) {elementData[i] = elementData[++index];
}
// 移除后长度 --
size--;
return data;
}
/**
* 求长度这里, 咱们有两种思路, 一种是每次都遍历一下，算出长度
* 第二个就是在增加的时候, 就对 size 变量进行 ++
* 综合上来看, 第一种思路更为优良, 所以 size 办法间接返回
* @return
*/
public int size(){return size;}
}在开端插入和删除开端的工夫复杂度，咱们不再剖析，咱们仅来剖析在两头插入的工夫复杂度，事实上在开端插入也能够蕴含在两头插入这种状况中。这里的问题规模是结点的个数，也就是元素的数量，插入新元素后，结点数变为 n +1。
该算法的工夫次要破费在结点循环后移上语句上，该语句的执行次数是结点挪动次数为 n -k(k 为插入地位)。由此能够看出，所需挪动结点的次数不仅依赖于表的长度，而且还须要插入地位无关，不失一般性，假如在表中任何地位 (0<=k<=n) 上插入结点的机会是均等的:
| 插入下标地位 K | 0 | 1 | 2 | …. | n |
|---|---|---|---|---|---|
| 挪动次数 | n | n-1 | n-2 | 0 | |
| 可能的概率 | 1/n+1 | 1/n+1 | 1/n+1 | 1/n+1 | 1/n+1 |
最好状况下: 当 k = n 时，也就是仅仅须要在最初也就是相当于队尾增加元素，不须要挪动，其工夫复杂度为 O(1)。
最坏状况下: 当 k = 0 时，结点的挪动次数为 n 次，就是说要挪动表中的所有结点。
均匀状况: 在长度为 n 的线性表在第 k 个地位上插入一个结点，挪动次数为 n -k。均匀挪动次数为: (1/n+1)* (n(n+1))/2 = n/2。
由此可见在线性表上做插入运算，要均匀挪动表上一半元素，算法的均匀工夫复杂度为: O(n)。
线性表的删除运算也是须要挪动结点，以填补删除操作造成的空缺，从而保障删除后的元素间仍然通过物理地址相邻而体现逻辑相邻的关系。若删除地位刚好是最初一个元素，则只是须要删除终端结点，毋庸挪动结点: 若 0 =< i <= n-1，则必须将表中的地位 i +1,i+2…,n- 1 的结点挪动到 i，i+1，…，n- 2 上，则须要将 i + 1 至 n 共 n - i 个元素前移。
设结点数为 n，同插入元素一样，删除算法的工夫次要破费是在结点循环前移语句上，设挪动地位为 k，则该语句的挪动次数为 n -k-1，因而所需的挪动次数不仅依赖于表的长度，而且还与删除地位无关:
| 删除下标地位 K | 0 | 1 | 2 | …. | n-1 |
|---|---|---|---|---|---|
| 挪动次数 | n – 1 | n-2 | n-3 | 0 | |
| 可能的概率 | 1/n | 1/n | 1/n | 1/n | 1/n |
最好状况: 当 k = n – 1，结点前移语句不再进行，其工夫复杂度为 O(1).
最坏状况: 当 k = 0，所有结点都须要挪动。
均匀状况: 同样的不失一般性，咱们假设删除地位在 0 到 n - 1 的各个地位上呈现的概率是均等的，则结点须要挪动的均匀挪动次数为: 1/n (n-1)n / 2 = (n-1)/2. 概率乘以挪动次数而后累加。由此可见，在程序表上做删除运算，均匀约须要挪动一半元素，算法的均匀工夫复杂度为 O(n). 数组依据下标拜访的元素，不依赖于地位，工夫复杂度为 O(1).
线性表的存储构造—链表
链式存储构造或者说链式构造在现实生活中时比拟常见的，比拟为人所熟知的就是火车，像上面这样:
车厢在并没有间接分割，而是通过车厢间的链条建立联系。如果你和你的敌人一起坐火车去旅行，如果你俩刚好在买的相邻的座票，那如果你想找她谈话，那么因为相邻，你间接说就能够了。然而如果很不凑巧你的敌人在另外一个车厢，然而你晓得你敌人在哪座车厢你就能够找到他，这在某种意义上就是链式构造。
如果你的所坐的火车在找人的时候只能从后面的车厢找到前面的车厢，前面的车厢无奈达到后面的车厢，咱们就称这样的火车为单向火车，用数据结构的术语来称说的话就是单向链表。
如果你所坐的火车在找人的时候尽管只能从后面的车厢找前面的车厢，然而最初一节车厢能够达到第一节车厢，像这样的存储构造在数据结构中咱们称之为循环链表。
如果你坐的火车前面的人可能达到他后面的车厢，后面的人也能达到他前面的车厢，那么像这样的存储构造咱们就称之为双向链表。
从下面的探讨咱们应该能够得出链表结点的结构设计，像每个车厢本人装载乘客一样，也持有了下一个车厢的地位(也就是车厢之间的链条)。链表也和车厢类似，每个结点存储自身的信息之外还存储相邻结点的地位。
单链表
基于下面的探讨，单链表只能从前往后，每个结点不仅存储本人自身信息之外还存储下一个结点的存储地址，咱们能够大抵给出结点的数据结构:
public class SingleLinkedListNode {
// 存储结点自身的信息
private int data;
// 存储下一个结点的信息
private SingleLinkedListNode next;
public int getData() {return data;}
public void setData(int data) {this.data = data;}
public SingleLinkedListNode getNext() {return next;}
public void setNext(SingleLinkedListNode next) {this.next = next;}
}事实上咱们也能够将这个结点放在咱们设计的外部类中，浏览和应用起来更为简略。建设单链表通常有两种根本形式:
-
尾插法
尾插法更加简略一点，合乎直觉，咱们还是用火车车厢这个例子来解释尾插法，咱们能够将火车头了解为头结点，新来一个车厢咱们称之为 a1 吧，要挂就挂在火车头前面，再来一节车厢咱们称之为 a2 吧，这个就挂在 a1 前面。这个咱们就称之为尾插法。新来的结点都挂在最初一个结点的前面的，这也就是尾插法的来由。
-
头插法
尾插法像是排队一样，新的人排在队列的前面，那么头插法令与尾插法相同，他是插队。刚开始只有一个头结点，咱们称之为 a1，再来一个结点咱们称之为 a2，咱们将其放在 a1 之前。
在探讨存储构造和初始化形式之后，咱们开始讨论一下单链表的相干运算，这也是咱们前面介绍数据结构的基本思路，先是引入，再是介绍其存储构造，最初探讨基于该数据结构的运算。咱们这里只探讨单链表的几种外围运算: - 初始化
-
查找
查找又能够分为两种: 按值查找和按序号查找(相似于数组的按下标查找)
- 插入
-
删除
/** * @author XingKe * @date 2021-07-31 10:39 * 这里咱们从用尾插法的形式来建设单链表 */ public class SingleLinkedList { private Node head; /** * 结点数量 */ private int size; private class Node{ private int data; private Node next; public Node(int data, Node next) { this.data = data; this.next = next; } public Node(int data) {this(data,null); } @Override public String toString() { return "Node{" + "data=" + data + '}'; } } public SingleLinkedList(int data) {head = new Node(data,null); size++; } /** * 间接增加在开端 */ public void add(int data){ Node lastNode = head; while (lastNode.next != null){lastNode = lastNode.next;} Node newNode = new Node(data); lastNode.next = newNode; size++; } /** * 查看地位是否非法, 咱们将其形象进去做成一个办法 * @param index */ public void checkPosition(int index){if (index < 0 || index >= size){throw new RuntimeException("下标越界"); } } /** * 单链表的插入, 咱们只须要将插入地位的元素的 next 指向要增加元素，要增加的元素的 next 指向插入地位原先的 next * @param data * @param index */ public void add(int data, int index){checkPosition(index); Node indexNode = get(index); Node afterNode = indexNode.next; Node insertNode = new Node(data,afterNode); indexNode.next = insertNode; size++; } /** * 按数据查找 * @param data * @return */ public int indexOf(int data){ Node indexNode = head; int index = - 1; while (indexNode.data != data){ indexNode = indexNode.next; index++; } return index; } /** * 按下标查找 * @param index * @return */ public Node get(int index){checkPosition(index); Node indexNode = head; for (int i = 0; i < index; i++) {indexNode = indexNode.next;} return indexNode; } /** * 如果是队尾间接移除即可 * 如果是两头, 移除地位的前一个地位和后一个地位相连即可 * @param index */ public void remove(int index){checkPosition(index); // 获取须要移除地位的前一个结点 // 即移除头结点, 那么头结点的下一个结点称为头结点 if (index == 0){ head = head.next; return; } Node indexNode = get(index - 1); Node afterNode = indexNode.next.next; indexNode.next = afterNode; } }
接下来咱们来剖析一下查找，删除，插入的复杂度。这些都跟地位有关系，以查找为例，假如查找的元素刚好处于头结点，那只须要一次查找就能够了。
| 查找地位 | 0 | 1 | 2 | n |
|---|---|---|---|---|
| 查找次数 | 0 | 1 | 2 | n |
| 概率 | 1/n | 1/n | 1/n | 1/n |
各个地位的查找次数乘以对应概率累加即为均匀查找次数，最 (n(n+1)/2) * (1 / n), 工夫复杂度为 O(n).
删除和查找类似工夫次要都花在查找上了，因而工夫复杂度也为 O(n)
绝对于单向链表，循环链表的最初一个结点指向头结点，这是循环链表与单向链表不同的一点。
双向链表
在程序表中咱们总是能够依据下标能够很不便的找到表元素的前驱和后继，但单链表只能找后继，若须要对某个结点的间接前驱进行操作，则必须从头结点找起。因为单链表的结点只记录了后继结点的地位，而没有前驱结点的信息。那么能不能在其结点构造中减少记录前驱接地的数据项呢？当然是能够的，基于这种思维设计进去的，咱们就称之为双向链表。
/**
* @author XingKe
* @date 2021-07-31 12:36
*/
public class DoubleLinkedList {
private Node head;
// 指向第一个元素
private Node last;
private int size;
private class Node{
private Node before;
private int data;
private Node next;
public Node(int data, Node next, Node before) {
this.data = data;
this.next = next;
}
public Node(int data) {this(data,null, null);
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}
public DoubleLinkedList(int data) {Node node = new Node(1);
head = node;
last = node;
size = 0;
size++;
}
public void add(int data){last.next = new Node(data,null,last);
size++;
}
public void add(int data,int index){
// 定位该下标的地位
Node indexNode = node(index);
size++;
}
public void checkPosition(int index){if (index < 0 || index >= size){throw new RuntimeException("下标越界");
}
}
// 有了前驱结点, 咱们就不用从头找到尾了, 咱们能够依据下标判断
// 如果比拟靠厚咱们就从最初一个结点找, 如果比拟靠前咱们就从头结点开始找
// index < size / 2 那阐明比拟靠前, 咱们从头遍历,
// 如果 index > size / 2 , 那阐明比拟靠后, 咱们就从后往前找即可。// 咱们最多只须要查找一半的次数就能够了
private Node node(int index) {checkPosition(index);
if (index < size / 2){
Node indexNode = head;
for (int i = 0; i < index ; i++) {indexNode = head.next;}
return indexNode;
}else{
Node indexNode = last;
for (int i = size ; i > index ; i--) {indexNode = indexNode.before;}
return indexNode;
}
}
}删除和增加的操作也都花在查找元素上，咱们这里剖析一下查找的工夫复杂度:
| 查找地位 | 0 | 1 | 2 | index – 1 |
|---|---|---|---|---|
| 查找次数 | 0 | 1 | 2 | index – 1 |
| 概率 | 1/n | 1/n | 1/n | 1/n |
绝对单链表来是咱们能够直观的感触到双向链表最差只用查找一半的范畴就能够了，index 越向两头靠，查找的次数越多.
查找的工夫复杂度为 O(n)，这里可能有同学会问了，这不跟单链表差不多了吗？留神这个是渐进上界, n /2 和 n/4 都小于 n，咱们能够了解为这个 n 就是大 O 符号标记的，迫近的不够紧凑，咱们示意的工夫复杂度的时候能够选取尽量紧凑的上界，如果上界选的过大，那么就可能违反知觉。这个式子累加起来较为紧凑的上界为 O(n/4), 而单链表的查找速度为 O(n/2).
设计一种数据结构，咱们要想的灵便一点，思考如何基于原有的数据结构进行增强，我参考的书籍所结构的双向链表只有一个头结点，然而我参考了 Java 中的 LinkedList(JDK 官网实现的双向链表)，然而为了寻址不便这里又减少了 size 和 last。所以在设计数据结构的时候，也能够参考所应用的高级语言的类库。
总结一下
本篇属于《数据结构与算法剖析系列》中的一篇，算是重修数据结构与算法剖析了。这原本是将近一章的内容，我并入一篇文章里，大略写了将近两个周末，当前尽量麻利一点，做到不沉积太多内容。
