「Java 数据结构全面解读」:从基础到进阶的实战指南
数据结构是程序设计中的核心部分,用于组织和管理数据。Java 提供了丰富的集合框架和工具类,涵盖了常见的数据结构如数组、链表、栈、队列和树等。本文将系统性地介绍这些数据结构的概念、特点以及在 Java 中的实现,并通过代码示例进行演示。
一、数据结构基础概念
数据结构研究的是数据的逻辑结构和物理结构,以及它们之间的关系。
1.1 数据的逻辑结构
数据的逻辑结构反映了数据元素之间的逻辑关系,而与存储位置无关。常见逻辑结构包括:
- 散列结构:元素之间除了“同属一个集合”外,没有其他关系。
- 线性结构:元素之间存在一对一的关系,例如数组、链表。
- 树形结构:元素之间存在一对多的关系,例如二叉树。
- 图形结构:元素之间存在多对多的关系。
1.2 数据的物理结构
数据的物理结构描述了数据在计算机内存中的存储方式,主要有:
- 数组结构:元素在内存中是连续存储的,即元素存储在一整块连续的存储空间中,此时根据索引的查询效率是非常高的,因为可以根据下标索引直接一步到位找到元素位置,如果在数组末尾添加和删除元素效率也非常高。缺点是,如果事先申请足够大的内存空间,可能造成空间浪费,如果事先申请较小的内存空间,可能造成频繁扩容导致元素频繁搬家。另外,在数组中间添加、删除元素操作,就需要移动元素,此时效率也要打折。
- 链式结构:元素在内存中是不要求连续存储的,但是元素是封装在结点当中的,结点中需要存储元素数据,以及相关结点对象的引用地址。结点与结点之间可以是一对一的关系,也可以一对多的关系,比如:链表、树等。遍历链式结构只能从头遍历,对于较长的链表来说查询效率不高,对于树结构来说,查询效率比链表要高一点,因为每次可以确定一个分支,从而排除其他分支,但是相对于数组来说,还是数组[下标]的方式更快。树的实现方式有很多种,无非就是在添加/删除效率 与 查询效率之间权衡。
- 索引结构:元素在内存中是不要求连续存储的,但是需要有单独的一个索引表来记录每一个元素的地址,这种结构根据索引的查询效率很高,但是需要额外存储和维护索引表。。
- 哈希结构:元素的存储位置需要通过其hashCode值来计算,查询效率也很多,但是要考虑和解决好哈希冲突问题。
数据结构和算法是一门完整并且复杂的课程
二、Java 中常见的数据结构实现
Java 提供了丰富的数据结构支持,包括动态数组、链表、栈、队列和树等。这些数据结构主要通过 java.util
包中的类实现。
2.1 数组
动态数组特点
逻辑结构特点:线性结构
物理结构特点:
- 申请内存:一次申请一大段连续的空间,一旦申请到了,内存就固定了。
- 存储特点:所有数据存储在这个连续的空间中,数组中的每一个元素都是一个具体的数据(或对象),所有数据都紧密排布,不能有间隔。
例如:整型数组
例如:对象数组
自定义动态数组(拓展)示例代码
package com.test.list;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MyArrayList<E> implements Iterable<E>{
private Object[] all;
private int total;
public MyArrayList(){
all = new Object[10];
}
public void add(E e) {
ensureCapacityEnough();
all[total++] = e;
}
private void ensureCapacityEnough() {
if(total >= all.length){
all = Arrays.copyOf(all, all.length + (all.length>>1));
}
}
public void insert(int index, E value) {
//是否需要扩容
ensureCapacityEnough();
//添加元素的下标检查
addCheckIndex(index);
if(total-index > 0) {
System.arraycopy(all, index, all, index+1, total-index);
}
all[index]=value;
total++;
}
private void addCheckIndex(int index) {
if(index<0 || index>total){
throw new IndexOutOfBoundsException(index+"越界");
}
}
public void delete(E e) {
int index = indexOf(e);
if(index==-1){
throw new NoSuchElementException(e+"不存在");
}
delete(index);
}
public void delete(int index) {
//删除元素的下标检查
checkIndex(index);
if(total-index-1 > 0) {
System.arraycopy(all, index+1, all, index, total-index-1);
}
all[--total] = null;
}
private void checkIndex(int index) {
if(index<0 || index>total){
throw new IndexOutOfBoundsException(index+"越界");
}
}
public void update(int index, E value) {
//更新修改元素的下标检查
checkIndex(index);
all[index] = value;
}
public void update(E old, E value) {
int index = indexOf(old);
if(index!=-1){
update(index, value);
}
}
public boolean contains(E e) {
return indexOf(e) != -1;
}
public int indexOf(E e) {
int index = -1;
if(e==null){
for (int i = 0; i < total; i++) {
if(e == all[i]){
index = i;
break;
}
}
}else{
for (int i = 0; i < total; i++) {
if(e.equals(all[i])){
index = i;
break;
}
}
}
return index;
}
public E get(int index) {
//获取元素的下标检查
checkIndex(index);
return (E) all[index];
}
public int size() {
return total;
}
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E>{
private int cursor;
@Override
public boolean hasNext() {
return cursor!=total;
}
@Override
public E next() {
return (E) all[cursor++];
}
@Override
public void remove() {
MyArrayList.this.delete(--cursor);
}
}
}
测试类
package com.test.list;
import java.util.Iterator;
public class TestMyArrayList {
public static void main(String[] args) {
MyArrayList<String> my = new MyArrayList<>();
my.add("hello");
my.add("java");
my.add("java");
my.add("world");
my.add(null);
my.add(null);
my.add("list");
my.add("data");
System.out.println("元素个数:" + my.size());
for (String s : my) {
System.out.println(s);
}
System.out.println("-------------------------");
System.out.println("在[1]插入JAVA移动技术栈后:");
my.insert(1, "JAVA移动技术栈");
System.out.println("元素个数:" + my.size());
for (String s : my) {
System.out.println(s);
}
System.out.println("--------------------------");
System.out.println("删除[1]位置的元素后:");
my.delete(1);
System.out.println("元素个数:" + my.size());
for (String s : my) {
System.out.println(s);
}
System.out.println("删除null元素后:");
my.delete(null);
System.out.println("元素个数:" + my.size());
for (String s : my) {
System.out.println(s);
}
System.out.println("------------------------------");
System.out.println("替换[3]位置的元素为JAVA移动技术栈后:");
my.update(3, "JAVA移动技术栈");
System.out.println("元素个数:" + my.size());
for (String s : my) {
System.out.println(s);
}
System.out.println("替换java为JAVA后:");
my.update("java", "JAVA");
System.out.println("元素个数:" + my.size());
for (String s : my) {
System.out.println(s);
}
System.out.println("------------------------------------");
System.out.println("是否包含java:" +my.contains("java"));
System.out.println("java的位置:" + my.indexOf("java"));
System.out.println("haha的位置:" + my.indexOf("haha"));
System.out.println("[0]位置元素是:" + my.get(0));
System.out.println("------------------------------------");
System.out.println("删除字符串长度>4的元素后:");
Iterator<String> iterator = my.iterator();
while(iterator.hasNext()) {
String next = iterator.next();
if(next != null && next.length()>4) {
iterator.remove();
}
}
System.out.println("元素个数:" + my.size());
for (String string : my) {
System.out.println(string);
}
}
}
2.2 链表
链表特点
- 数据存储在结点中,结点通过指针连接。
- 插入和删除效率高,查询效率低。
- Java 提供了
LinkedList
类实现链表,支持双向链表。
示例代码
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
System.out.println(linkedList); // 输出:[A, B, C]
}
}
2.3 栈
栈特点
- 先进后出(FILO) 或 后进先出(LIFO):最后插入的元素最先被移除。
- 栈只是逻辑结构,其物理结构可以是数组,也可以是链表,即栈结构分为顺序栈和链式栈。
- 核心类库中的栈结构有
Stack
和LinkedList
。Stack
就是顺序栈,它是Vector
的子类,而LinkedList
是链式栈。
核心操作方法
peek()
:查看栈顶元素,不弹出。pop()
:弹出栈顶元素。push(E e)
:压入栈顶。
示例代码
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println(stack.pop()); // 输出:30
System.out.println(stack.peek()); // 输出:20
}
}
自定义单链表(拓展)
package com.test.list;
import java.util.Iterator;
public class MyOneWayLinkedList<E> implements Iterable<E>{
private Node head;
private int total;
public void add(E e){
Node newNode = new Node(e, null);
if(head == null){
head = newNode;
}else{
Node node = head;
while(node.next!=null){
node = node.next;
}
node.next = newNode;
}
total++;
}
private Node[] findNodes(Object obj){
Node[] result = new MyOneWayLinkedList.Node[2];
Node node = head;
Node find = null;
Node beforeFind = null;
if(obj == null){
while(node != null){
if(node.data == null){
find = node;
break;
}
beforeFind = node;
node = node.next;
}
}else{
while(node != null){
if(obj.equals(node.data)){
find = node;
break;
}
beforeFind = node;
node = node.next;
}
}
result[0] = beforeFind;
result[1] = find;
return result;
}
public void delete(Object obj){
Node[] nodes = findNodes(obj);
Node beforeFind = nodes[0];
Node find = nodes[1];
if(find != null){
if(beforeFind == null){
head = find.next;
}else {
beforeFind.next = find.next;
}
total--;
}
}
private Node findNode(Object obj){
return findNodes(obj)[1];
}
public boolean contains(Object obj){
return findNode(obj) != null;
}
public void update(E old, E value) {
Node find = findNode(old);
if(find != null){
find.data = value;
}
}
public int size() {
return total;
}
@Override
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E>{
private Node node = head;
@Override
public boolean hasNext() {
return node != null;
}
@Override
public E next() {
E value = node.data;
node = node.next;
return value;
}
}
private class Node{
E data;
Node next;
Node(E data, Node next) {
this.data = data;
this.next = next;
}
}
}
测试类
package com.test.list;
public class TestMyOneWayLinkedList{
public static void main(String[] args) {
MyOneWayLinkedList<String> my = new MyOneWayLinkedList<>();
my.add("hello");
my.add("world");
my.add(null);
my.add(null);
my.add("java");
my.add("java");
System.out.println("一共有:" + my.size());
System.out.println("所有元素:");
for (String s : my) {
System.out.println(s);
}
System.out.println("-------------------------------------");
System.out.println("查找java,null,haha的结果:");
System.out.println(my.contains("java"));
System.out.println(my.contains(null));
System.out.println(my.contains("haha"));
System.out.println("-------------------------------------");
System.out.println("替换java,null后:");
my.update("java","JAVA");
my.update(null,"chai");
System.out.println("所有元素:");
for (String s : my) {
System.out.println(s);
}
System.out.println("-------------------------------------");
System.out.println("删除hello,JAVA,null后:");
my.delete("hello");
my.delete("JAVA");
my.delete(null);
System.out.println("所有元素:");
for (String s : my) {
System.out.println(s);
}
}
}
自定义双链表(拓展)
package com.test.list;
import java.util.Iterator;
public class MyLinkedList<E> implements Iterable<E>{
private Node first;
private Node last;
private int total;
public void add(E e){
Node newNode = new Node(last, e, null);
if(first == null){
first = newNode;
}else{
last.next = newNode;
}
last = newNode;
total++;
}
public int size(){
return total;
}
public void delete(Object obj){
Node find = findNode(obj);
if(find != null){
if(find.prev != null){
find.prev.next = find.next;
}else{
first = find.next;
}
if(find.next != null){
find.next.prev = find.prev;
}else{
last = find.prev;
}
find.prev = null;
find.next = null;
find.data = null;
total--;
}
}
private Node findNode(Object obj){
Node node = first;
Node find = null;
if(obj == null){
while(node != null){
if(node.data == null){
find = node;
break;
}
node = node.next;
}
}else{
while(node != null){
if(obj.equals(node.data)){
find = node;
break;
}
node = node.next;
}
}
return find;
}
public boolean contains(Object obj){
return findNode(obj) != null;
}
public void update(E old, E value){
Node find = findNode(old);
if(find != null){
find.data = value;
}
}
@Override
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E>{
private Node node = first;
@Override
public boolean hasNext() {
return node!=null;
}
@Override
public E next() {
E value = node.data;
node = node.next;
return value;
}
}
private class Node{
Node prev;
E data;
Node next;
Node(Node prev, E data, Node next) {
this.prev = prev;
this.data = data;
this.next = next;
}
}
}
自定义双链表测试
package com.test.list;
public class TestMyLinkedList {
public static void main(String[] args) {
MyLinkedList<String> my = new MyLinkedList<>();
my.add("hello");
my.add("world");
my.add(null);
my.add(null);
my.add("java");
my.add("java");
System.out.println("一共有:" + my.size());
System.out.println("所有元素:");
for (String s : my) {
System.out.println(s);
}
System.out.println("-------------------------------------");
System.out.println("查找java,null,haha的结果:");
System.out.println(my.contains("java"));
System.out.println(my.contains(null));
System.out.println(my.contains("haha"));
System.out.println("-------------------------------------");
System.out.println("替换java,null后:");
my.update("java","JAVA");
my.update(null,"chai");
System.out.println("所有元素:");
for (String s : my) {
System.out.println(s);
}
System.out.println("-------------------------------------");
System.out.println("删除hello,JAVA,null后:");
my.delete("hello");
my.delete("JAVA");
my.delete(null);
System.out.println("所有元素:");
for (String s : my) {
System.out.println(s);
}
}
}
2.4 队列
队列特点
队列是逻辑结构,其物理结构可以是数组,也可以是链表。队列有普通队列、双端队列、并发队列等等,核心类库中的队列实现类有很多(后面会学到很多),LinkedList
是双端队列的实现类。
Queue 除了基本的 Collection
操作外,队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式:一种抛出异常(操作失败时),另一种返回一个特殊值(null
或 false
,具体取决于操作)。Queue
实现通常不允许插入 null
元素,即使在允许 null
的实现中,也不应该将 null
插入到队列中,因为 null
也用作某些方法的特殊返回值,表明队列不包含元素。
抛出异常 | 返回特殊值 | |
---|---|---|
插入 | add(e) | offer(e) |
移除 | remove() | poll() |
检查 | element() | peek() |
双端队列(Deque)
Deque,名称 deque 是“double ended queue(双端队列)”的缩写,通常读为“deck”。此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式:一种形式在操作失败时抛出异常,另一种形式返回一个特殊值(null
或 false
,具体取决于操作)。Deque
接口的实现类有 ArrayDeque
和 LinkedList
,它们一个底层是使用数组实现,一个使用双向链表实现。
第一个元素(头部) | 最后一个元素(尾部) | |||
---|---|---|---|---|
抛出异常 | 特殊值 | 抛出异常 | 特殊值 | |
插入 | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
移除 | removeFirst() | pollFirst() | removeLast() | pollLast() |
检查 | getFirst() | peekFirst() | getLast() | peekLast() |
此接口扩展了 Queue
接口。在将双端队列用作队列时,将得到 FIFO(先进先出)行为。将元素添加到双端队列的末尾,从双端队列的开头移除元素。从 Queue
接口继承的方法完全等效于 Deque
方法,如下表所示:
**Queue** 方法 | 等效 **Deque** 方法 |
---|---|
add(e) | addLast(e) |
offer(e) | offerLast(e) |
remove() | removeFirst() |
poll() | pollFirst() |
element() | getFirst() |
peek() | peekFirst() |
双端队列也可用作 LIFO(后进先出)堆栈。应优先使用此接口而不是遗留 Stack
类。在将双端队列用作堆栈时,元素被推入双端队列的开头并从双端队列开头弹出。堆栈方法完全等效于 Deque
方法,如下表所示:
堆栈方法 | 等效 **Deque** 方法 |
---|---|
push(e) | addFirst(e) |
pop() | removeFirst() |
peek() | peekFirst() |
结论:Deque
接口的实现类既可以用作 FILO 堆栈使用,又可以用作 FIFO 队列使用。
示例代码
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
queue.add("A");
queue.add("B");
queue.add("C");
System.out.println(queue.poll()); // 输出:A
System.out.println(queue.peek()); // 输出:B
}
}
2.5 二叉树
二叉树特点
- 每个节点最多有两个子节点。
- Java 提供了
TreeMap
和TreeSet
类实现基于红黑树的有序集合。
示例代码
import java.util.TreeMap;
public class TreeMapExample {
public static void main(String[] args) {
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(1, "One");
treeMap.put(2, "Two");
treeMap.put(3, "Three");
System.out.println(treeMap); // 输出:{1=One, 2=Two, 3=Three}
}
}
普通二叉树:
public class BinaryTree<E>{
private TreeNode root; //二叉树的根结点
private int total;//结点总个数
private class TreeNode{
//至少有以下几个部分
TreeNode parent;
TreeNode left;
E data;
TreeNode right;
public TreeNode(TreeNode parent, TreeNode left, E data, TreeNode right) {
this.parent = parent;
this.left = left;
this.data = data;
this.right = right;
}
}
}
TreeMap红黑树:
public class TreeMap<K,V> {
private transient Entry<K,V> root;
private transient int size = 0;
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
}
三、总结与建议
Java 提供了对常见数据结构的完整支持,无论是基础的数组、链表,还是复杂的树、队列,都可以通过标准库轻松实现。在实际开发中,应根据场景选择合适的数据结构:
- 快速随机访问:选择
ArrayList
。 - 频繁插入和删除:选择
LinkedList
。 - 先进后出:选择
Stack
。 - 先进先出:选择
Queue
。 - 有序存储:选择
TreeMap
或TreeSet
。
通过对这些数据结构的深入理解和灵活运用,可以显著提升程序的性能和可维护性。
标签:null,Java,进阶,System,println,数据结构,my,public,out From: https://blog.csdn.net/qq_36534560/article/details/144884639