概述
数据结构是计算机科学中非常重要的一部分，用于组织和管理数据的方式。在软件开发过程中，选择合适的数据结构可以提高算法的效率，从而提高程序的性能。
Java是一种面向对象的编程语言，提供了丰富的数据结构和算法库。本文将介绍一些常用的数据结构，并使用Java实现它们。
数组
数组是最简单的数据结构之一，它由相同类型的元素组成，并按照顺序进行排列。在Java中，数组的长度是固定的，一旦创建后无法改变。以下是一个使用Java实现的简单数组示例：
public class Array {
private int[] data;
private int size;
public Array(int capacity) {
data = new int[capacity];
size = 0;
}
public int getSize() {
return size;
}
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
public void add(int index, int value) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Invalid index");
}
if (size == data.length) {
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = value;
size++;
}
public void remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Invalid index");
}
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
if (size <= data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
}
public int get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Invalid index");
}
return data[index];
}
public void set(int index, int value) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Invalid index");
}
data[index] = value;
}
private void resize(int newCapacity) {
int[] newData = new int[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Array: [");
for (int i = 0; i < size; i++) {
builder.append(data[i]);
if (i != size - 1) {
builder.append(", ");
}
}
builder.append("]");
return builder.toString();
}
}
该数组实现包含一些常见的操作，如获取大小、判断是否为空、增加和删除元素、获取元素值等。在插入和删除元素时，如果数组已满或过于空闲，则会自动调整容量。
链表
链表是一种非连续存储的数据结构，它由节点组成，并使用指针将它们连接起来。在Java中，链表可以是单向、双向或循环的。以下是一个使用Java实现的单向链表示例：
public class LinkedList<T> {
private class Node {
public T value;
public Node next;
public Node(T value, Node next) {
this.value = value;
this.next = next;
}
public Node(T value) {
this(value, null);
}
public Node() {
this(null, null);
}
}
private Node head;
private int size;
public LinkedList() {
head = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void addFirst(T value) {
head = new Node(value, head);
size++;
}
public void addLast(T value) {
Node node = new Node(value);
if (isEmpty()) {
head = node;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
size++;
}
public void add(int index, T value) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Invalid index");
}
if (index == 0) {
addFirst(value);
} else if (index == size) {
addLast(value);
} else {
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
Node node = new Node(value);
node.next = prev.next;
prev.next = node;
size++;
}
}
public T removeFirst() {
if (isEmpty()) {
throw new NoSuchElementException("List is empty");
}
T value = head.value;
head = head.next;
size--;
return value;
}
public T removeLast() {
if (isEmpty()) {
throw new NoSuchElementException("List is empty");
}
if (size == 1) {
return removeFirst();
} else {
Node prev = head;
while (prev.next.next != null) {
prev = prev.next;
}
T value = prev.next.value;
prev.next = null;
size--;
return value;
}
}
public T remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Invalid index");
}
if (index == 0) {
return removeFirst();
} else if (index == size - 1) {
return removeLast();
} else {
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
Node nodeToRemove = prev.next;
prev.next = nodeToRemove.next;
size--;
return nodeToRemove.value;
}
}
public T get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Invalid index");
}
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.value;
}
public void set(int index, T value) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Invalid index");
}
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
current.value = value;
}
public boolean contains(T value) {
Node current = head;
while (current != null) {
if (current.value.equals(value)) {
return true;
}
current = current.next;
}
return false;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("LinkedList: [");
Node current = head;
while (current != null) {
builder.append(current.value);
if (current.next != null) {
builder.append(" -> ");
}
current = current.next;
}
builder.append("]");
return builder.toString();
}
}
该链表实现包含了一些常用的操作，如获取大小、判断是否为空、在头部和尾部插入元素、在指定位置插入元素、删除头部和尾部元素、删除指定位置的元素、获取指定位置的元素、设置指定位置的元素、判断是否包含指定元素等。
栈
栈是一种先进后出（Last-In-First-Out，LIFO）的数据结构，类似于一叠盘子。在Java中，可以使用数组或链表实现栈。以下是一个使用Java实现的基于链表的栈示例：
public class LinkedListStack<T> {
private class Node {
public T value;
public Node next;
public Node(T value, Node next) {
this.value = value;
this.next = next;
}
public Node(T value) {
this(value, null);
}
public Node() {
this(null, null);
}
}
private Node top;
private int size;
public LinkedListStack() {
top = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void push(T value) {
Node node = new Node(value, top);
top = node;
size++;
}
public T pop() {
if (isEmpty()) {
throw new NoSuchElementException("Stack is empty");
}
T value = top.value;
top = top.next;
size--;
return value;
}
public T peek() {
if (isEmpty()) {
throw new NoSuchElementException("Stack is empty");
}
return top.value;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("LinkedListStack: [");
Node current = top;
while (current != null) {
builder.append(current.value);
if (current.next != null) {
builder.append(" -> ");
}
current = current.next;
}
builder.append("]");
return builder.toString();
}
}
该栈实现包含了一些常用的操作，如获取大小、判断是否为空、入栈、出栈、获取栈顶元素。
队列
队列是一种先进先出（First-In-First-Out，FIFO）的数据结构，类似于排队。在Java中，可以使用数组或链表实现队列。以下是一个使用Java实现的基于数组的队列示例：
public class ArrayQueue<T> {
private T[] data;
private int front;
private int rear;
private int size;
@SuppressWarnings("unchecked")
public ArrayQueue(int capacity) {
data = (T[]) new Object[capacity + 1];
front = 0;
rear = 0;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return front == rear;
}
public void enqueue(T value) {
if ((rear + 1) % data.length == front) {
resize(2 * getCapacity());
}
data[rear] = value;
rear = (rear + 1) % data.length;
size++;
}
public T dequeue() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
T value = data[front];
data[front] = null;
front = (front + 1) % data.length;
size--;
if (size <= getCapacity() / 4 && getCapacity() / 2 != 0) {
resize(getCapacity() / 2);
}
return value;
}
public T getFront() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
return data[front];
}
private void resize(int newCapacity) {
@SuppressWarnings("unchecked")
T[] newData = (T[]) new Object[newCapacity + 1];
for (int i = 0; i < size; i++) {
newData[i] = data[(i + front) % data.length];
}
data = newData;
front = 0;
rear = size;
}
private int getCapacity() {
return data.length - 1;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("ArrayQueue: [");
for (int i = front; i != rear; i = (i + 1) % data.length) {
builder.append(data[i]);
if ((i + 1) % data.length != rear) {
builder.append(", ");
}
}
builder.append("]");
return builder.toString();
}
}
该队列实现包含了一些常用的操作，如获取大小、判断是否为空、入队、出队、获取队首元素。
总结
本文介绍了Java中一些常用的数据结构，包括数组、链表、栈和队列，并给出了相应的实现代码。这些数据结构可以用于解决各种实际问题，在实际开发中非常有用。希望读者通过学习这些示例代码，对数据结构有更深入的理解，并能够灵活运用它们解决实际问题。
本文来自极简博客，作者：前端开发者说，转载请注明原文链接：使用Java实现数据结构
