1 Stack：栈

1.1 介绍

一种线性表，只允许在线性表的一端进行操作，即栈顶允许操作，而栈底不允许。像个桶状物，可以通过桶顶往桶里取放物品，而不能对桶底做什么，而且先放入桶中的物品总是在更底部，这就形成了栈的一个特性：先入后出。

1.2 时间复杂度

入栈 栈顶压入一个数据，O(1)出栈 移除栈顶数据，O(1)

1.3 适用场景

先入而后出的特点和递归的使用十分契合。

1.4 代码实现

pop() 出栈方法，即弹出栈顶数据push() 入栈方法，即往栈顶压入一个数据peek() 中文探出、偷看的意思，作用是返回当前栈顶数据，即查询栈顶数据

1.4.1 Java代码

仿造JDK1.8中Stack类源码的实现，

package structure; import java.util.Arrays; import java.util.EmptyStackException; public class MyStack<E> { // 用于存放栈数据的数组容器 private Object[] elementData; // 用于标记栈中数据的个数 private int elementCount; // 用于指定当容器需要扩容时，每次扩容的大小 private int capacityIncrement; public MyStack() { this(10); // 默认的初始容量大小为10 } public MyStack(int initialCapacity) { this(initialCapacity, 0); } /** * @param initialCapacity 指定容器的初始容量大小 * @param capacityIncrement 指定容器扩容幅度 */ public MyStack(int initialCapacity, int capacityIncrement) { this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } public void push(E item) { if (this.elementCount + 1 > this.elementData.length) { // 当容器已满时进行扩容 int oldCapacity = this.elementData.length; // 判断是否指定了扩容的幅度，未指定则默认进行2倍扩容(同源码) int newCapacity = oldCapacity + (capacityIncrement > 0 ? capacityIncrement : oldCapacity); this.elementData = Arrays.copyOf(this.elementData, newCapacity); } this.elementData[this.elementCount++] = item; } public void pop() { if (this.elementCount > 0) { this.elementCount--; this.elementData[this.elementCount] = null; // 垃圾回收 } } @SuppressWarnings("unchecked") public E peek() { if (this.elementCount == 0) { throw new EmptyStackException(); } return (E) this.elementData[this.elementCount - 1]; } }

1.4.2 Python代码

class MyStack: def __init__(self): self.element_data = [] def push(self, item): self.element_data.append(item) def pop(self): self.element_data.pop() def peek(self): return self.element_data[len(self.element_data) - 1]

1.4.3 JavaScript代码

function MyStack(elementData = []) { this._elementData = elementData; } MyStack.prototype.push = function (item) { this._elementData.push(item); }; MyStack.prototype.pop = function () { this._elementData.pop(); }; MyStack.prototype.peek = function () { return this._elementData[this._elementData.length - 1]; };

2 Queue：队列

2.1 介绍

一种线性表，允许在一端存数据，另一端取数据，这也构成了他的特性：先入先出。就像排队买票，先排队的先买到票，买到票的在前面离开队伍，需要买票的则在后面加入队伍。

2.2 时间复杂度

入队 在最后面添加一个元素，O(1)出队 在最前面删除一个元素，O(1)

2.3 适用场景

根据先进先出的特点，适用于多线程阻塞队列管理。

2.4 代码实现

add() 入队方法remove() 出队方发

2.4.1 Java代码

2.4.2.1 数组方式实现

package queue; public class MyQueue { private Object[] elementData = new Object[10]; private int elementCount; public void add(Object item) { this.elementData[this.elementCount++] = item; } public Object remove() { if (this.elementCount == 0) { throw new RuntimeException("the que is empty"); } Object res = this.elementData[0]; for (int i = 0; i < this.elementCount - 1 - 1; i++) { this.elementData[i] = this.elementData[i + 1]; } this.elementData[this.elementCount - 1] = null; return res; } }

2.4.1.2 列表方式实现

package queue; import java.util.ArrayList; public class MyQueue { private ArrayList<Object> elementData = new ArrayList<>(); public void add(Object item) { this.elementData.add(item); } public Object remove() { if (this.elementData.isEmpty()) { throw new RuntimeException("the queue is empty"); } return this.elementData.remove(0); } }

2.4.1.3 两个栈组合实现

一个栈A负责入队，一个栈B负责出队，由于栈的特性先入后出，所以可以栈A中数据依次出栈、且同时入栈到栈B中，这样栈B出栈时，相当于总是移除栈A的栈底数据

package queue; import java.util.Stack; public class MyQueue { private Stack<Object> inStack = new Stack<>(); private Stack<Object> outStack = new Stack<>(); public void add(Object item) { this.inStack.push(item); } public Object remove() { if (this.outStack.isEmpty()) { while (this.inStack.size() > 0) { this.outStack.push(this.inStack.pop()); } } return this.outStack.pop(); } }

2.4.2 Python代码

class MyQueue: def __init__(self): self.elementData = [] def add(self, item): self.elementData.append(item) def remove(self): if self.elementData.__len__() > 0: target = self.elementData[0] self.elementData.remove(target) return target

2.4.3 JavaScript代码

function MyQueue(elementData=[]){ this._elementData = elementData; } MyQueue.prototype.add = function (item) { this._elementData.push(item); }; MyQueue.prototype.remove = function () { this._elementData.shift(); };

3 Heap：堆

3.1 介绍

对于堆的定义，需满足以下条件：

堆是棵完全二叉树堆中某个节点的值总是不大于或不小于其父节点的值； 称根节点值最小的堆为最小堆/小根堆；称根节点值最大的堆为最大堆/大根堆

3.2 时间复杂度

O(n)，以小根堆为例，具体推导过程如下：

树每层的节点数最多为： 2ⁿ⁻¹，n为层数由1可得层数和节点数的关系为： h = log₂n + 1，n为节点数，h为层数每层及对应的推导次数关系如下（先熟悉代码后此处会更容易理解） 层数最多需推导次数，h为总层数节点个数1h - 12⁰2h - 22¹3h - 32²………h-112ʰ⁻²h02ʰ⁻¹ 由3可得总的事件复杂度为：

---

      s = (h - 1) * 2⁰ + (h - 2) * 2¹ + (h - 3) * 2² + … + (1) * 2ʰ⁻² + (0) * 2ʰ⁻¹          = (h - 1) * 2⁰ + (h - 2) * 2¹ + (h - 3) * 2² + … + (1) * 2ʰ⁻²

---

      2s = (h - 1) * 2¹ + (h - 2) * 2² + (h - 3) * 2³ + … + (2) * 2ʰ⁻² + (1) * 2ʰ⁻¹

---

      2s - s = - (h - 1) * 2⁰ + 2¹ + 2² + … + 2ʰ⁻² + 2ʰ⁻¹

---

      等比数列公式：Sₙ = a₁(1 - qⁿ) / (1 - q)

---

      2s - s = 1 - h + 2¹ * (1 - 2ʰ⁻¹) / (1 - 2)                 = 2ʰ⁻¹ - h - 1

---

      将 h = log₂n + 1 代入

---

      2ʰ⁻¹ - h - 1 = 2n - log₂n - 2

---

取最大影响因子并去除系数，得： O(n)

3.3 适用场景

堆排序、topN等

3.4 代码实现

create() 创建堆方法（这里以创建最小堆为例）

3.4.1 Java代码

package structure.heap; public class MyHeap { /** * 获取指定节点索引的左子节点索引 * * @param todoNodeIndex 待处理节点索引 * @return 待处理节点的左子节点索引 */ private int leftNodeIndex(int todoNodeIndex) { return (todoNodeIndex + 1) * 2 - 1; } /** * 获取指定节点索引的右子节点索引 * * @param todoNodeIndex 待处理节点索引 * @return 待处理节点的右子节点索引 */ private int rightNodeIndex(int todoNodeIndex) { return (todoNodeIndex + 1) * 2; } /** * 获取指定节点索引的父节点索引，就是求左子节点索引的反过程 * * @param todoNodeIndex 待处理节点索引 * @return 待处理节点的父节点索引 */ private int parentNodeIndex(int todoNodeIndex) { return (todoNodeIndex + 1) / 2 - 1; } /** * 用于创建堆 * * 思路是，判断指定父节点中，是否有子节点值比其还小，如果有则进行一次互换， * 以替换后的节点作为指定索引，重复前一步，直到该节点比子节点都要大时结束。 * * 每一次判断是否互换的过程就是一次推导过程 * * @param heap 正在构建中的堆数组 * @param todoNodeIndex 待进行推导的节点的索引 */ @SuppressWarnings("unchecked") private void adjust(Comparable[] heap, int todoNodeIndex) { int leftNodeIndex = leftNodeIndex(todoNodeIndex); int rightNodeIndex = rightNodeIndex(todoNodeIndex); int smallestNodeValueIndex = todoNodeIndex; //先假定最小节点值对应的索引为父节点索引 if (leftNodeIndex < heap.length) { //有可能子节点的索引超出heap索引范围，如最后一层节点的子节点索引 smallestNodeValueIndex = heap[smallestNodeValueIndex].compareTo(heap[leftNodeIndex]) > 0 ? leftNodeIndex : smallestNodeValueIndex; } if (rightNodeIndex < heap.length) { smallestNodeValueIndex = heap[smallestNodeValueIndex].compareTo(heap[rightNodeIndex]) > 0 ? rightNodeIndex : smallestNodeValueIndex; } if (smallestNodeValueIndex == todoNodeIndex) return; //当父节点节点值比子节点的节点值都要大时本次推导结束 //执行替换操作 Comparable smallNodeValue = heap[smallestNodeValueIndex]; heap[smallestNodeValueIndex] = heap[todoNodeIndex]; heap[todoNodeIndex] = smallNodeValue; adjust(heap, smallestNodeValueIndex);// 继续推导 } /** * 创建堆 * * @param arr 用于创建成堆的数组 */ public void create(Comparable[] arr) { if (arr.length < 2) return; // 从后向前推导，先求最后一个有子节点的父节点索引，即最后一个索引的父节点索引 int parentNodeIndex = parentNodeIndex(arr.length - 1); for (int i = parentNodeIndex; i >= 0; i--) { adjust(arr, i); } } } package structure; import org.junit.Test; import structure.heap.MyHeap; import java.util.Arrays; public class MyHeapTest { @Test public void test(){ MyHeap heap = new MyHeap(); Comparable[] arr = {19, 5, 12, 9, 15, 16, 7, 21, 9}; heap.create(arr); System.out.println(Arrays.toString(arr)); // [5, 9, 7, 9, 15, 16, 12, 21, 19] } }

3.4.2 Python代码

def get_left_node_index(todo_node_index): return (todo_node_index + 1) * 2 - 1 def get_right_node_index(todo_node_index): return (todo_node_index + 1) * 2 def get_parent_node_index(todo_node_index): return (todo_node_index + 1) // 2 - 1 def adjust(todo_node_index, heap): left_node_index = get_left_node_index(todo_node_index) right_node_index = get_right_node_index(todo_node_index) smallest_node_index = todo_node_index if left_node_index < len(heap): smallest_node_index = [smallest_node_index, left_node_index][heap[smallest_node_index] > heap[left_node_index]] if right_node_index < len(heap): smallest_node_index = [smallest_node_index, right_node_index][heap[smallest_node_index] > heap[right_node_index]] if smallest_node_index == todo_node_index: return heap[todo_node_index], heap[smallest_node_index] = heap[smallest_node_index], heap[todo_node_index] adjust(smallest_node_index, heap) def create(arr): if len(arr) < 2: return parent_node_index = get_parent_node_index(len(arr) - 1) for index in range(parent_node_index, -1, -1): adjust(index, arr) if __name__ == '__main__': arr = [19, 5, 12, 9, 15, 16, 7, 21, 9] create(arr) print(arr) # [5, 9, 7, 9, 15, 16, 12, 21, 19]

3.4.3 JavaScript代码

let getLeftNodeIndex = (todoNodeIndex => (todoNodeIndex + 1) * 2 - 1); let getRightNodeIndex = (todoNodeIndex => (todoNodeIndex + 1) * 2); let getParentNodeIndex = (todoNodeIndex => parseInt((todoNodeIndex + 1) / 2 + "") - 1); let adjust = ((heap, todoNodeIndex) => { let leftNodeIndex = getLeftNodeIndex(todoNodeIndex); let rightNodeIndex = getRightNodeIndex(todoNodeIndex); let smallestNodeIndex = todoNodeIndex; if (leftNodeIndex < heap.length) smallestNodeIndex = heap[smallestNodeIndex] > heap[leftNodeIndex] ? leftNodeIndex : smallestNodeIndex; if (rightNodeIndex < heap.length) smallestNodeIndex = heap[smallestNodeIndex] > heap[rightNodeIndex] ? rightNodeIndex : smallestNodeIndex; if (smallestNodeIndex === todoNodeIndex) return; [heap[todoNodeIndex], heap[smallestNodeIndex]] = [heap[smallestNodeIndex], heap[todoNodeIndex]]; adjust(heap, smallestNodeIndex); }); let create = (heap => { let parentNodeIndex = getParentNodeIndex(heap.length - 1); for (let i = parentNodeIndex; i >= 0; i--) { adjust(heap, i); } }); let arr = [9, 5, 12, 9, 15, 16, 7, 21, 19]; create(arr); console.log(arr); //[5, 9, 7, 9, 15, 16, 12, 21, 19]

4 BinarySearchTree：二叉查找树

4.1 介绍

二叉查找树，又称二叉搜索树，亦称二叉排序树，他有如下特点：

首先它是个二叉树其次树中的任一节点总是大于其左子树的任一节点，小于其右子树的任一节点如图：

4.2 时间复杂度

二叉查找树的时间复杂度，通常指查找节点的时间复杂度，这分为两种情况，如果这颗二叉树是平衡的，由树高和节点数的关系：h = log₂n + 1 知，最多需要比较 log₂n + 1 次，即时间复杂度为：O(log₂n)，但是可能有极端情况，如正序或倒序将一批数据（如：1,2,3,4,5）依次添加构建成树，那么树的形状将是这样的：

此时树高将是 n，时间复杂度为：O(n)。

4.3 使用场景

由于二叉查找树存在最差时间复杂度：O(n)情况，所以在应用上，更多的是使用基于二叉查找树、并经过优化的平衡二叉树、红黑树等。

4.4 代码实现

add() 添加节点方法search() 查找节点方法remove() 删除节点方法show() 展示所有节点，通过中序遍历方式，可以顺序输出，相当于实现了排序

4.4.1 Java代码实现

package structure.tree; import java.util.Optional; public class MyBinarySearchTree { public class Node { public Comparable value; public Node leftNode; public Node rightNode; Node(Comparable value) { this.value = value; } /** * 添加节点的具体实现 * 注意这里为了方便，对于相同的节点值只进行添加一次 * * @param node 待添加的节点 */ @SuppressWarnings("unchecked") private void addNode(Node node) { if (node.value.compareTo(this.value) > 0) { //如果待添加的节点比当前节点大，说明待添加节点应该放在当前节点右子树上 if (null == this.rightNode) { //如果当前节点尚无右节点 this.rightNode = node; } else { this.rightNode.addNode(node); } } else if (node.value.compareTo(this.value) < 0) { //如果待添加的节点比当前节点小，说明待添加节点应该放在当前节点左子树上 if (null == this.leftNode) { //如果当前节点尚无左节点 this.leftNode = node; } else { this.leftNode.addNode(node); } } } /** * 查找节点的具体实现 * * @param value 待查找节点的节点值 * @return 查找到的节点，找不到则返回null */ @SuppressWarnings("unchecked") private Optional<Node> searchNode(Comparable value) { if (value.compareTo(this.value) == 0) { return Optional.of(this); } else if (value.compareTo(this.value) > 0 && null != this.rightNode) { return this.rightNode.searchNode(value); } else if (value.compareTo(this.value) < 0 && null != this.leftNode) { return this.leftNode.searchNode(value); } return Optional.empty(); } /** * 删除节点具体实现 * * @param node 待删除节点 */ private void removeNode(Node node) { Node parentNode = searchParentNode(node);//获取父节点 if (null == node.leftNode && null == node.rightNode){ //如果要删除的节点是叶子结点：没有左子节点，也没有右子节点 if (null == parentNode){ //如果删除的是根节点 MyBinarySearchTree.this.rootNode = null; } else { //如果删除的是非根节点 if (node == parentNode.leftNode) { parentNode.leftNode = null; } else { parentNode.rightNode = null; } } } else if(null != node.leftNode && null != node.rightNode){ //如果要删除的节点同时有左右节点 /* * 删除方式是：找到右子树最小节点（或左子树最大节点），删除掉，并将值赋给被删除节点 * */ Node rightTreeMinNode = searchMinNode(node.rightNode); removeNode(rightTreeMinNode); node.value = rightTreeMinNode.value; } else { //如果要删除的节点存在左子节点或右子节点 if (null == parentNode){ if (null != node.leftNode){ MyBinarySearchTree.this.rootNode = MyBinarySearchTree.this.rootNode.leftNode; } else { MyBinarySearchTree.this.rootNode = MyBinarySearchTree.this.rootNode.rightNode; } } else { if (null != node.leftNode) { if (node == parentNode.leftNode){ parentNode.leftNode = node.leftNode; } else { parentNode.rightNode = node.leftNode; } } else { if (node == parentNode.leftNode){ parentNode.leftNode = node.rightNode; } else { parentNode.rightNode = node.rightNode; } } } } } /** * 查找指定节点的父节点 * * @param node 指定节点 * @return 找到的指定节点的父节点，找不到返回null */ @SuppressWarnings("unchecked") private Node searchParentNode(Node node) { if (null == node) return null; if ((null != this.leftNode && this.leftNode == node) || (null != this.rightNode && this.rightNode == node)) { return this; } else if (node.value.compareTo(this.value) < 0 && null != this.leftNode) { return this.leftNode.searchParentNode(node); } else if (node.value.compareTo(this.value) > 0 && null != this.rightNode) { return this.rightNode.searchParentNode(node); } return null; } /** * 查找指定节点的最小子节点 * * @param node 指定节点 * @return 找到的指定节点的最小子节点 */ private Node searchMinNode(Node node) { if (null == node) return null; if (null == node.leftNode) return node; else return searchMinNode(node.leftNode); } /** * 通过中序排序方式从小到大展示二叉树的所有节点值 */ private void middleOrderShow(Node node) { if (null == node) return; middleOrderShow(node.leftNode); System.out.print(node.value + " "); middleOrderShow(node.rightNode); } } /** * 根节点 */ private Node rootNode; /** * 添加节点方法 * 通过输入节点值来添加节点 * * @param value 输入的节点值 */ public void add(Comparable value) { Node newNode = new Node(value); if (null == this.rootNode) this.rootNode = newNode; else this.rootNode.addNode(newNode); } /** * 查找节点方法 * 通过输入节点值来查找对应的节点 * * @param value 输入的节点值 * @return 查找到的节点，找不到则返回null */ public Node search(Comparable value) { if (null == this.rootNode) return null; Optional<Node> target = this.rootNode.searchNode(value); return target.orElse(null); } /** * 删除节点 * 通过输入节点值来删除对应的节点 * * @param value 输入的节点值 */ public void remove(Comparable value) { if (null == this.rootNode) return; /*先找到要删除的节点*/ Node targetNode = search(value); if (null == targetNode) return; this.rootNode.removeNode(targetNode); } /** * 展示所有节点 */ public void show(){ if (null == this.rootNode) return; System.out.print("[ "); this.rootNode.middleOrderShow(this.rootNode); System.out.print("]"); System.out.println(); } } package structure; import org.junit.Test; import structure.tree.MyBinarySearchTree; public class MyBinarySearchTreeTest { @Test public void test(){ MyBinarySearchTree tree = new MyBinarySearchTree(); Comparable[] values = {5, 2, 16, 8, 1, 19, 3, 15, 10, 21, 16, 23}; for (Comparable value : values) { tree.add(value); } tree.show(); //[ 1 2 3 5 8 10 15 16 19 21 23 ] MyBinarySearchTree.Node root = tree.search(5); System.out.println(root.leftNode.value); //2 System.out.println(root.rightNode.value); //16 tree.remove(16); System.out.println(root.rightNode.value); //19 tree.show(); //[ 1 2 3 5 8 10 15 19 21 23 ] } }

4.4.2 Python代码实现

class Node: def __init__(self, value: int): self.value = value self.left_node = None self.right_node = None def add_node(self, node): if node.value < self.value: if not self.left_node: self.left_node = node else: self.left_node.add_node(node) elif node.value > self.value: if not self.right_node: self.right_node = node else: self.right_node.add_node(node) def search_node(self, value): if value == self.value: return self elif value < self.value and self.left_node: return self.left_node.search_node(value) elif value > self.value and self.right_node: return self.right_node.search_node(value) def search_parent_node(self, node): if not node: return if self.left_node == node or self.right_node == node: return self elif node.value < self.value and self.left_node: return self.left_node.search_parent_node(node) elif node.value > self.value and self.right_node: return self.right_node.search_parent_node(node) def search_min_node(self, node): if node: if not node.left_node: return node else: return self.search_min_node(node.left_node) def middle_order_show(self, node): if node: self.middle_order_show(node.left_node) print(node.value, end=",") self.middle_order_show(node.right_node) class MyBinarySearchTree: root_node = None def add(self, value: int): new_node = Node(value) if self.root_node is None: self.root_node = new_node else: self.root_node.add_node(new_node) def search(self, value: int): if self.root_node is not Node: return self.root_node.search_node(value) def remove(self, value: int): if self.root_node is Node: return target_node = self.root_node.search_node(value) if not target_node: return parent_node = self.root_node.search_parent_node(target_node) if not target_node.left_node and not target_node.right_node: if not parent_node: self.root_node = None else: if target_node == parent_node.left_node: parent_node.left_node = None else: parent_node.right_node = None elif target_node.left_node and target_node.right_node: right_tree_min_node = self.root_node.search_min_node(target_node.right_node) self.remove(right_tree_min_node.value) target_node.value = right_tree_min_node.value else: if not parent_node: if target_node.left_node: self.root_node = target_node.left_node else: self.root_node = target_node.right_node else: if target_node.left_node: if target_node == parent_node.left_node: parent_node.left_node = target_node.left_node else: parent_node.right_node = target_node.left_node else: if target_node == parent_node.left_node: parent_node.left_node = target_node.right_node else: parent_node.right_node = target_node.right_node def show(self): if self.root_node is not None: self.root_node.middle_order_show(self.root_node) print() if __name__ == '__main__': tree = MyBinarySearchTree() for value in [5, 2, 16, 8, 1, 19, 3, 15, 10, 21, 16, 23]: tree.add(value) tree.show() # 1, 2, 3, 5, 8, 10, 15, 16, 19, 21, 23 root = tree.search(5) print(root.left_node.value) # 2 print(root.right_node.value) # 16 tree.remove(16) print(root.right_node.value) # 19 tree.show() # 1, 2, 3, 5, 8, 10, 15, 19, 21, 23

4.4.3 JavaScript代码实现

function Node(value) { this.value = value; this.leftNode = null; this.rightNode = null; } Node.prototype.addNode = function (node) { if (node.value < this.value) { if (null == this.leftNode) this.leftNode = node; else this.leftNode.addNode(node); } else if (node.value > this.value) { if (null == this.rightNode) this.rightNode = node; else this.rightNode.addNode(node); } }; Node.prototype.searchNode = function (value) { if (value === this.value) return this; else if (value < this.value && this.leftNode) { return this.leftNode.searchNode(value); } else if (value > this.value && this.rightNode) { return this.rightNode.searchNode(value); } else { return null; } }; Node.prototype.searchParentNode = function (node) { if (null === node) return null; if (node === this.leftNode || node === this.rightNode) return this; else if (node.value < this.value && this.leftNode) return this.leftNode.searchParentNode(node); else if (node.value > this.value && this.rightNode) return this.rightNode.searchParentNode(node); else return null; }; Node.prototype.searchMinNode = function (node) { if (!node) return null; if (null === node.leftNode) return node; else return this.searchMinNode(node.leftNode); }; Node.prototype.middleOrderShow = function (node) { if (!node) return; this.middleOrderShow(node.leftNode); console.log(node.value); this.middleOrderShow(node.rightNode); }; function MyBinarySearchTree() { this.rootNode = null; } MyBinarySearchTree.prototype.add = function (value) { let newNode = new Node(value); if (null == this.rootNode) this.rootNode = newNode; else this.rootNode.addNode(newNode); }; MyBinarySearchTree.prototype.search = function (value) { if (null == this.rootNode) return; return this.rootNode.searchNode(value); }; MyBinarySearchTree.prototype.remove = function (value) { if (null == this.rootNode) return; let targetNode = this.rootNode.searchNode(value); if (!targetNode) return; let parentNode = this.rootNode.searchParentNode(targetNode); if (!targetNode.leftNode && !targetNode.rightNode) { if (!parentNode) { this.rootNode = null; } else { if (targetNode === parentNode.leftNode) parentNode.leftNode = null; else parentNode.rightNode = null; } } else if (targetNode.leftNode && targetNode.rightNode) { let rightTreeMinNode = this.rootNode.searchMinNode(targetNode.rightNode); this.remove(rightTreeMinNode.value); targetNode.value = rightTreeMinNode.value; } else { if (!parentNode) { if (targetNode.leftNode) this.rootNode = this.rootNode.leftNode; else this.rootNode = this.rootNode.rightNode; } else { if (targetNode.leftNode) { if (targetNode === parentNode.leftNode) { parentNode.leftNode = targetNode.leftNode; } else { parentNode.rightNode = targetNode.leftNode; } } else { if (targetNode === parentNode.leftNode) { parentNode.leftNode = targetNode.rightNode; } else { parentNode.rightNode = targetNode.rightNode; } } } } }; MyBinarySearchTree.prototype.show = function () { if (null != this.rootNode) this.rootNode.middleOrderShow(this.rootNode) }; let tree = new MyBinarySearchTree(); let values = [5, 2, 16, 8, 1, 19, 3, 15, 10, 21, 16, 23]; values.forEach(value => tree.add(value)); tree.show(); // 1, 2, 3, 5, 8, 10, 15, 16, 19, 21, 23 let root = tree.search(5); console.log(root.leftNode.value); // 2 console.log(root.rightNode.value); // 16 tree.remove(16); console.log(root.rightNode.value); // 19 tree.show(); // 1, 2, 3, 5, 8, 10, 15, 19, 21, 23

5 SinglyLinkedList：单向链表

5.1 介绍

和其他链表（还有单向循环链表、双向链表、双向循环链表）一样，单向链表也是由众多的节点组成，其中单向链表的每个节点又有两个组成部分：数据域和引用域

数据域 存储着具体的数据值引用域 存储着下一个数据的地址，并且最后一个节点的引用域为null

5.2 时间复杂度

这个很好理解，无论添加节点、删除节点、更新节点、获取节点，都是从第一个节点开始往后找，直到直到目标，所以最坏的情况就是找到最后一个节点处，此时时间复杂度都为O(n)

5.3 代码实现

add() 添加节点remove() 根据 节点值/索引 移除节点update() 根据 节点值/索引 更新节点get() 根据 指定索引 获取对应的节点size() 获取节点个数show() 遍历，展示所有节点

5.3.1 Java代码实现

package structure.linkedlist; public class MySinglyLinkedList<E> { class Node { E value; Node nextNode; Node(E value) { this.value = value; } private void addNode(Node node) { if (null == this.nextNode) this.nextNode = node; else this.nextNode.addNode(node); } private void removeNode(E value) { Node currentNode = this.nextNode; if (null == currentNode) return; if (value.equals(currentNode.value)) { this.nextNode = currentNode.nextNode; MySinglyLinkedList.this.nodeCount--; } else { this.nextNode.removeNode(value); } } private void removeNode(int index) { //在此之前已经对index进行了判断 Node currentNode = this.nextNode; int currentIndex = ++MySinglyLinkedList.this.firstNodeIndex; if (currentIndex == index) { this.nextNode = currentNode.nextNode; MySinglyLinkedList.this.nodeCount--; } else { this.nextNode.removeNode(index); } } private void updateNode(E oldValue, E newValue) { if (oldValue.equals(this.value)) { this.value = newValue; } else { if (null != this.nextNode) { this.nextNode.updateNode(oldValue, newValue); } } } private void updateNode(int index, E newValue){ //在此之前已经对index进行了判断 int currentIndex = ++MySinglyLinkedList.this.firstNodeIndex; if (currentIndex == index) { this.nextNode.value = newValue; } else { this.nextNode.updateNode(index, newValue); } } private E getNode(int index){ //在此之前已经对index进行了判断 int currentIndex = ++MySinglyLinkedList.this.firstNodeIndex; if (currentIndex == index) { return this.nextNode.value; } else { return this.nextNode.getNode(index); } } private void showNodes(){ if (null != this.nextNode) { System.out.print(this.value + ", "); this.nextNode.showNodes(); } else { System.out.print(this.value); } } } /** * 第一个节点 */ private Node firstNode; /** * 第一个节点的索引值 */ private int firstNodeIndex; /** * 节点数 */ private int nodeCount; public void add(E value) { Node newNode = new Node(value); if (null == this.firstNode) { this.firstNode = newNode; } else { this.firstNode.addNode(newNode); } this.nodeCount++; } /** * 根据节点值来删除节点 * * @param value 要删除的节点的节点值 */ public void remove(E value) { if (null == this.firstNode) { throw new RuntimeException("list is empty!"); } if (value.equals(this.firstNode.value)) { this.firstNode = this.firstNode.nextNode; this.nodeCount--; } else { this.firstNode.removeNode(value); } } /** * 根据节点索引来删除节点 * * @param index 要删除的节点的索引 */ public void remove(int index) { if (index < 0 || index >= this.nodeCount) { throw new IndexOutOfBoundsException(); } if (null == this.firstNode) { throw new RuntimeException("list is empty!"); } if (0 == index) { this.firstNode = this.firstNode.nextNode; this.nodeCount--; } else { this.firstNodeIndex = 0; this.firstNode.removeNode(index); } } /** * 根据节点值进行更新操作 * * @param oldValue 旧的节点值 * @param newValue 新的节点值 */ public void update(E oldValue, E newValue) { if (null == this.firstNode) { throw new RuntimeException("list is empty!"); } if (oldValue.equals(this.firstNode.value)) { this.firstNode.value = newValue; } else { this.firstNode.updateNode(oldValue, newValue); } } /** * 根据节点索引进行更新操作 * * @param index 待更新节点的索引 * @param newValue 新的节点值 */ public void update(int index, E newValue) { if (index < 0 || index >= this.nodeCount) { throw new IndexOutOfBoundsException(); } if (null == this.firstNode) { throw new RuntimeException("list is empty!"); } if (0 == index) { this.firstNode.value = newValue; } else { this.firstNodeIndex = 0; this.firstNode.updateNode(index, newValue); } } public E get(int index) { if (index < 0 || index >= this.nodeCount) { throw new IndexOutOfBoundsException(); } if (null == this.firstNode) { throw new RuntimeException("list is empty!"); } if (0 == index) return this.firstNode.value; else { this.firstNodeIndex = 0; return this.firstNode.getNode(index); } } public int size() { if (null == this.firstNode) { throw new RuntimeException("list is empty!"); } return this.nodeCount; } public void show() { if (null == this.firstNode) { throw new RuntimeException("list is empty!"); } System.out.print("["); this.firstNode.showNodes(); System.out.print("]"); System.out.println(); } } package structure; import org.junit.Test; import structure.linkedlist.MySinglyLinkedList; public class MySinglyLinkedListTest { @Test public void test(){ MySinglyLinkedList<String> list = new MySinglyLinkedList<>(); /*1.测试添加数据*/ String[] values = {"c", "b", "a", "aa", "bb", "cc", "a", "b", "c"}; for (String value: values) { list.add(value); } System.out.println(list.size()); //9 list.show(); //[c, b, a, aa, bb, cc, a, b, c] /*2.测试删除数据*/ /*2.1.索引方式删除第一个数据*/ list.remove(0); System.out.println(list.size()); //8 list.show(); //[b, a, aa, bb, cc, a, b, c] /*2.2.索引方式删除非第一个数据*/ list.remove(2); System.out.println(list.size()); //7 list.show(); //[b, a, bb, cc, a, b, c] /*2.3.节点值方式删除第一个数据*/ list.remove("b"); System.out.println(list.size()); //6 list.show(); //[a, bb, cc, a, b, c] /*2.4.节点值方式删除非第一个数据*/ list.remove("c"); System.out.println(list.size()); //5 list.show(); //[a, bb, cc, a, b] /*3.测试修改数据*/ /*3.1.索引方式修改第一个数据*/ list.update(0, "aaa"); list.show(); //[aaa, bb, cc, a, b] /*3.2.索引方式修改非第一个数据*/ list.update(2, "ccc"); list.show(); //[aaa, bb, ccc, a, b] /*3.3.节点值方式修改第一个数据*/ list.update("aaa", "aa"); list.show(); //[aa, bb, ccc, a, b] /*3.4.节点值方式修改非第一个数据*/ list.update("ccc", "cc"); list.show(); //[aa, bb, cc, a, b] /*4.测试获取数据*/ /*4.1.获取第一个数据*/ System.out.println(list.get(0)); //aa /*4.2.获取非第一个数据*/ System.out.println(list.get(2)); //cc } }

5.3.2 Python代码实现

class Node: def __init__(self, value, next_node=None): self.value = value self.next_node = next_node def add_node(self, node): if not self.next_node: self.next_node = node else: self.next_node.add_node(node) def remove_node_by_value(self, value) -> int: current_node = self.next_node if not current_node: return 0 if value == current_node.value: self.next_node = current_node.next_node return -1 else: return self.next_node.remove_node_by_value(value) def remove_node_by_index(self, index, first_node_index=0) -> int: current_node = self.next_node current_node_index = first_node_index + 1 if not current_node: return 0 if current_node_index == index: self.next_node = current_node.next_node return -1 else: return self.next_node.remove_node_by_index(index, current_node_index) def update_node_by_value(self, old_value, new_value): if not self.next_node: return if self.next_node.value == old_value: self.next_node.value = new_value else: self.next_node.update_node_by_value(old_value, new_value) def update_node_by_index(self, index, new_value, first_node_index=0): if not self.next_node: return current_node_index = first_node_index + 1 if current_node_index == index: self.next_node.value = new_value else: self.next_node.update_node_by_index(index, new_value, current_node_index) def get_node(self, index, first_node_index=0): if not self.next_node: return current_node_index = first_node_index + 1 if current_node_index == index: return self.next_node.value else: return self.next_node.get_node(index, current_node_index) class MySinglyLinkedList: first_node = None node_count = 0 def add(self, value): new_node = Node(value) if self.first_node is None: self.first_node = new_node else: self.first_node.add_node(new_node) self.node_count += 1 def remove_by_value(self, value): if self.first_node is None: raise Exception("list is empty!") if value == self.first_node.value: self.first_node = self.first_node.next_node self.node_count -= 1 else: self.node_count += self.first_node.remove_node_by_value(value) def remove_by_index(self, index: int): if index < 0 or index >= self.node_count: raise IndexError('list index out of range') if self.first_node is None: raise Exception("list is empty!") if 0 == index: self.first_node = self.first_node.next_node self.node_count -= 1 else: self.node_count += self.first_node.remove_node_by_index(index) def update_by_value(self, old_value, new_value): if self.first_node is None: raise Exception("list is empty!") if self.first_node.value == old_value: self.first_node.value = new_value else: self.first_node.update_node_by_value(old_value, new_value) def update_by_index(self, index: int, new_value): if index < 0 or index >= self.node_count: raise IndexError('list index out of range') if self.first_node is None: raise Exception("list is empty!") if 0 == index: self.first_node.value = new_value else: self.first_node.update_node_by_index(index, new_value) def get(self, index: int): if index < 0 or index >= self.node_count: raise IndexError('list index out of range') if self.first_node is None: raise Exception("list is empty!") if 0 == index: return self.first_node.value else: return self.first_node.get_node(index) def size(self) -> int: if self.first_node is None: raise Exception("list is empty!") return self.node_count def show(self): if self.first_node is None: raise Exception("list is empty!") current_node = self.first_node print('[', end='') while current_node: print(current_node.value, end=[', ', ''][current_node.next_node is None]) current_node = current_node.next_node print(']', end='') print() if __name__ == '__main__': li = MySinglyLinkedList() """1.测试添加数据""" for value in ["c", "b", "a", "aa", "bb", "cc", "a", "b", "c"]: li.add(value) li.show() # [c, b, a, aa, bb, cc, a, b, c] """2.测试删除数据""" '''2.1.索引方式删除第一个数据''' li.remove_by_index(0) li.show() # [b, a, aa, bb, cc, a, b, c] '''2.2.索引方式删除非第一个数据''' li.remove_by_index(2) li.show() # [b, a, bb, cc, a, b, c] '''2.3.节点值方式删除第一个数据''' li.remove_by_value('b') li.show() # [a, bb, cc, a, b, c] '''2.4.节点值方式删除非第一个数据''' li.remove_by_value('c') li.show() # [a, bb, cc, a, b] """3.测试修改数据""" '''3.1.索引方式修改第一个数据''' li.update_by_index(0, "aaa") li.show() # [aaa, bb, cc, a, b] '''3.2.索引方式修改非第一个数据''' li.update_by_index(2, "ccc") li.show() # [aaa, bb, ccc, a, b] '''3.3.节点值方式修改第一个数据''' li.update_by_value('aaa', "aa") li.show() # [aa, bb, ccc, a, b] '''3.4.节点值方式修改非第一个数据''' li.update_by_value("ccc", 'cc') li.show() # [aa, bb, cc, a, b] """4.测试获取数据""" '''4.1.获取第一个索引数据''' print(li.get(0)) # aa '''4.2.获取非第一个索引数据''' print(li.get(2)) # cc

5.3.3 JavaScript代码实现

function Node(value) { this.value = value; this.nextNode = null; } Node.prototype.addNode = function (node) { if (null === this.nextNode) this.nextNode = node; else this.nextNode.addNode(node); }; Node.prototype.removeNodeByValue = function (value) { let currentNode = this.nextNode; if (null === currentNode) return 0; if (value === currentNode.value) { this.nextNode = currentNode.nextNode; return -1; } else return this.nextNode.removeNodeByValue(value); }; Node.prototype.removeNodeByIndex = function (index, firstNodeIndex = 0) { let currentNode = this.nextNode; let currentNodeIndex = ++firstNodeIndex; if (null === currentNode) return 0; if (currentNodeIndex === index) { this.nextNode = currentNode.nextNode; return -1; } else return this.nextNode.removeNodeByIndex(index, currentNodeIndex); }; Node.prototype.updateNodeByValue = function (oldValue, newValue) { if (this.nextNode) { if (oldValue === this.nextNode.value) this.nextNode.value = newValue; else this.nextNode.updateNodeByValue(oldValue, newValue); } }; Node.prototype.updateNodeByIndex = function (index, newValue, firstNodeIndex = 0) { if (this.nextNode) { let currentNodeIndex = ++firstNodeIndex; if (currentNodeIndex === index) this.nextNode.value = newValue; else this.nextNode.updateNodeByIndex(index, newValue, currentNodeIndex); } }; Node.prototype.getNode = function (index, firstNodeIndex = 0) { if (this.nextNode) { let currentNodeIndex = ++firstNodeIndex; if (currentNodeIndex === index) return this.nextNode.value; else return this.nextNode.getNode(index, currentNodeIndex); } }; function MySinglyLinkedList() { this.firstNode = null; this.nodeCount = 0; } MySinglyLinkedList.prototype.add = function (value) { let newNode = new Node(value); if (!this.firstNode) this.firstNode = newNode; else this.firstNode.addNode(newNode); this.nodeCount++; }; MySinglyLinkedList.prototype.removeByValue = function (value) { if (this.firstNode) { if (value === this.firstNode.value) { this.firstNode = this.firstNode.nextNode; this.nodeCount--; } else this.nodeCount += this.firstNode.removeNodeByValue(value); } }; MySinglyLinkedList.prototype.removeByIndex = function (index) { if (this.firstNode && 0 <= index && index < this.nodeCount) { if (0 === index) { this.firstNode = this.firstNode.nextNode; this.nodeCount--; } else this.nodeCount += this.firstNode.removeNodeByIndex(index); } }; MySinglyLinkedList.prototype.updateByValue = function (oldValue, newValue) { if (this.firstNode) { if (oldValue === this.firstNode.value) this.firstNode.value = newValue; else this.firstNode.updateNodeByValue(oldValue, newValue); } }; MySinglyLinkedList.prototype.updateByIndex = function (index, newValue) { if (this.firstNode && 0 <= index && index < this.nodeCount) { if (0 === index) this.firstNode.value = newValue; else this.firstNode.updateNodeByIndex(index, newValue); } }; MySinglyLinkedList.prototype.get = function (index) { if (this.firstNode && 0 <= index && index < this.nodeCount) { if (0 === index) return this.firstNode.value; else return this.firstNode.getNode(index); } }; MySinglyLinkedList.prototype.size = function () { return this.nodeCount; }; MySinglyLinkedList.prototype.show = function () { let values = '['; let currentNode = this.firstNode; while (currentNode) { values += currentNode.value; currentNode = currentNode.nextNode; values += currentNode ? ', ' : ''; } values += ']'; console.log(values) }; let list = new MySinglyLinkedList(); /*1.测试添加数据*/ ["c", "b", "a", "aa", "bb", "cc", "a", "b", "c"].forEach(value => list.add(value)); list.show(); //[c, b, a, aa, bb, cc, a, b, c] /*2.测试删除数据*/ /*2.1.索引方式删除第一个数据*/ list.removeByIndex(0); list.show(); //[b, a, aa, bb, cc, a, b, c] /*2.2.索引方式删除非第一个数据*/ list.removeByIndex(2); list.show(); //[b, a, bb, cc, a, b, c] /*2.3.节点值方式删除第一个数据*/ list.removeByValue("b"); list.show(); //[a, bb, cc, a, b, c] /*2.4.节点值方式删除非第一个数据*/ list.removeByValue("c"); list.show(); //[a, bb, cc, a, b] /*3.测试修改数据*/ /*3.1.索引方式修改第一个数据*/ list.updateByIndex(0, "aaa"); list.show(); //[aaa, bb, cc, a, b] /*3.2.索引方式修改非第一个数据*/ list.updateByIndex(2, "ccc"); list.show(); //[aaa, bb, ccc, a, b] /*3.3.节点值方式修改第一个数据*/ list.updateByValue("aaa", "aa"); list.show(); //[aa, bb, ccc, a, b] /*3.4.节点值方式修改非第一个数据*/ list.updateByValue("ccc", "cc"); list.show(); //[aa, bb, cc, a, b] /*4.测试获取数据*/ /*4.1.获取第一个数据*/ console.log(list.get(0)); //aa /*4.2.获取非第一个数据*/ console.log(list.get(2)); //cc