常见的线性结构
- 2020 年 3 月 29 日
- 筆記
目录
前言
本篇博客主要是记录手写这些这数据结构的底层实现，加深对线性结构的理解，实现自己的一个小型数据结构库，也会进行简单的时间复杂度分析，对不同的实现进行比较和优化，即侧重于代码实现。由于数据结构是实践性比较强的一个科目，希望大家在看这篇博客时，自己也去写一下代码，看一下运行结果是不是自己想要的，我也会贴出我的运行结果来进行分析。
数组
数组介绍
数组是在内存中存储相同数据类型的连续的空间，最大的优点：查询快速。
数组最好应用于“索引有语意”的情况，例如索引代表学生学号，我们可以根据学号获取这个学生对象的信息。但并非所有有语意的索引都适用于数组，例如身份证号，我们不可能拿身份证号作为索引，因为身份证长度是18位数，而且身份证号也不是连续的，这样会浪费很大的内存空间。
数组也可以处理“索引没有语意”的情况，若索引没有语意时，如何表示没有元素？我们应该如何去添加元素、如何去删除元素呢？为了解决这些问题，我们可以基于Java的数组，二次封装属于我们自己的数组。
自定义数组
我们通过创建一个自定义数组，来实现对数组的增删改查，以及数组进行扩容，现在我们先通过定义一个整型数组来实现，后面再通过泛型来达到通用的效果。
1.先创建一个实体类：Array
public class Array { private int[] data; private int size; } 2.为我们的数组添加一些基本的方法，比如构造器、获取数组容量大小、获取数组中元素个数、判断数组是否为空、判断是否包含某个元素的方法
//有参构造--- 根据用户分配的初始容量进行创建数组 public Array(int capacity){ data = new int[capacity]; size = 0; } //创建无参构造 --- 当用户未指定初始容量时，我们可以设置一个初始容量大小 public Array(){ this(10); } //创建一个获取容量大小的方法 public int getCapacity(){ return data.length; } //创建一个获取数组中元素个数的方法 public int getSize(){ return size; } //判断数组是否为空 public boolean isEmpty(){ return size == 0; } //是否包含某个元素 public boolean contains(int e) { for(int i = 0; i < this.size; ++i) { if (this.data[i] == e) { return true; } } return false; } 实现数组的增删改查方法
1.向数组中添加元素
在指定索引位置添加一个新元素
// 在指定索引的位置插入一个新元素e public void add(int index, int e){ //判断索引是否合法 if(index < 0 || index > size){ throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size."); } //判断数组是否已满 if(size == data.length){ throw new IllegalArgumentException("Add failed. Array is full."); } //把索引为index以及index之后的元素，都向右移动一个位置 for(int i = size - 1; i >= index ; i --){ data[i + 1] = data[i]; } //在指定index的位置添加新元素e data[index] = e; //维护size的值 size ++; } 在所有元素前添加一个新元素
// 在所有元素前添加一个新元素 public void addFirst(int e){ add(0, e); } 在所有元素后添加一个新元素
// 在所有元素前添加一个新元素 public void addLast(int e){ add(size, e); } 2.修改数组中的元素
通过索引修改数组中的元素
public void set(int index, int e){ if(index < 0 || index >= size) throw new IllegalArgumentException("Set failed. Index is illegal."); //由于数组支持随机访问，根据索引即可找到所需要修改的元素 data[index] = e; } 3.查找元素
通过index索引，获取元素
public int get(int index){ //判断用户输入的索引值是否合法 if(index < 0 || index >= size) throw new IllegalArgumentException("Get failed. Index is illegal."); return data[index]; } 查找某个元素的索引
public int find(int e) { for(int i = 0; i < this.size; ++i) { if (this.data[i] == e) { return i; } } //未找到该元素，则返回-1 return -1; } 4.删除元素
删除指定位置的元素,并返回删除的元素
// 从数组中删除index位置的元素, 返回删除的元素 public int remove(int index){ //索引合法性判断 if(index < 0 || index >= size) throw new IllegalArgumentException("Remove failed. Index is illegal."); //保存待删除的元素 int ret = data[index]; //把index位置之后的所有元素，都向左移动一个位置 for(int i = index + 1 ; i < size ; i ++) data[i - 1] = data[i]; //维护size的值 size --; return ret; } - 删除第一个元素
// 从数组中删除第一个元素, 返回删除的元素 public int removeFirst(){ return remove(0); } 删除最后一个元素
public int removeLast(){ return remove(size - 1); } 删除数组中的指定元素
// 从数组中删除元素e public void removeElement(int e){ int index = find(e); if(index != -1) remove(index); } 5.重写toString()
@Override public String toString(){ //通过StringBuilderl来拼接字符串 StringBuilder res = new StringBuilder(); //自定义输出格式 res.append(String.format("Array: size = %d , capacity = %dn", size, data.length)); res.append('['); for(int i = 0 ; i < size ; i ++){ res.append(data[i]); if(i != size - 1) res.append(", "); } res.append(']'); return res.toString(); } 对我们数组的增删改查方法进行测试,我们可以在主函数中进行测试：
public static void main(String[] args) { Array arr = new Array(20); for(int i = 0 ; i < 10 ; i ++){ //执行添加元素操作 --- 新增到元素末尾 arr.addLast(i); } System.out.println(arr);// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] //将新元素插入到指定位置 arr.add(1, 100); System.out.println(arr);// [0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9] //将新元素添加到第一个位置 arr.addFirst(-1); System.out.println(arr);// [-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9] //删除指定位置的元素 arr.remove(2); System.out.println(arr);// [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9] //删除指定元素 arr.removeElement(4); System.out.println(arr);// [-1, 0, 1, 2, 3, 5, 6, 7, 8, 9] //删除第一个位置的元素 arr.removeFirst(); System.out.println(arr);// [0, 1, 2, 3, 5, 6, 7, 8, 9] } 经测试，我们自定义数组的增删改查等基本操作已经实现了，不过我们现在写的自定义数组，只能存储整型数据，为了适用性更好，我们可以把我们的自定义数组改为泛型，如下：
public class Array<E> { private E[] data; private int size; public Array(int capacity){ //无法定义为new E[capacity] ,使因为jdk1.5之后才支持泛型的，由于历史版本遗留问题 // 这里只能进行强转 this.data = (E[]) new Object[capacity]; this.size = 0; } //创建无参构造 --- 当用户未指定初始容量时，我们可以设置一个初始容量大小 public Array(){ this(10); } //创建一个获取容量大小的方法 public int getCapacity(){ return this.data.length; } //创建一个获取数组中元素个数的方法 public int getSize() { return this.size; } //判断数组是否为空 public boolean isEmpty() { return this.size == 0; } // 向所有元素后添加一个新元素 public void addLast(E e){ // //判断数组中是否还有空位置 // if (size == data.length) { // throw new IllegalArgumentException("AddLast failed. Array is full."); // } // //因为size始终表示数组中元素为空的第一个索引 // data[size] = e; // //添加元素后，需要改变size的值 // size++; add(size,e); } //在所有元素前添加一个新元素 --- 将新元素添加到索引为0的位置 public void addFirst(E e){ // //判断数组中是否还有空位置 // if (size == data.length) { // throw new IllegalArgumentException("AddLast failed. Array is full."); // } // //需要将所有元素向后移一个位置，然后把新元素加入到索引为0的位置 // for(int i = size - 1; i >= 0 ; i --){ // //向后赋值 // data[i + 1] = data[i]; // } // data[0] = e; // size ++; add(0,e); } // 在指定索引的位置插入一个新元素e public void add(int index, E e){ if(size == data.length){ throw new IllegalArgumentException("Add failed. Array is full."); } if(index < 0 || index > size){ throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size."); } for(int i = size - 1; i >= index ; i --){ data[i + 1] = data[i]; } data[index] = e; size ++; } // 获取index索引位置的元素 public E get(int index){ //判断用户输入的索引值是否合法 if(index < 0 || index >= size) throw new IllegalArgumentException("Get failed. Index is illegal."); return data[index]; } //查找某个元素的索引 public int find(E e) { for(int i = 0; i < this.size; ++i) { if (this.data[i] == e) { return i; } } return -1; } // 修改index索引位置的元素为e public void set(int index, E e){ if(index < 0 || index >= size) throw new IllegalArgumentException("Set failed. Index is illegal."); data[index] = e; } //是否包含某个元素 public boolean contains(E e) { for(int i = 0; i < this.size; ++i) { if (this.data[i] == e) { return true; } } return false; } //删除指定位置的元素 public void remove(int index) { //索引合法性判断 if (index >= 0 && index < this.size) { for(int i = index + 1; i < this.size; ++i) { //向前赋值 this.data[i - 1] = this.data[i]; } //删除元素后，修改size的值 --this.size; } else { throw new IllegalArgumentException("Remove failed. Index is illegal."); } } //删除第一个元素 public void removeFirst() { this.remove(0); } //删除最后一个元素 public void removeLast() { this.remove(this.size - 1); } //删除数组中的指定元素 public void removeElement(E e) { //先查找指定元素所在的索引位置 int index = this.find(e); //删除指定索引位置的元素 this.remove(index); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Array: size = %d , capacity = %dn", size, data.length)); res.append('['); for(int i = 0 ; i < size ; i ++){ res.append(data[i]); if(i != size - 1) res.append(", "); } res.append(']'); return res.toString(); } } 修改为泛型之后，我们可以通过自定义一个学生类，来使用我们的自定义数组进行增删查改操作，测试是否有问题：
public class Student { private String name; private int score; public Student(String studentName, int studentScore) { this.name = studentName; this.score = studentScore; } public String toString() { return String.format("Student(name: %s, score: %d)", this.name, this.score); } public static void main(String[] args) { Array arr = new Array(); //执行添加元素操作 --- 新增到元素末尾 arr.addLast(new Student("Lucy", 100)); arr.addLast(new Student("Bob", 66)); arr.addLast(new Student("Tina", 88)); System.out.println(arr); //删除指定位置的元素 arr.remove(2); System.out.println(arr); //将新元素插入到指定位置 arr.add(1,new Student("LiHua", 75)); System.out.println(arr); } } 动态数组
当数组中的元素存满时，再执行添加操作，这个时候会抛出数组元素已满的异常信息，我们希望我们的自定义数组可以进行动态扩容，我们可以通过写一个重置数组容量的方法，这个方法只允许在数组类内部调用，不允许用户直接调用，所以需要设置成私有的。
//将数组空间的容量变成newCapacity大小 private void resize(int newCapacity){ E[] newData = (E[]) new Object[newCapacity]; for (int i=0;i<size;i++){ newData[i] = data[i]; } data = newData; } 写好了resize()后，现在让我们来重写之前的添加和删除方法：
添加操作：为了防止在添加的时候，抛出数组已满的异常，我们可以在向数组中添加元素的时候，判断数组受否已满，若满了，则进行扩容操作，这里我们扩容为原来的2倍
public void add(int index, E e){ if(index < 0 || index > size){ throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size."); } if(size == data.length){ //throw new IllegalArgumentException("Add failed. Array is full."); //若数组满了，则进行扩容操作 this.resize(data.length * 2); } for(int i = size - 1; i >= index ; i --){ data[i + 1] = data[i]; } data[index] = e; size ++; } 删除操作：为了不浪费内存，在删除元素时，我们可以判断数组中元素的个数是否是数组容量的一半，若是的话，这个时候就对数组进行缩容操作，以达到节省内存的目的
// 从数组中删除index位置的元素, 返回删除的元素 public E remove(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("Remove failed. Index is illegal."); E ret = data[index]; for(int i = index + 1 ; i < size ; i ++) data[i - 1] = data[i]; size --; data[size] = null; // 方便GC机制回收 //当数组的元素个数为数组长度的一半时，进行缩容操作 if(size == data.length / 2) resize(data.length / 2); return ret; } 现在我们来测试我们的扩容和缩容方法：
public static void main(String[] args) { Array<Integer> arr = new Array<>(); for(int i = 0 ; i < 10 ; i ++) arr.addLast(i); System.out.println(arr); arr.add(1, 100); System.out.println(arr); arr.addFirst(-1); System.out.println(arr); arr.remove(2); System.out.println(arr); arr.removeElement(4); System.out.println(arr); arr.removeFirst(); System.out.println(arr); } 运行结果分析：
时间复杂度分析
常见的算法复杂度：O(1),O(n),O(lgn),O(nlgn),O(n^2)
大O描述的是算法的运行时间和输入数据之间的关系
例如下面这段代码：
public static int sum(int[] nums){ int sum = 0; for (int num : nums) { sum = sum + num; } return sum; } 这段代码的算法复杂度为O（n）。n是nums中的元素个数，这个算法的运行时间是和nums中元素的个数呈线性关系的。好了，上面是关于算法复杂度的简单描述，我们来看下我们自定义数组中添加操作的算法复杂度吧：
- 添加操作：由于算法复杂度是按照最坏的情况来计算的，所以这里添加的算法复杂度为O（n）
addLast(e) ——– O(1)
addFirst(e) ——— O(n),因为向数组中第一个元素位置添加元素，需要将这些元素都向右移动一个位置，这和元素的个数呈线性关系，若数组中元素的个数越多，组需要花费的时间越长
add(index,e) —– O(n/2) =O(n) - 删除操作同添加操作，算法复杂度为O（n）
- 修改操作的算法复杂度为O（1），这个是数组的最大优势，也就是支持随机访问，只要我们知道所查元素的索引。
- 查找操作：get(index) — O(1) ,contains(e)和find(e)的时间复杂度都为O（n）,因为需要遍历这个数据中的所有元素。
栈
栈介绍
栈也是一种线性结构，相比数组，栈对应的操作是数组的子集。栈只能从一端添加元素，也只能从这端取出元素，这一端成为栈顶,栈是一种“先进后出”的数据结构，即 LIFO(Last In First Out)
一些常见的栈应用：比如：撤销操作，程序调用的系统栈，括号匹配等问题。
栈中常用的方法：
void push(Object obj); //进栈
Object pop(); //出栈
Object peek(); //查看栈顶的元素
int getSize(); //查看栈中元素的个数
boolean isEmpty(); //判断栈是否为空
定义栈接口
由于用户在调用栈进行操作时，完全不用关心栈的底层是如何实现的，因此我们可以定义一个 接口来供用户调用，下面就让我们基于之前实现的自定义动态数组，来实现栈的这些基本操作：
public interface Stack<E> { /** * 获取栈中元素的个数 * @return */ int getSize(); /** * 判断栈是否为空 * @return */ boolean isEmpty(); /** * 入栈 * @param e */ void push(E e); /** * 出栈 * @return */ E pop(); /** * 查看栈顶元素 * @return */ E peek(); } 基于数组实现栈的基本操作
public class ArrayStack<E> implements Stack<E> { //这里的Array是我们的自定义动态数组 private Array<E> array; //有参构造器，为栈分配指定空间 public ArrayStack(int capacity) { this.array = new Array(capacity); } //无参构造器，调用动态数组的无参构造进行赋值 public ArrayStack(){ this.array = new Array<>(); } //获取栈的容量 public int getCapacity() { return this.array.getCapacity(); } @Override public int getSize() { //直接调用动态数组的getSize() return this.array.getSize(); } @Override public boolean isEmpty() { return this.array.isEmpty(); } @Override public void push(E e) { //向栈中添加元素，调用动态数组的向最后一个元素位置的添加方法 this.array.addLast(e); } @Override public E pop() { //获取栈顶的元素，即动态数组的最后一个元素 E e = this.array.get(array.getSize() - 1); //删除动态数组中最后一个元素 this.array.removeLast(); return e; } @Override public E peek() { return this.array.get(array.getSize() - 1); } //重写toString() @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Stack: "); res.append('['); for (int i=0; i<this.getSize(); i++){ res.append(this.array.get(i)); if (i != this.getSize()-1 ){ res.append(','); } } res.append("] top"); return res.toString(); } } 现在来测试我们基于动态数组实现的栈：
public static void main(String[] args) { Stack<Integer> stack = new ArrayStack(); for(int i = 0; i < 5; ++i) { //入栈 stack.push(i); System.out.println(stack); } //出栈 stack.pop(); System.out.println(stack); //打印出栈顶的元素 System.out.println(stack.peek()); } 测试代码的运行结果分析：
使用栈实现“括号匹配”问题
该问题是leetcode官网上的一个问题，题目描述如图：
关于括号匹配问题，具体实现如下：
public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (int i=0; i<s.length(); i++){ if (s.charAt(i) != '(' && s.charAt(i) != '[' && s.charAt(i) != '{'){ if (stack.isEmpty()) return false; char topChar = stack.pop(); if (topChar == '(' && s.charAt(i) != ')') return false; if (topChar == '[' && s.charAt(i) != ']') return false; if (topChar == '{' && s.charAt(i) != '}') return false; }else { stack.push(s.charAt(i)); } } return stack.isEmpty(); } 队列
队列介绍
队列也是一种线性结构，相比数组，队列对应的操作是数组的子集，队列只能从一端（队尾）添加元素，只能从另一端（队首）取出元素。队列是一种先进先出的数据结构（先到先得），即FIFO(First In First Out).
队列中常用的操作：
- void enqueue(Object obj); //入队
- Object dequeue(); //出队
- Object getFront(); //获取队首的元素
- int getSize(); //获取队列中元素的个数
- boolean isEmpty(); //判断队列是否为空
定义队列接口
和栈操作一样，我们不需要让用户知道队列底层是如何实现的，只知道如何调用就行了，所以我们创建一个接口，包含这些队列的基本方法：
public interface Queue<E> { /** * 入队 * @param e 入队的元素 */ void enqueue(E e); /** * 出队 * @return 出队的元素 */ E dequeue(); /** * 获取队首的元素 * @return 队首的元素 */ E getFront(); /** * 判断队列是否为空 * @return */ boolean isEmpty(); /** * 获取队列中的元素 * @return */ int getSize(); } 数组队列
有了队列接口后，我们现在来通过自定义的动态数组实现队列的基本操作：
public class ArrayQueue<E> implements Queue<E>{ private Array<E> array; //有参构造 --- 用户可以自定义队列的大小 public ArrayQueue(int capacity) { this.array = new Array<E>(capacity); } //无参构造 public ArrayQueue(){ array = new Array<E>(); } //入队操作 -- 相当于向动态数组末尾添加元素 @Override public void enqueue(E e) { array.addLast(e); } //出队操作 --- 相当于删除动态数组的第一个元素 @Override public E dequeue() { return array.removeFirst(); } //获取队首的元素 @Override public E getFront() { return array.getFirst(); } //判断队列是否未空 @Override public boolean isEmpty() { return array.isEmpty(); } //返回队列中元素的个数 @Override public int getSize() { return array.getSize(); } //获取队列的容量大小 public int getCapacity(){ return array.getCapacity(); } //重写toString() --- 自定义输出格式 @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append("Queue: "); //队列 builder.append("front["); //队首 for (int i=0; i<array.getSize(); i++){ builder.append(array.get(i)); //如果不是最后一个元素，则在元素后面追加',' if (i != array.getSize()-1 ){ builder.append(","); } } builder.append("]trail"); //队尾 return builder.toString(); } } 数组队列测试，我们可以住方法中写我们的测试代码：
public static void main(String[] args) { ArrayQueue<Integer> queue = new ArrayQueue<>(); for(int i = 0 ; i < 10 ; i ++){ queue.enqueue(i); System.out.println(queue); //当余数为2时，就从队列中删除一个元素 if(i % 3 == 2){ queue.dequeue(); System.out.println(queue); } } } 测试代码的运行结果分析如下：
数组队列的时间复杂度分析：
入队：由于是向数组中最后一个元素末尾添加元素，不需要关心数组中元素的个数，所以时间复杂度为O(1);
出队：由于出队操作，我们始终是删除的数组第一个元素，实际上是将待删除的元素之后的所有元素都想前移动一个位置，所以出队操作执行的时间与数组的中元素的个数呈线性关系，时间复杂度为O(n).
循环队列
由于数组队列的出队操作的时间复杂度为O(n),效率是比较低的，为了提升程序性能，降低时间复杂度，让出队操作的时间复杂度也是O(1)，我们引入了循环队列。
循环队列的实现思路：
我们可以使用Java给我们提供的数组来表示队列，并且定义两个变量，一个变量（front）用来表示队首元素所在的索引，另一个变量（tail）表示队尾待添加元素的索引，这样在入队时，直接将元素天添加到队尾位置就可以了，即索引为trail的位置；在进行出队操作时，我们也可以通过front索引来获取队首元素，并进行删除，这样就可以实现队列的入队和出队操作的时间复杂度都为O(1)了。同时为了节约空间内存，删除元素后，释放的空间，我们在添加新的元素时，是可以放在这些位置上的，就像一个环一样，不过要留出一个空位置，用来表示这个队列为空，即当front == tai时表示为空。
代码实现如下：
public class LoopQueue<E> implements Queue<E> { //注意这里的data类型为E[]，并不是Array private E[] data; //队首元素的索引 private int front; //队尾待添加元素的索引 private int tail; //队列中元素的个数 private int size; //有参构造 public LoopQueue(int capacity){ //这里要比用户分配的空间多1，是为了处理循环队列为空和已满的问题 this.data = (E[])new Object[capacity+1]; this.front = 0; this.tail = 0; this.size = 0; } //无参构造 public LoopQueue(){ this(10); } //判断队列是否未空 @Override public boolean isEmpty() { return this.front == this.tail; } //获取队列中元素的个数 @Override public int getSize() { return this.size; } //获取队列的容量 public int getCapacity() { //这这里需要减去1，因为这一个空间是辅助我们去实现循环队列入队出队操作的 return this.data.length - 1; } //获取队首的元素 @Override public E getFront() { //判断队列是否为空 if (this.isEmpty()){ throw new IllegalArgumentException("Queue is empty."); } return this.data[this.front]; } //入队操作 @Override public void enqueue(E e) { //判断队列是否已满 if ((this.tail+1) % this.data.length == this.front){ //若满了，则对该队列进行扩容 this.resize(getCapacity() * 2); } //将该元素加入队尾 this.data[this.tail] = e; //修改tail的值 -- 需要考虑到tail的值是(data.length-1)时 this.tail = (this.tail+1) % data.length; //修改size的值 this.size ++ ; } //出队操作 @Override public E dequeue() { //判断队列是否为空 if (this.isEmpty()){ throw new IllegalArgumentException("Cannot dequeue from an empty queue."); }else { //获取队首的元素 E e = this.data[this.front]; //修改front的值 this.front = (this.front + 1) % this.data.length; //修改size的值 --this.size; //为了节约空间，当队列中的元素为当前队列的1/4时，进行缩容 //要保证空间缩容为原来的1/2时，容量不为0 if (this.size == this.getCapacity() / 4 && this.getCapacity() / 2 != 0){ this.resize(this.getCapacity()/2); } return e; } } //修改队列的空间大小 private void resize(int capacity){ //创建一个新数组 E[] newData = (E[])(new Object[capacity+1]); //把原队列中的值放入新数组中 for (int i=0; i<this.size; i++){ //注意：要保持队列的数据结构特性,即需要保持数据的先进先出的数据格式 //注意超出数组长度的情况 -- 通过对数组长度取余数来避免 newData[i] = this.data[(i + this.front) % this.data.length ]; } this.data = newData; this.front = 0; this.tail = this.size; } //重写toString() --- 自定义我们的输出格式 @Override public String toString() { StringBuilder builder = new StringBuilder(); //获取当前 队列的元素个数和容量大小 builder.append(String.format("Queue：size=%d, capacity=%dn ",this.getSize(),this.getCapacity())); //队首 builder.append("front ["); //取余数是为了防止下标越界 for (int i = this.front;i != this.tail;i = (i+1)%this.data.length){ builder.append(this.data[i]); if ((i+1) % this.data.length != tail){ builder.append(","); } } builder.append("] tail"); return builder.toString(); } } 我们在主方法中写我们的测试代码：
public static void main(String[] args) { Queue<Integer> queue = new LoopQueue(); for(int i = 0; i < 10; ++i) { queue.enqueue(i); System.out.println(queue); if (i % 3 == 2) { queue.dequeue(); System.out.println(queue); } } } 测试代码的运行结果分析：
数组队列和循环队列的性能比较
现在循环队列就已经实现了，前面说到循环队列的入队和出队操作的时间复杂度都为O(1)，而数组队列的出队操作的时间复杂度为O(n)，现在让我们来简单设计一个程序， 来比较数组队列和循环队列进行入队操作和出队操作所需要的时间吧。
public class QueueCompare { //测试队列进行入队和出队操作所花费的时间 public static Long testQueue(Queue<Integer> queue,int num){ //获取系统的当前时间 --- 毫秒 long startTime = System.currentTimeMillis(); Random random = new Random(); int i; for (i=0; i<num; i++){ //在队列中添加一个整数范围内的随机数 queue.enqueue(random.nextInt(Integer.MAX_VALUE)); } for (i=0; i<num; i++){ //出队操作 queue.dequeue(); } //获取进行入队和出队操作后的当前时间 --- 毫秒 long endTime = System.currentTimeMillis(); return endTime-startTime; } public static void main(String[] args) { //比较10万个整数的入队和出队操作所花费的时间 int num = 100000; //数组队列耗时 Queue<Integer> arrayQueue = new ArrayQueue<>(); Long time1 = testQueue(arrayQueue, num); System.out.println("ArrayQueue, time: " + time1 + " ms"); //循环队列耗时 Queue<Integer> loopQueue = new LoopQueue<>(); Long time2 = testQueue(loopQueue, num); System.out.println("loopQueue, time: " + time2 + " ms"); } } 在我这台电脑上的运行结果如下：
我们可以从结果中看到，运行结果差距还是很大的，所以这也体现了算法的重要性，以及O（n）和O（1）的区别。
链表：最基础的动态数据结构
链表介绍
链表也是一种线性结构，但与数组、栈和队列不同的是，链表是一种动态数据结构。虽然 我们创建的动态的数组也能进行扩容操作，但底层是依赖于静态数组的，其实质还是静态数据结构。
为什么链表很重要？
1.链表是真正的动态数据结构，也是最简单的动态数据结构
2.链表可以帮助我们更深入的理解引用（即C语言种的指针）
3.帮助我们更深入的理解递归
4.辅助组成其他的数据结构
链表数据存储在“节点”中（Node）中，其优点是真正的动态，不需要处理固定容量的问题，但缺点正是数组的优点，就是丧失了随机访问能力。数组最好用于索引有语意的情况，它最大的优点是支持快速查询，即支持随机访问；而链表不适合用于索引有语意的情况，它最大的有点是动态的。
链表的最基本元素是节点，现在让我们自己手动来写一个最简单的链表类：
public class LinkedList<E> { //链表的头结点 private Node head; //链表的长度 private int size; //以为链表是动态的数据结构，所以不需要分配容量 public LinkedList(){ this.head = null; this.size = 0; } // 获取链表中元素的个数 public int getSize(){ return this.size; } // 返回链表是否为空 public boolean isEmpty(){ return size == 0; } //设置成为内部类，是为了对用户屏蔽链表的内部实现 private class Node{ //存储这个节点的数据 public E e; //指向下一个节点的引用 public Node next; public Node(E e, Node next) { this.e = e; this.next = next; } public Node(E e){ this(e, null); } public Node(){ this(null, null); } //我们只需要输出这个节点的数据信息 @Override public String toString() { return e.toString(); } } } 实现链表的增删改查操作
在自己手写链表底层实现的时候，有不用懂得最好用笔和纸，把这些节点的指向关系画出来，因为图形化的才是最直观的，也能帮助我们更好的理解。
1.向链表中添加元素
// 在链表头添加新元素 public void addFirst(E e){ // Node node = new Node(e); // node.next = head; // head = node; //上面三行代码可以合并成一行代码 head = new Node(e, head); size ++; } // 在链表的index(0-based)位置添加新元素e // 在链表中index并不是一个常用的操作，因为链表不支持随机访问 public void add(int index,E e){ //判断index是否合法 //注意：与数组不同的是，链表这里的index是可以等于size的，此时表示在链表末尾添加元素 if (index <0 || index > size){ throw new IllegalArgumentException("Add failed. Illegal index."); } //判断是否是向头节点中添加元素 if (index == 0){ this.addFirst(e); }else { Node prev = head; for (int i = 0;i< index-1 ;i++){ prev = prev.next; } // Node node = new Node(e); // node.next = prev.next; // prev.next = node; //上面三行代码可以合并成一行代码 prev.next = new Node(e,prev.next); size ++ ; } } //在链表末尾添加元素 public void addLast(E e){ this.add(size,e); } 下面我们也可以通过为链表添加一个虚拟的头结点，来实现链表的添加方法，就不用对头结点进行单独处理，如下：
//设置虚拟头结点 private Node dummyHead; private int size; public LinkedList() { //虚拟头结点不存数据，始终为空 this.dummyHead = new Node(); this.size = 0; } // 获取链表中的元素个数 public int getSize(){ return size; } // 返回链表是否为空 public boolean isEmpty(){ return size == 0; } // 在链表的index(0-based)位置添加新的元素e // 在链表中不是一个常用的操作，练习用：） public void add(int index,E e){ //判断索引是否合法 if (index<0 || index > size){ throw new IllegalArgumentException("Add failed. Illegal index."); } Node prev = dummyHead; for (int i=0; i<index; i++){ prev = prev.next; } prev.next = new Node(e,prev.next); size ++ ; } // 在链表头添加新的元素e public void addFirst(E e){ this.add(0,e); } // 在链表末尾添加新的元素e public void addLast(E e){ this.add(size,e); } 2.修改元素：下面我们使用为为链表添加一个虚拟头结点的方式，来进行修改链表中的元素
// 获得链表的第index(0-based)个位置的元素 public E get(int index){ //这里把index=size也排除是因为最后一个节点所指向的节点为空 if (index < 0 || index >= size){ throw new IllegalArgumentException("Get failed. Illegal index."); } Node curr = dummyHead.next; for (int i=0; i<index; i++){ curr = curr.next; } return curr.e; } // 获得链表的第一个元素 public E getFirst(){ return get(0); } // 获得链表的最后一个元素 public E getLast(){ return get(size - 1); } // 查找链表中是否有元素e public boolean contains(E e){ Node curr = dummyHead.next; while (curr != null){ if (curr.e.equals(e)) return true; curr = curr.next; } return false; } 修改链表中的指定位置的元素
// 修改链表的第index(0-based)个位置的元素为e public void set(int index,E e){ if (index < 0 || index >= size){ throw new IllegalArgumentException("Get failed. Illegal index."); } Node curr = dummyHead.next; for (int i=0; i<index; i++){ curr = curr.next; } curr.e = e; } 3.删除元素
// 从链表中删除index(0-based)位置的元素, 返回删除的元素 public E remove(int index){ if (index < 0 || index >= size){ throw new IllegalArgumentException("remove failed. Illegal index."); } Node prev = dummyHead; for (int i=0; i<index; i++){ prev = prev.next; } //待删除的元素 Node delNode = prev.next; prev.next = delNode.next; //方便GC机制回收 delNode.next = null; size -- ; return delNode.e; } // 从链表中删除第一个元素, 返回删除的元素 public E removeFirst(){ return this.remove(0); } // 从链表中删除最后一个元素, 返回删除的元素 public E removeLast(){ return this.remove(size-1); } // 从链表中删除元素e public void removeElement(E e){ Node prev = dummyHead; while ( prev.next != null ){ //如果找到被删除的元素，就跳出循环 if (prev.next.e.equals(e)) break; prev = prev.next; } if (prev.next != null){ Node delNode = prev.next; prev.next = delNode.next; delNode.next = null; size -- ; } } 重写我们自定义链表的toString()
@Override public String toString(){ StringBuilder res = new StringBuilder(); Node cur = dummyHead.next; while(cur != null){ res.append(cur + "->"); cur = cur.next; } res.append("NULL"); return res.toString(); } 对自定义链表的增删改查方法进行测试：
public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); for(int i = 0 ; i < 5 ; i ++){ linkedList.addFirst(i); System.out.println(linkedList); } linkedList.add(2, 666); System.out.println(linkedList); linkedList.remove(2); System.out.println(linkedList); linkedList.removeFirst(); System.out.println(linkedList); linkedList.removeLast(); System.out.println(linkedList); } 测试代码的运行结果如下：
通过自定义链表实现栈
public class LinkedStack<E> implements Stack<E> { //基于自定义链表实现栈结构 private LinkedList<E> linkedList = new LinkedList<>(); @Override public int getSize() { return this.linkedList.getSize(); } @Override public boolean isEmpty() { return this.linkedList.isEmpty(); } @Override public void push(E e) { this.linkedList.addFirst(e); } @Override public E pop() { return this.linkedList.removeFirst(); } @Override public E peek() { return this.linkedList.getFirst(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Stack: top "); res.append(this.linkedList); return res.toString(); } //测试自定义栈 public static void main(String[] args) { LinkedListStack<Integer> stack = new LinkedListStack(); for(int i = 0; i < 5; ++i) { stack.push(i); System.out.println(stack); } stack.pop(); System.out.println(stack); } } 通过自定义链表实现队列
public class LinkedListQueue<E> implements Queue<E> { //head指向头结点,tail指向下次添加元素的位置 private Node head, tail; private int size; //不写也可以，和系统自动生成的无参构造器作用效果相同 public LinkedListQueue(){ head = null; tail = null; size = 0; } //入队 -- 只能从队尾添加元素 @Override public void enqueue(E e) { if (tail == null){ tail = new Node(e); head = tail; }else { tail.next = new Node(e); tail = tail.next; } size ++ ; } //出队操作 -- 只能从队首删除元素 @Override public E dequeue() { if (isEmpty()) { throw new IllegalArgumentException("Cannot dequeue from an empty queue."); } Node delNode = head; head = head.next; delNode.next = null; if (head == null) tail=null; size -- ; return delNode.e; } //获取队首的元素 @Override public E getFront() { if(isEmpty()) throw new IllegalArgumentException("Queue is empty."); return head.e; } @Override public boolean isEmpty() { return size == 0; } @Override public int getSize() { return size; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue: front "); Node curr = head; while (curr != null){ res.append(curr.e+"->"); curr = curr.next; } res.append("NULL tail"); return res.toString(); } private class Node{ public E e; public Node next; public Node(E e, Node next){ this.e = e; this.next = next; } public Node(E e){ this(e, null); } public Node(){ this(null, null); } @Override public String toString(){ return e.toString(); } } public static void main(String[] args){ LinkedListQueue<Integer> queue = new LinkedListQueue<>(); for(int i = 0 ; i < 10 ; i ++){ queue.enqueue(i); System.out.println(queue); if(i % 3 == 2){ queue.dequeue(); System.out.println(queue); } } } } 运行结果：
现在让我们来看一个leetcode上关于链表的简单例题，就是力扣上的203号题，题目描述如下：
实现如下：
//leetcode上的题：删除给定链表中和指定元素相等的所有元素 public ListNode removeElements(ListNode head, int val) { //当给定的链表为空时，直接返回 if (head == null) { return head; }else { ListNode prev; //当头节点的值和val相等时 --- 相当于删除头结点 while (head != null && head.val == val){ prev = head; head = head.next; prev.next = null; } prev = head; while (prev.next != null){ if (prev.next.val == val){ ListNode delNode = prev.next; prev.next = delNode.next; delNode.next = null; }else { prev = prev.next; } } } return head; } 递归
我们在使用递归时，要注意递归函数的“宏观语意”，递归函数就是一个函数，完成一个功能。可以理解为把待解决的复杂问题转化为求解最基本的问题。
例1：
//计算arr[i...n)这个区间内所有数字的和 -- 使用递归 private static int sum(int[] arr,int i){ //把复杂为题化为求解最基本的问题 if (i == arr.length) return 0; //将sum(arr,I+1) 递归方法理解为为可以解决求arr[(i+1)...n)这个区间内所有数字的和 return arr[i] + sum(arr,i+1); } public static int sum(int[] arr){ return sum(arr, 0); } 例2：使用递归解决删除链表中元素的问题
思路：由于链表具有天然递归性，Node可以表示一个节点，也可以表示一个链表，所以我们可以把给定的链表分为头结点和head.next,调用递归方法判断head.next中师傅含有待删除元素，然后返回已经删除该元素的链表，在判断头结点中元素是否和待删除元素相等，若相等则返回head.next,否则返回head,实现代码如下：
public ListNode removeElements(ListNode head, int val) { if (head == null) return head; ListNode res = removeElements(head.next, val); if (head.val == val) { return res; }else { head.next = res; return head; } } 上述代码也可以使用三目运算符来简化我们的代码，如下：
public ListNode removeElements(ListNode head, int val) { if (head == null) return head; head.next = removeElements(head.next, val); return head.val == val ? head.next : head; } 递归在动态数据结构中是很常用的，因为很多问题使用递归比非递归更容易解决，在后面学习树的过程中，我们也将频繁使用递归，数据结构的线性结构学习笔记就记录到这里了。
