本文共 12383 字，大约阅读时间需要 41 分钟。

1、概念

1.1 Java

Java一般用来做服务器开发

拿一个淘宝网站举例子： 本质上我们所看到的网页， 是一些数据的集合 我们在我们的电脑上看到这些数据， 都是从淘宝服务器获得的。

Java代码 .java - .class – 根据。Class文件产生的对象才是实际有意义的

数据存储在数据库MySql 管控数据（外存）

Java本质工作核心： 攒数据

Java要不要临时存储数据

// java为了更好更优秀的处理数据（不在完全通过我们手动操作）java提供了一些class-----》 java的集合类

java 最终怎么临时存储数据 = 数组 + 对象

1.2 数据结构和JAVA有什么关系?

（数据结构在JAVA上的表现） 数据结构本身和JAVA没有任何关系, 只不过JAVA中有多种集合、数组、等集合性质的多对象存储结构, 有时候我们希望更便捷,更具有逻辑性的操作这些集合或者数组数据 所以,我们根据数据结构的组织方式, 构建了一些特殊的JAVA集合类 用于描述了一些JAVA对象的底层数据的组成关系

Java的集合类底层组织数据的方式， 是参照某些数据结构（逻辑、思想）来进行的。 Java需要临时存储数据， --》 提供集合类 —》 数组 + 链表

1.3 数据结构的种类和JAVA中的集合类别有哪些?

数据结构： 抽象概念/逻辑概念

集合： 一堆数据 线性表： 有序的序列（操作受限的线性表： 栈：先进后出 队列： 先进先出） Y = ax + b 树： 一对多的数据关系， 国家， 族谱 图： 多对多的关系： 理论层级 集合类分类: 1, Collection 2, Map

1. 为什么需要集合类？
   很多情况下，我们需要对一组对象进行操作。而且很可能事先并不知道到底有多少个对象。为了解决这个问题呢，Java 就提供了集合类供我们使用。(存储更多类型问题, 扩容问题, 内存空间浪费问题, 数据查找问题, 数据删除问题等等)
2. 集合类的特点： a. 只能存储引用数据类型 b. 可以自动地调整自己的大小
3. 数组和集合类都是容器，它们有何不同？
   a. 数组可以存储基本数据类型的数据，集合不可以。
   b. 数组的长度是固定的，集合可以自动调整自己的大小。
   c. 数组的效率高，相对来说集合效率比较低。
   d. 数组没有API，集合有丰富的API。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 公式：数据结构=数据+结构

数据结构用来抽象的描述数据的组织关系 数据：用类型表示 结构：在任何问题中，数据元素都不是孤立存在的，它们之间都存在着某种关系，这种数据元素相互之间的关系称为结构。 元素之间，通常有以下四种基本结构： 集合 线性结构 树形结构 图结构 前面分类中定义的关系，描述的是数据元素间的逻辑关系，因此又称为逻辑结构。 但是仅仅知道数据元素间的逻辑关系是不够的，因为我们得实现自己的数据结构。

我们需要用具体的java代码, 来模拟或者来表示数据结构

因此，我们得关注数据结构在计算机底层是如何表示的？ 数据结构在计算机中的表示，称为数据的物理结构，又称为存储结构或者映像。 结构的表示可以分为两种：顺序存储结构 (顺序映像) 和 链式存储结构 (非顺序映像)。 顺序映像：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。(数组) 非顺序映像：借助指示元素存储地址的”指针”，来表示数据元素的逻辑关系。(链表)

2 数组

2.1 数组

Q1: 数组我们都很熟悉，那你理解的数组是什么样的呢？它的最主要特点是什么呢？

数组是连续存储 -->随机访问 Q2: 为什么数组的索引是一般都是从0开始的呢？ 第一个层面: 历史遗留问题. 硬件资源, 上世纪40-50年代 微型机, 存储数据 第二个层面: 方便计算. (下标-1) * 单个元素空间 + 基础位置 Q3: 为什么数组的效率比链表高？ 链表: 链表是非连续存储, 如果查找一个元素需要一步一步遍历 数组: 是连续存储, 可以根据下标一步计算出存储位置

