初阶数据结构总结：顺序表、单链表、双链表、栈、队列、二叉树顺序结构
·
1. 顺序表（ArrayList）
顺序表（也叫动态数组、ArrayList）是一种简单的线性数据结构，其中的元素存储在一个连续的内存区域内，可以通过索引直接访问。顺序表支持随机访问，但在插入和删除元素时（尤其是在数组中间插入或删除），效率较低。
1.1 特点：
- 访问时间复杂度为 O(1)。
- 插入和删除时间复杂度为 O(n)。
- 固定大小数组可以扩展或缩小。
1.2 代码实现
import java.util.Arrays;
class ArrayListExample {
private int[] array;
private int size;
private static final int INITIAL_CAPACITY = 10;
public ArrayListExample() {
array = new int[INITIAL_CAPACITY];
size = 0;
}
public void add(int value) {
if (size == array.length) {
array = Arrays.copyOf(array, array.length * 2); // 动态扩容
}
array[size++] = value;
}
public int get(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
return array[index];
}
public void remove(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
System.arraycopy(array, index + 1, array, index, size - index - 1); // 移动元素
size--;
}
public int size() {
return size;
}
public static void main(String[] args) {
ArrayListExample list = new ArrayListExample();
list.add(1);
list.add(2);
list.add(3);
System.out.println("Element at index 1: " + list.get(1));
list.remove(1);
System.out.println("Size after removal: " + list.size());
}
}
2. 单链表（Singly Linked List）
单链表是由多个节点组成的线性表，每个节点包含数据和指向下一个节点的指针。单链表的最大优点是插入和删除操作可以在常数时间内完成，尤其适用于频繁的插入和删除操作。
2.1 特点：
- 插入和删除操作时间复杂度为 O(1)。
- 查找操作时间复杂度为 O(n)。
- 每个节点只包含一个指向后继节点的指针。
2.2 代码实现
class SinglyLinkedList {
private static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head;
public SinglyLinkedList() {
head = null;
}
public void add(int value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
public void remove(int value) {
if (head == null) return;
if (head.data == value) {
head = head.next;
return;
}
Node current = head;
while (current.next != null && current.next.data != value) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
}
public boolean search(int value) {
Node current = head;
while (current != null) {
if (current.data == value) {
return true;
}
current = current.next;
}
return false;
}
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.printList();
list.remove(2);
list.printList();
System.out.println("Contains 3? " + list.search(3));
}
}
3. 双链表（Doubly Linked List）
双链表是由多个节点组成的线性表，每个节点包含数据和两个指针：一个指向前驱节点，另一个指向后继节点。双链表的优点是支持双向遍历，能更方便地进行删除操作。
3.1 特点：
- 每个节点有两个指针（前驱和后继）。
- 插入和删除操作时间复杂度为 O(1)。
- 查找操作时间复杂度为 O(n)。
3.2 代码实现
class DoublyLinkedList {
private static class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
private Node head;
private Node tail;
public DoublyLinkedList() {
head = null;
tail = null;
}
public void add(int value) {
Node newNode = new Node(value);
if (tail == null) {
head = tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
}
public void remove(int value) {
if (head == null) return;
Node current = head;
while (current != null && current.data != value) {
current = current.next;
}
if (current != null) {
if (current.prev != null) {
current.prev.next = current.next;
} else {
head = current.next;
}
if (current.next != null) {
current.next.prev = current.prev;
} else {
tail = current.prev;
}
}
}
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.printList();
list.remove(2);
list.printList();
}
}
4. 栈（Stack）
栈是一种后进先出（LIFO）的数据结构，只允许在一端进行插入和删除操作，通常称为栈顶。
4.1 特点：
- 插入和删除操作时间复杂度为 O(1)。
- 访问栈内元素只能从栈顶进行。
4.2 代码实现
class Stack {
private int[] stack;
private int top;
private static final int INITIAL_CAPACITY = 10;
public Stack() {
stack = new int[INITIAL_CAPACITY];
top = -1;
}
public void push(int value) {
if (top == stack.length - 1) {
stack = Arrays.copyOf(stack, stack.length * 2); // 扩容
}
stack[++top] = value;
}
public int pop() {
if (top == -1) throw new EmptyStackException();
return stack[top--];
}
public int peek() {
if (top == -1) throw new EmptyStackException();
return stack[top];
}
public boolean isEmpty() {
return top == -1;
}
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("Top: " + stack.peek());
stack.pop();
System.out.println("Top after pop: " + stack.peek());
}
}
5. 队列（Queue）
队列是一种先进先出（FIFO）的数据结构，插入操作发生在队列尾部，删除操作发生在队列头部。
5.1 特点：
- 插入和删除操作时间复杂度为 O(1)。
- 适合处理需要按顺序处理的任务。
5.2 代码实现
class Queue {
private int[] queue;
private int front;
private int rear;
private static final int INITIAL_CAPACITY = 10;
public Queue() {
queue = new int[INITIAL_CAPACITY];
front = 0;
rear = 0;
}
public void enqueue(int value) {
if (rear == queue.length) {
queue = Arrays.copyOf(queue, queue.length * 2); // 扩容
}
queue[rear++] = value;
}
public int dequeue() {
if (front == rear) throw new NoSuchElementException();
int value = queue[front++];
return value;
}
public boolean isEmpty() {
return front == rear;
}
public static void main(String[] args) {
Queue queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println("Dequeue: " + queue.dequeue());
System.out.println("Is Empty? " + queue.isEmpty());
}
}
6. 二叉树顺序结构
二叉树是每个节点最多有两个子节点的树形数据结构，通常用于表示分层关系。在顺序结构中，二叉树的节点按数组形式存储。
6.1 特点：
- 对于一个节点
i，其左子节点的位置为2i+1，右子节点的位置为2i+2，父节点的位置为(i-1)/2。 - 高效的树结构存储方式。
6.2 代码实现
class BinaryTree {
private int[] tree;
private int size;
public BinaryTree(int capacity) {
tree = new int[capacity];
size = 0;
}
public void insert(int value) {
if (size < tree.length) {
tree[size++] = value;
} else {
System.out.println("Tree is full!");
}
}
public void printTree() {
for (int i = 0; i < size; i++) {
System.out.print(tree[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree(10);
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.printTree();
}
}
总结
这些数据结构是编程中最常见和基础的结构，掌握它们的基本实现和应用可以帮助你更好地理解和解决各种算法问题。顺序表适合随机访问，链表适合频繁的插入和删除，栈和队列则常用于处理特定顺序的数据流，而二叉树则是许多高级数据结构和算法的基础。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
3
0- 0
已为社区贡献30条内容
所有评论(0)