首页 > 编程语言 >「Java 数据结构全面解读」:从基础到进阶的实战指南

「Java 数据结构全面解读」:从基础到进阶的实战指南

时间:2025-01-05 14:02:58浏览次数:3  
标签:null Java 进阶 System println 数据结构 my public out

「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):最后插入的元素最先被移除。
  • 栈只是逻辑结构,其物理结构可以是数组,也可以是链表,即栈结构分为顺序栈和链式栈。
  • 核心类库中的栈结构有 StackLinkedListStack 就是顺序栈,它是 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 操作外,队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式:一种抛出异常(操作失败时),另一种返回一个特殊值(nullfalse,具体取决于操作)。Queue 实现通常不允许插入 null 元素,即使在允许 null 的实现中,也不应该将 null 插入到队列中,因为 null 也用作某些方法的特殊返回值,表明队列不包含元素。

抛出异常返回特殊值
插入add(e)offer(e)
移除remove()poll()
检查element()peek()
双端队列(Deque)

Deque,名称 deque 是“double ended queue(双端队列)”的缩写,通常读为“deck”。此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式:一种形式在操作失败时抛出异常,另一种形式返回一个特殊值(nullfalse,具体取决于操作)。Deque 接口的实现类有 ArrayDequeLinkedList,它们一个底层是使用数组实现,一个使用双向链表实现。

第一个元素(头部)最后一个元素(尾部)
抛出异常特殊值抛出异常特殊值
插入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 提供了 TreeMapTreeSet 类实现基于红黑树的有序集合。
示例代码
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
  • 有序存储:选择 TreeMapTreeSet

通过对这些数据结构的深入理解和灵活运用,可以显著提升程序的性能和可维护性。

标签:null,Java,进阶,System,println,数据结构,my,public,out
From: https://blog.csdn.net/qq_36534560/article/details/144884639

相关文章

  • java+SpringBoot+msyql教师招聘管理系统81097-计算机毕设原创(赠源码)
    目 录摘要1绪论1.1研究背景1.2研究意义1.3论文结构与章节安排2系统分析2.1可行性分析2.1.1技术可行性2.1.2经济可行性2.1.3操作可行性2.2系统流程分析2.2.1数据增加流程2.2.2数据修改流程2.2.3数据删除流程2.3系统功能分析2.3.......
  • Java 8系列之重新认识HashMap6
    摘要HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(JavaDevelopmetKit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别,深入探讨HashMap的结构实现和功能原理。简介Java......
  • (免费领源码)基于Java#SpringBoot#mysql#微信小程序的健身打卡平台的设计与实现13606-计
    摘 要随着人们健康意识的不断提高,健身已经成为一种流行的生活方式。然而,传统的健身方式往往受到时间和空间的限制,无法满足人们随时随地进行健身打卡的需求。为了解决这个问题,提出了一种基于SpringBoot微信小程序的健身打卡平台的设计与实现。本平台旨在提供一个便捷、实......
  • java&springboot&mysql社会救助信息管理系统55502-计算机毕业设计 原创(附源码)
    摘 要在网络飞速发展的信息时代,各个行业都离不开信息的处理,在这种时代背景下,社会以人们健康为导向,以社会救助信息管理系统的持续创新,根据这两点,为当前形势最重要的社会救助信息管理系统就很有必要。系统采用了B/S结构,在此基础上,对各业务模块进行了界面交互,以MySQL为数据......
  • java+springboot+mysql 药房销售系统34450-计算机定制原创毕设选题推荐(免费领源码)
    目 录摘 要ABSTRACT1.绪论1.1研究背景及意义1.2研究意义1.3国内外研究现状1.3.1国内外研究现状1.3.2国外研究现状2.相关技术2.1JAVA语言2.2SpringBoot框架2.3MySQL数据库3.系统分析3.1需求分析3.1.1员工用户功能分析3.1.2管理员功能模块......
  • Java集合 —— LinkedList详解(源码)
    在学习LinkedList之前先来了解一下链表链表概念 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序通过链表中的指针链接次序实现的 图中的1、2、3、4、5都是结构体,称为结点;结构体包含所存的数据和下一结点的地址。顺序表中的地址是连续的,而链表中......
  • C/C++调试---堆数据结构
    堆数据结构因为C/C++语言赋予程序员通过引用和指针来操纵内存对象的最大自由,所以毫不奇怪的是这些程序中的大多数bug都与错误的内存访问有关。根据错误发生的位置是栈还是堆,内存错误可分为两种:栈错误和堆错误。栈栈是分配给给一个独立的控制流(线程)的来纳许内存区域,用......
  • 28 个 JavaScript 单行代码让你成为 JavaScript 大神
    1.反转字符串constreversedString=str=>str.split('').reverse().join('');reversedString("HelloWorld");//dlroWolleH此函数获取一个字符串,将其拆分为一个字符数组,反转该数组,然后将其重新合并为一个字符串,反转原始字符串。2.标题大小写字符串consttitle......
  • [数据结构学习笔记4] 链表
    链表(LinkedLists)和数组类似,链表也是用来存放一组数据。和数组不一样的是,链表存储不需要连续的内存位置,一个链表由很多节点组成,节点与节点间通过一个next指针关联。图示:NodeValue/DataNext 链表操作:查找一个值:通过链表的next指针一直往下跳直到:1.找到了想......
  • JavaScript 观察者模式:前端开发必备技能
    一、什么是观察者模式?        观察者模式(ObserverPattern),也称为发布-订阅模式(Publish/Subscribe),定义了一种一对多的依赖关系。当一个对象(被观察对象或主题Subject)的状态发生变化时,所有依赖于它的对象(观察者Observer)都会得到通知,并自动进行相应的更新。     ......