2.2 数组的操作

2.2.1 数组的基本操作

(1)添加 (保证元素的顺序)

最好情况：O(1) 最坏情况：移动n个元素，O(n) 平均情况：移动 n/2 个元素，O(n) (2) 删除 (保证元素的顺序) 最好情况：O(1) 最坏情况：移动n-1个元素，O(n) 平均情况：移动(n-1)/2个元素，O(n) (3)查找 a. 根据索引查找元素：O(1) b. 查找数组中与特定值相等的元素 ①大小无序：O(n) ②大小有序：O(log2n) (4)总结 数组: 添加和删除慢 o(n) 查找快: 尤其根据下标查找 -->大小有序的折半查找

3 链表

3.1 什么是链表

Java中什么是链表, 一个对象持有另一个对象的引用, 另一个对象持有之后的一个对象的引用,…… 构成一个链表

Java的角度，链表的本质: 是java对象的相互持有和引用

Node zs = new Node("zs", null);Node ls = new Node("ls", null);Node wu = new Node("wu", null);Node zl = new Node("zl", null);zs.next = ls;ls.next = wu;wu.next = zl;

得到一个链表如下：zs -> ls ->wu ->zl

形象地说，链表就是用一串链子将结点串联起来。 结点：包含数据域和指针域。 数据域：数据 指针域：下一个结点的地址

3.2 链表的分类

（1）单链表: 在链表中的每一个节点, 都有一个子结点, (尾结点没有子结点)

（2）循环单链表: 单链表的改进, 让单链表的尾结点的下一个结点, 指向头结点

（3）双向链表: 双向链表也是单链表的改进, 让结点不仅可以指向之后的元素, 也可以指向之前的元素

（4）双向循环链表: 双向链表的一个改进, 头元素的之前指向尾元素, 尾元素的之后指向头元素

3.3 单链表操作

单链表：

（1）单链表操作: 查找o(n), 添加和删除o(1)

3.4 双向链表的操作

双向链表操作:查找o(n), 添加和删除o(1)

（1）很容易验证，前面那些操作，双向链表和单链表的时间复杂度是一样的。那为什么在工程上，我们用的一般是双向链表而不是单链表呢？

因为在实际操作过程中, 双向链表根据下标查找的效率, 是高于单链表.

--> 隐性的结论, 在实际工作中, 根据下标查找这个操作相对添加和删除比较频繁

思想: 用空间换时间

（2）求链表的中间元素 判断链表中是否有环(circle)

