基本数据结构前言
本文为所有常用数据结构的简单实现。持续更新中……
友情链接 csdn
以下为已实现数据结构的概览
1. 线性表: 顺序表、单向链表、双向链表
线性表顺序表
1 /** 2 * 顺序表 3 * 4 * @since 2022-09-14 5 */ 6 @SuppressWarnings("all") 7 public class SequenceList { 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的索引。若不存在，则返回-161 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 { 8 private Node 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 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 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 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 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 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 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 {110 Node next;111 T data;112 113 Node(Node 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 { 8 private Node 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 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 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 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 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 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 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 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 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 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 {149 Node prev;150 Node next;151 T data;152 153 Node(Node prev, Node next, T data) {154 this.prev = prev;155 this.next = next;156 this.data = data;157 }158 }159 }