基本数据结构
本文为所有常用数据结构的简单实现，并不进行性能优化。持续更新中……
以下为已实现数据结构的概览
1 /** 2 * 顺序表 3 * 4 * @since 2022-09-14 5 */ 6 @SuppressWarnings("all") 7 public class SequenceList<T> { 8 private final Object[] data; 9 private int length; 10 11 // 创建指定容量的顺序表 12 public SequenceList(int capacity) { 13 data = new Object[capacity]; 14 length = 0; 15 } 16 17 // 返回数据长度 18 public int length() { 19 return length; 20 } 21 22 // 在index位置上插入元素 23 public void insert(int index, T data) { 24 if (index >= 0 && index <= length && index < this.data.length) { // 保证插入的位置不超过最大容量 25 for (int i = length - 1; i >= index; i--) { 26 this.data[i + 1] = this.data[i]; 27 } 28 this.data[index] = data; 29 length++; 30 } 31 } 32 33 // 删除index位置上的值 34 public void delete(int index) { 35 if (index >= 0 && index < length) { 36 for (int i = index; i < length; i++) { 37 data[i] = data[i + 1]; 38 } 39 data[length - 1] = null; 40 length--; 41 } 42 } 43 44 // 修改index位置上的值 45 public void set(int index, T data) { 46 if (index >= 0 && index < length) { 47 this.data[index] = data; 48 } 49 } 50 51 // 获取index位置上的值 52 public T get(int index) { 53 if (index >= 0 && index < length) { 54 return (T) data[index]; 55 } else { 56 return null; 57 } 58 } 59 60 // 搜索data的索引。若不存在，则返回-1 61 public int find(T data) { 62 for (int index = 0; index < length; index++) { 63 if (this.data[index].equals(data)) { 64 return index; 65 } 66 } 67 return -1; 68 } 69 70 // 打印所有值 71 public void print() { 72 System.out.print("["); 73 if (length > 0) { 74 System.out.print(data[0]); 75 for (int i = 1; i < length; i++) { 76 System.out.print(", " + data[i]); 77 } 78 } 79 System.out.print("]\n"); 80 } 81 }
1 /** 2 * 单向链表 3 * 4 * @since 2022-09-14 5 */ 6 @SuppressWarnings("all") 7 public class SinglyLinkedList<T> { 8 private Node<T> head; 9 private int length; 10 11 // 创建单向链表 12 public SinglyLinkedList() { 13 } 14 15 // 返回数据长度 16 public int length() { 17 return length; 18 } 19 20 // 在index位置上插入一个值 21 public void insert(int index, T data) { 22 if (index >= 0 && index <= length) { 23 if (index == 0) { 24 if (length == 0) { 25 this.head = new Node<>(null, data); 26 } else { 27 this.head = new Node<>(this.head, data); 28 } 29 } else { 30 Node<T> p = head; // 插入节点的前驱 31 for (int i = 1; i < index; i++) { 32 p = p.next; 33 } 34 if (index == length) { 35 p.next = new Node<>(null, data); 36 } else { 37 p.next = new Node<>(p.next, data); 38 } 39 } 40 this.length++; 41 } 42 } 43 44 // 删除index位置上的值 45 public void delete(int index) { 46 if (index >= 0 && index < length) { 47 if (index == 0) { 48 head = head.next; 49 } else { 50 Node<T> p = head; // 删除节点的前驱 51 for (int i = 1; i < index; i++) { 52 p = p.next; 53 } 54 p.next = p.next.next; 55 } 56 this.length--; 57 } 58 } 59 60 // 修改index位置上的值 61 public void set(int index, T data) { 62 if (index >= 0 && index < length) { 63 Node<T> node = head; 64 for (int i = 0; i < index; i++) { 65 node = node.next; 66 } 67 node.data = data; 68 } 69 } 70 71 // 获取index位置上的值 72 public T get(int index) { 73 if (index >= 0 && index < length) { 74 Node<T> node = head; 75 for (int i = 0; i < index; i++) { 76 node = node.next; 77 } 78 return node.data; 79 } else { 80 return null; 81 } 82 } 83 84 // 搜索data值的索引。若不存在，则返回-1 85 public int find(T data) { 86 Node<T> node = head; 87 int index = 0; 88 while (node != null) { 89 if (node.data.equals(data)) { 90 return index; 91 } 92 index++; 93 node = node.next; 94 } 95 return -1; 96 } 97 98 // 打印所有值 99 public void print() { 100 Node<T> p = head; 101 while (p != null) { 102 System.out.print(p.data + " => "); 103 p = p.next; 104 } 105 System.out.print("null\n"); 106 } 107 108 // 链表节点 109 private static class Node<T> { 110 Node<T> next; 111 T data; 112 113 Node(Node<T> next, T data) { 114 this.next = next; 115 this.data = data; 116 } 117 } 118 }
1 /** 2 * 双向链表 3 * 4 * @since 2022-09-14 5 */ 6 @SuppressWarnings("all") 7 public class DoubleLinkedLis<T> { 8 private Node<T> head; 9 private int length; 10 11 // 创建双向链表 12 public DoubleLinkedLis() { 13 } 14 15 // 返回数据长度 16 public int length() { 17 return length; 18 } 19 20 // 在index位置上插入一个值 21 public void insert(int index, T data) { 22 if (index >= 0 && index <= length) { 23 if (index == 0) { 24 if (length == 0) { 25 this.head = new Node(null, null, data); 26 } else { 27 this.head = new Node(null, this.head, data); 28 } 29 } else { 30 Node<T> p = head; // 插入节点的前驱 31 for (int i = 1; i < index; i++) { 32 p = p.next; 33 } 34 if (index == length) { 35 p.next = new Node<>(p, null, data); 36 } else { 37 Node<T> node = new Node<>(p, p.next, data); 38 node.next.prev = node; 39 node.prev.next = node; 40 } 41 } 42 this.length++; 43 } 44 } 45 46 // 删除index位置上的值 47 public void delete(int index) { 48 if (index >= 0 && index < length) { 49 if (index == 0) { 50 head = head.next; 51 head.prev = null; 52 } else { 53 Node<T> p = head; // 删除节点的前驱 54 for (int i = 1; i < index; i++) { 55 p = p.next; 56 } 57 p.next = p.next.next; 58 if (p.next != null) { 59 p.next.prev = p; 60 } 61 } 62 this.length--; 63 } 64 } 65 66 // 设置index位置上的值 67 public void set(int index, T data) { 68 if (index >= 0 && index < length) { 69 Node<T> node = head; 70 for (int i = 0; i < index; i++) { 71 node = node.next; 72 } 73 node.data = data; 74 } 75 } 76 77 // 获取index位置上的值 78 public T get(int index) { 79 if (index >= 0 && index < length) { 80 Node<T> node = head; 81 for (int i = 0; i < index; i++) { 82 node = node.next; 83 } 84 return node.data; 85 } else { 86 return null; 87 } 88 } 89 90 // 搜索data值的索引。若不存在，则返回-1 91 public int find(T data) { 92 Node<T> node = head; 93 int index = 0; 94 while (node != null) { 95 if (node.data.equals(data)) { 96 return index; 97 } 98 index++; 99 node = node.next; 100 } 101 return -1; 102 } 103 104 // 返回data值的前驱 105 public T prev(T data) { 106 Node<T> node = head; 107 while (node != null) { 108 if (node.data.equals(data)) { 109 if (node.prev == null) { 110 return null; 111 } else { 112 return node.prev.data; 113 } 114 } 115 node = node.next; 116 } 117 return null; 118 } 119 120 // 返回data值的后继 121 public T next(T data) { 122 Node<T> node = head; 123 while (node != null) { 124 if (node.data.equals(data)) { 125 if (node.next == null) { 126 return null; 127 } else { 128 return node.next.data; 129 } 130 } 131 node = node.next; 132 } 133 return null; 134 } 135 136 // 打印所有值 137 public void print() { 138 Node<T> p = head; 139 System.out.print("null <=> "); 140 while (p != null) { 141 System.out.print(p.data + " <=> "); 142 p = p.next; 143 } 144 System.out.print("null\n"); 145 } 146 147 // 链表节点 148 private static class Node<T> { 149 Node<T> prev; 150 Node<T> next; 151 T data; 152 153 Node(Node<T> prev, Node<T> next, T data) { 154 this.prev = prev; 155 this.next = next; 156 this.data = data; 157 } 158 } 159 }