public class Ex1 {
       public static void main(String[] args) {
           Node1 node1 = new Node1("1", null);        Node1 node2 = new Node1("2", node1);        Node1 node3 = new Node1("3", node2);        Node1 node4 = new Node1("4", node3);        Node1 node5 = new Node1("5", node4);        Node1 node6 = new Node1("6", node5);        Node1 node7 = new Node1("7", node6);        // 7 -- 6 --5  --4  --3  --2  --1        // 快慢指针:        Node1 f = node7;// 快指针        Node1 l = node7;// 慢指针        // 判断快指针的下一个元素, 以及下下个元素, 是不是null, 不是null向后继续移动        while (f.next != null && f.next.next != null){
               f = f.next.next;// 移动两步            l = l.next; // 移动一步        }        // f接近于于尾部的时候, 跳出上述循环        System.out.println(l.value);    }}class Node1{
       String value;    Node1 next;    public Node1(String value, Node1 next) {
           this.value = value;        this.next = next;    }}

（3）反转单链表

public class Ex2 {
       public static void main(String[] args) {
           Node2 node1 = new Node2("1", null);        Node2 node2 = new Node2("2", node1);        Node2 node3 = new Node2("3", node2);        Node2 node4 = new Node2("4", node3);        Node2 node5 = new Node2("5", node4);        Node2 node6 = new Node2("6", node5);        Node2 node7 = new Node2("7", node6);        // 7 -- 6 --5  --4  --3  --2  --1        node1.next = node5;        Node2 f = node7;        Node2 l = node7;        while (f.next != null && f.next.next != null){
               f = f.next.next;            l = l.next;            if (f == l){
   // 快指针和慢指针相遇, 必定意味着有环                break;            }        }        if (f.next != null && f.next.next != null){
               System.out.println("有环");        } else {
               System.out.println("没有环");        }    }}class Node2{
       String value;    Node2 next;    public Node2(String value, Node2 next) {
           this.value = value;        this.next = next;    }}

3.5 使用链表/数组实现一个线性表

自己手动实现一个集合类

这个集合类: 从集合类使用的角度: 就是一个数据容器(添加, 删除, 查找)

底层结构: 链表

数据结构角度: 模拟一个线性表

线性表: 有序序列: 一个序列除了头尾元素以外, 每一个元素都有唯一的前驱和后继

---->线性表一般伴随着有序, 伴随着可以通过下标操作

public class MyLinked {
       private Node head; // 这个集合类底层所维护链表的头结点    private  int size; // 用来标记这个链表/集合类存储了多少数据    public boolean add(String str){
   //        if (str == null) throw new IllegalArgumentException("parame is null");        // 原本的链表是否为空//        if (head == null || size == 0){}        if (size == 0){
               // 意味着 链表为空, 新添加的元素, 作为头结点            head = new Node(str, null);            size++;            return true;        }        // 链表原本不空        // 添加到尾部: 先找到尾部        Node mid = head; // 用mid标记遍历结点, 最终找到尾结点        while (mid.next != null){
               mid = mid.next;        }        // mid.next == null : mid是原链表的尾结点        mid.next = new Node(str, null);        size++;        return true;    }    public boolean remove(String str){
           if (size == 0) throw new RuntimeException("linked is empty");        if (str == null){
               // 如皋要删除的元素是null, ==比较            if (str == head.value){
                   // 判断头结点是不是我们要删除的元素                head = head.next;                size--;                return true;            }            // 删除不是头结点            Node mid = head;            // mid的下一个元素不是null            // mid的下一个元素 存储的值也不是要找的            while (mid.next != null && str != mid.next.value ){
                   mid = mid.next;// mid向后遍历            }            // 两种结果            // 1, 没找到, mid.next == null            // 2, 找到了,            if (mid.next == null){
                   // 没找到                return false;            }            // 找到了, 要删除的是mid的next            mid.next = mid.next.next;// 删除mid的next            size--;            return true;        }else {
               // 如果要删除的元素不是null, equals比较            if (str.equals(head.value)){
                   // 判断头结点是不是我们要删除的元素                head = head.next;                size--;                return true;            }            // 删除不是头结点            Node mid = head;            // mid的下一个元素不是null            // mid的下一个元素 存储的值也不是要找的            while (mid.next != null && !str.equals(mid.next.value) ){
                   mid = mid.next;// mid向后遍历            }            // 两种结果            // 1, 没找到, mid.next == null            // 2, 找到了,            if (mid.next == null){
                   // 没找到                return false;            }            // 找到了, 要删除的是mid的next            mid.next = mid.next.next;// 删除mid的next            size--;            return true;        }    }    public boolean contains(String str){
           if (isEmpty()) throw new RuntimeException("linked is empty");        if (str == null){
               // 如皋要查找的元素是null, ==比较            if (str == head.value){
                   // 头结点就是要查找的结点                return true;            }            // 删除不是头结点            Node mid = head;            // mid的下一个元素不是null            // mid的下一个元素 存储的值也不是要找的            while (mid.next != null ){
                   mid = mid.next;// mid向后遍历                if (mid.value == str){
                       // 判断遍历过程中的元素, 是否要查找的元素                    return true;                }            }        } else {
               // 如果要查找的元素不是null, equals比较            if (str.equals(head.value)){
                   // 头结点就是要查找的结点                return true;            }            // 删除不是头结点            Node mid = head;            // mid的下一个元素不是null            // mid的下一个元素 存储的值也不是要找的            while (mid.next != null ){
                   mid = mid.next;// mid向后遍历                if (str.equals(mid.value)){
                       // 判断遍历过程中的元素, 是否要查找的元素                    return true;                }            }        }        return false;    }    public  boolean set(String oldValue, String newValue){
           if (isEmpty()) throw new RuntimeException("linked is empty");        //        if (oldValue == null){
               // 要替换的值是null            Node mid = head;            // 如果遍历的结点不是null, 并且这个结点存储的值也不是null            // 接着向后遍历            while (mid != null && oldValue != mid.value){
                   mid = mid.next;            }            // 1, mid == null: 没有            // 2, oldValue == mid.value: 找到了mid就是要改变的结点            if (mid == null){
   // 就没有这个旧值                return false;            }            // 有            mid.value = newValue;            return true;        }else {
               // 要替换的值不是null            Node mid = head;            // 如果遍历的结点不是null, 并且这个结点存储的值也不是要替换的结点            // 接着向后遍历            while (mid != null && !oldValue.equals(mid.value)){
                   mid = mid.next;            }            // 1, mid == null: 没有            // 2, oldValue == mid.value: 找到了mid就是要改变的结点            if (mid == null){
   // 就没有这个旧值                return false;            }            // 有            mid.value = newValue;            return true;        }    }    // 增删改查    // 增删查    // 改:    /**     * 实现一个添加方法     * @param index : 要添加的位置     * @param str : 要添加的内容     * @return : 是否添加成功     */    public boolean add(int index, String str){
           // 判断给的下标是否合法        if (index < 0 || index > size) throw new IllegalArgumentException("size = " + size );        // zs -  ls - wu - zl        // 头结点: index = 0        if (index == 0){
   // 添加的位置就是头结点            head = new Node(str, head);            size++;            return true;        }        // 添加的不是头位置        int tag = 1; // 位置标记        Node mid = head;        while (tag != index){
               mid = mid.next;            tag++;        }        // zs  ls  wu  zl        // mid代表要添加位置的之前        mid.next = new Node(str, mid.next);        size++;        return true;    }    public String remove(int index){
           // 判断给的下标是否合法        if (index < 0 || index >= size) throw new IllegalArgumentException("size = " + size );        // 删除是头元素        if (index == 0){
               String oldValue = head.value;            head = head.next;            size--;            return oldValue;        }        // 删除的不是头元素        int tag = 1; // 位置标记        Node mid = head;        while (tag != index){
               mid = mid.next;            tag++;        }        // mid 删除元素前一个        String oldValue = mid.next.value;        // 删除        mid.next = mid.next.next;        size--;        return oldValue;    }    /**     * 查找方法: 根据下标查找这个下标所对应存储的内容     * @param index : 提供的下标     * @return :  返回的内容     */    public String get(int index){
           // 判断给的下标是否合法        if (index < 0 || index >= size) throw new IllegalArgumentException("size = " + size );        int tag = 0;        Node mid = head;        while (tag != index){
               mid = mid.next;            tag++;        }        //mid 就是要查找的位置        return mid.value;    }//        myLinked.add(i, str);//        myLinked.remove(i);//        myLinked.get(i);// 根据下标获取这个下标的元素内容    /**     * 根据下标替换新内容     * @param index     * @param newValue     * @return     */    public String set(int index, String newValue){
           // 判断给的下标是否合法        if (index < 0 || index >= size) throw new IllegalArgumentException("size = " + size );        int tag = 0;        Node mid = head;        while (tag != index){
               mid = mid.next;            tag++;        }        // mid 就是你给定的查找位置        String value = mid.value;        mid.value = newValue;        return value;    }    // 判断这个集合类存储的数据是否为空    public boolean isEmpty(){
           return size == 0;    }    public int size(){
           return size;    }    class Node{
           String value;        Node next;        public Node(String value, Node next) {
               this.value = value;            this.next = next;        }    }}

转载地址：https://blog.csdn.net/weixin_43510391/article/details/116211295 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！