# data_structure_demo **Repository Path**: lzyzzz666/data_structure_demo ## Basic Information - **Project Name**: data_structure_demo - **Description**: 数据结构仓库 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2022-05-16 - **Last Updated**: 2022-05-31 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # java手撸数据结构--数组(无序、有序、稀疏) 数组是java语言内置的数据类型，他是一个线性的序列，所以可以快速访问其他的元素，数组和其他语言不同，当你创建了一个数组时，他的容量是不变的，而且生命周期也是不能改变的，还有JAVA数组会做边界检查，如果发现有越界现象，会报RuntimeException异常错误，当然检查边界会以效率为代价。 ## 数组的局限性分析 - **插入快**:对于无序数组，即元素没有按照一定顺序排列，只是按照插入的顺序排列。无序数组增加一个元素很简单，只需要在数组末尾添加元素即可，但有序数组却不一定了，它需要在指定的位置插入。 - **查找慢**:当然通过下标查找是很快的。但是通常我们都是根据元素值来查找的，给定一个元素值，对于无序数组，我们需要从数组的第一个元素还是遍历，直到找到那个元素。有序数组通过特定算法查找的速度会比无需数组快。 - **删除慢**：根据元素值删除，我们要先找到该元素所在位置，然后将元素后端的值整体向前移动一个位置。也需要比较多的时间。 - **数组一旦创建，大小固定**:如果初始化一个很大的数组大小，那会白白浪费内存空间，如果给小了，后面的数据个数增加了又添加不进去了。 　　 **很显然，数组虽然插入快，但是查找和删除比较慢，而且扩展性差，所以我们一般不会用数组来存储数据。** ## 无序数组 无序数组，顾名思义，就是没有顺序的数组，即元素没有按照一定顺序排列，只是按照插入的顺序排列。 #### 创建一个类来实现无序数组 ``` class MyArray{ //存储具体数据的数组 int[] array; //当前数组存放数据数量 int size; //构造函数，初始化无序数组 public MyArray(int maxPage) { array = new int[maxPage]; size = 0; } } ``` #### 1. 插入 ``` /** * 插入 */ public void insert(int value) { if (size < array.length) { //数组未满，则插入 array[size++] = value; } } ``` #### 2. 查找 ``` /** * 查找返回下标 */ public int find(int value) { int i; for (i = 0; i < array.length; i++) { if (array[i] == value) { break; } } if (i == size) { System.out.println("数组中不存在当前数据"); return -1; } else { return i; } } ``` #### 3. 删除 ``` /** * 删除 */ public void delete(int value) { int j; if((j=this.find(value))>-1){ for (int i = j; i < size-1; i++) { array[i]=array[i+1]; } //删除完把记录-1 size--; } } ``` #### 4. 遍历 ``` /** * 遍历 */ public void forEach(){ for (int i = 0; i < size; i++) { System.out.print(array[i]+" "); } System.out.println(); } ``` #### 5.测试 ``` public static void main(String[] args) { MyArray myArray = new MyArray(10); myArray.insert(12); myArray.insert(5); myArray.insert(1); myArray.forEach(); myArray.delete(5); myArray.forEach(); } ``` 值： ``` 12 5 1 12 1 ``` ## 有序数组 **有序数组优缺点分析** - 优点： 采用二分查找效率高，比无序数组效率高。 - 缺点： 插入的时候，要移动元素，比无序数组效率低。 #### 创建一个类来实现有序数组 ``` /** * 有序数组 */ class MySequenceArray { //存储有序数组的集合 private int[] array; //元素数量 private int size; public MySequenceArray(int size) { array = new int[size]; size = 0; } ｝ ``` #### 查找 ![avatar](/static/数组二分查找.png) ``` /** * 查找返回下标(二分查找) */ public int find(int value) { if (size == 0) { return -1; } int index; //当前比对的最大下标 int maxIndex = size - 1; // 当前比对的最小下标 int minIndex = 0; //当前下标 int currentIndex; while (true) { if (minIndex > maxIndex) { return -1; } currentIndex = (maxIndex + maxIndex) / 2; if (value == array[currentIndex]) { return currentIndex; } else if (value > array[currentIndex]) { minIndex = currentIndex + 1; } else { maxIndex = currentIndex - 1; } } } ``` #### 插入 ``` /** * 插入 */ public void insert(int value) { if (array.length > size) { int index; for (index = 0; index < size; index++) { if (value < array[index]) { //找到了 break; } } if (index < size) { //数组中存在比value大的数，则index以后的数向后移动一位 for (int i = size; i > index; i--) { array[i] = array[i - 1]; } //将value插入index处 array[index] = value; } else { //最后找不到比value大的数 array[index] = value; } size++; } } ``` #### 删除 ``` /** * 删除 */ public void delete(int value) { int index; if ((index = find(value)) > -1) { for (int i = index; i < size - 1; i++) { array[i] = array[i + 1]; } size--; } } ``` #### 遍历 ``` /** * 遍历 */ public void forEach() { for (int i = 0; i < size; i++) { System.out.print(array[i] + " "); } System.out.println(); } ``` #### 测试 ``` public static void main(String[] args) { MySequenceArray mySequenceArray = new MySequenceArray(10); mySequenceArray.insert(10); mySequenceArray.insert(1); mySequenceArray.insert(55); mySequenceArray.insert(3); mySequenceArray.forEach(); mySequenceArray.delete(3); mySequenceArray.delete(2); mySequenceArray.forEach(); } ``` ``` 1 3 10 55 1 10 55 ``` ## 稀疏数组 所谓稀疏数组就是数组中大部分的内容值都未被使用（或都为零），在数组中仅有少部分的空间使用。 因此造成内存空间的浪费，为了节省内存空间，并且不影响数组中原有的内容值，我们可以采用一种压缩的方式来表示稀疏数组的内容。 ![avatar](/static/稀疏数组.png) #### 稀疏数组实现方式 如下： - 方式一：二维数组存储，用空间换取时间，占用空间大，查询效率高 ``` int[][] array = new int[7][9]; //占用63 array[1][1] = 3; array[3][0] = 1; array[3][1] = 4; array[4][2] = 7; array[5][5] = 5; ``` **遍历** ``` for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[i].length; j++) { System.out.print(array[i][j] + " "); } System.out.println(); } ``` 遍历值如下： ``` 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 ``` - 方式二：使用压缩方式，执行效率较低，占用空间小 ##### 创建一个类来实现稀疏数组 ``` /** * 稀疏数组实现 */ class MySparseArray{ //稀疏数组的行数 private int row; //稀疏数组的列数 private int col; //稀疏数组当前行当前列的值 private int val; //通过构造函数实例化 public MySparseArray(int row, int col, int val) { this.row = row; this.col = col; this.val = val; } public int getRow() { return row; } public int getCol() { return col; } public int getVal() { return val; } } ``` #### 稀疏数组的使用 ``` //定义五个节点的稀疏数组，这里的6不包含第一行记录 MySparseArray[] mySparseArrays = new MySparseArray[6]; //第一行为记录行数、列数、节点数，下标为0 //7行、9列 mySparseArrays[0] = new MySparseArray(7, 9, 6); mySparseArrays[1] = new MySparseArray(1, 1, 3); mySparseArrays[2] = new MySparseArray(3, 0, 1); mySparseArrays[3] = new MySparseArray(3, 1, 4); mySparseArrays[4] = new MySparseArray(4, 2, 7); mySparseArrays[5] = new MySparseArray(5, 5, 5); // 遍历 for (int i = 0; i < mySparseArrays[0].getRow(); i++) { for (int j = 0; j < mySparseArrays[0].getCol(); j++) { int k;//这个字段用来记录有值的下标 //第一行记录为0，要跳过第一行 for (k = 1; k < mySparseArrays.length; k++) { if (mySparseArrays[k].getRow() == i && mySparseArrays[k].getCol() == j) { break; } } if (k < mySparseArrays.length) { System.out.print(mySparseArrays[k].getVal() + " "); } else { System.out.print(0 + " "); } } //换行 System.out.println(); } ``` 值为： ``` 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 ``` # java手撸数据结构--链表(单向、双端) **链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)**。 > 使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。 ## 单向链表(无序链表)(Single-Linked List) 单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分 (data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。链表有一个头节点。 ![avatar](/static/单向链表.png) #### 首先定义一个节点类作为链表的节点 ```java /** * 链表节点类 */ public class Node { //节点值 private Integer data; //下个节点信息 private Node next; public Node(Integer data, Node next) { this.data = data; this.next = next; } public Integer getData() { return data; } public void setData(Integer data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } } ``` #### 我们创建一个类来实现基本的单向链表 ``` /** * 单向链表实现类 */ class MySingleLinkedList{ //头节点 private Node head; public Node getHead() { return head; } public void setHead(Node head) { this.head = head; } ｝ ``` ![avatar](/static/单向链表操作.png) 1. ##### 插入 ```java /** * 头插 */ public void pushHead(int data) { Node node = new Node(data, head); head = node; } ``` ```java /** * 尾插 */ public void pushTail(int data) { Node node = new Node(data, null); if (head.getData() == null) { head = node; } Node currentNode = head; while (true) { if (currentNode.getNext() == null) { currentNode.setNext(node); break; } currentNode = currentNode.getNext(); } } ``` 2. ##### 查找 ```java /** * 查找指定节点 */ public Node find(int data) { if (head == null) { return null; } Node node; Node currentNode = head; while (true) { if (currentNode == null || currentNode.getData() == data) { node = currentNode; break; } currentNode = currentNode.getNext(); } return node; } ``` 3. ##### 删除 ```java /** * 删除头节点 */ public void deleteHead() { if (head != null) { head = head.getNext(); } } ``` ```java /** * 删除尾节点 */ public void deleteTail() { if (head != null) { Node currentNode = head; while (true) { if (currentNode.getNext() == null) { break; } if (currentNode.getNext().getNext() == null) { currentNode.setNext(null); break; } currentNode = currentNode.getNext(); } } } ``` ```java /** * 删除指定元素 */ public void delete(int data) { if (head != null) { if (head.getData() == data) { deleteHead(); return; } //当前节点 Node currentNode = head; //当前节点父级节点信息 Node dadNode = head; while ((currentNode = currentNode.getNext()) != null) { if (currentNode.getData() == data) { dadNode.setNext(currentNode.getNext()); } dadNode = currentNode; } } } ``` 4. ##### 遍历 ```java /** * 遍历 */ public void forEach() { if (head != null) { Node currentNode = head; do { System.out.print(currentNode.getData() + " --> "); } while ((currentNode = currentNode.getNext()) != null); System.out.print("null"); System.out.println(); } } ``` #### 测试 ```java Node head = new Node(12, null); MySingleLinkedList mySingleLinkedList = new MySingleLinkedList(head); mySingleLinkedList.pushHead(10); mySingleLinkedList.pushTail(99); mySingleLinkedList.pushTail(1); mySingleLinkedList.pushHead(2); mySingleLinkedList.forEach(); mySingleLinkedList.deleteHead(); mySingleLinkedList.deleteTail(); mySingleLinkedList.delete(12); mySingleLinkedList.forEach(); ``` **结果** ``` 2 --> 10 --> 12 --> 99 --> 1 --> null 10 --> 99 --> null ``` ## 双端链表 双端链表是单向链表周的一种，他在原有的单向链表上加了个尾节点，对于尾部操作更加便捷。 ![avatar](/static/双端链表.png) #### 创建一个双端链表实现类 ```java /** * 双端链表实现 */ class MyDoubleLinked{ //头节点 private Node head; // 尾节点 private Node tail; public Node getHead() { return head; } public void setHead(Node head) { this.head = head; } public Node getTail() { return tail; } public void setTail(Node tail) { this.tail = tail; } } ``` ![avatar](/static/双端链表操作.png) 1. #### 插入 ```java /** * 头插 */ public void pushHead(int data) { Node node = new Node(data, head); head = node; } ``` ```java /** * 尾插 * * @param data */ public void pushTail(int data) { if (head == null) { pushHead(data); } else { Node node = new Node(data, null); tail.setNext(node); tail = node; } } ``` 2. #### 查找 ```java /** * 查找指定节点 */ public Node find(int data) { if (head == null) { return null; } Node node; Node currentNode = head; while (true) { if (currentNode == null || currentNode.getData() == data) { node = currentNode; break; } currentNode = currentNode.getNext(); } return node; } ``` 3. 删除 ```java /** * 删除头节点 */ public void deleteHead() { if (head != null) { head = head.getNext(); } } ``` ```java /** * 删除尾节点 */ public void deleteTail() { if (head != null) { Node currentNode = head; while (true) { if (currentNode.getNext() == null) { break; } if (currentNode.getNext().getNext() == null) { currentNode.setNext(null); tail = currentNode; break; } currentNode = currentNode.getNext(); } } } ``` ```java /** * 删除指定元素 */ public void delete(int data) { if (head != null) { if (head.getData() == data) { deleteHead(); return; } //当前节点 Node currentNode = head; //当前节点父级节点信息 Node dadNode = head; while ((currentNode = currentNode.getNext()) != null) { if (currentNode.getData() == data) { dadNode.setNext(currentNode.getNext()); } dadNode = currentNode; } } } ``` 4. 遍历 ```java /** * 遍历 */ public void forEach() { if (head != null) { Node currentNode = head; do { System.out.print(currentNode.getData() + " --> "); } while ((currentNode = currentNode.getNext()) != null); System.out.print("null"); System.out.println(); } } ``` #### 测试 ```java Node head = new Node(12, null); MySingleLinkedList mySingleLinkedList = new MySingleLinkedList(head); mySingleLinkedList.pushHead(10); mySingleLinkedList.pushTail(99); mySingleLinkedList.pushTail(1); mySingleLinkedList.pushHead(2); mySingleLinkedList.forEach(); mySingleLinkedList.deleteHead(); mySingleLinkedList.deleteTail(); mySingleLinkedList.delete(12); mySingleLinkedList.forEach(); ``` **结果** ``` 2 --> 10 --> 12 --> 99 --> 1 --> null 10 --> 99 --> null ``` } ``` 4. ##### 遍历 ```java /** * 遍历 */ public void forEach() { if (head != null) { Node currentNode = head; do { System.out.print(currentNode.getData() + " --> "); } while ((currentNode = currentNode.getNext()) != null); System.out.print("null"); System.out.println(); } } ``` #### 测试 ```java Node head = new Node(12, null); MySingleLinkedList mySingleLinkedList = new MySingleLinkedList(head); mySingleLinkedList.pushHead(10); mySingleLinkedList.pushTail(99); mySingleLinkedList.pushTail(1); mySingleLinkedList.pushHead(2); mySingleLinkedList.forEach(); mySingleLinkedList.deleteHead(); mySingleLinkedList.deleteTail(); mySingleLinkedList.delete(12); mySingleLinkedList.forEach(); ``` **结果** ``` 2 --> 10 --> 12 --> 99 --> 1 --> null 10 --> 99 --> null ```