1.Java算法中常用的数据结构

淩亂°似流年 2022-10-22 15:56 193阅读 0赞

### Java算法中常用的数据结构 ###

*  1. Java算法中常用的数据结构
 *   *  1.1 写在前面的话
     *  1.2 Java算法中常用的数据结构
     *   *  1.2.1 数组
         *  1.2.2 字符串 String
         *  1.2.3 动态数组ArrayList
         *  1.2.4 双向链表 LinkedList
         *  1.2.5 哈希表 HashMap
         *  1.2.6 哈希集合 HashSet
         *  1.2.7 队列 Queue
         *  1.2.8 堆栈 Stack
         *  1.2.9 二叉树
         *  1.2.10 单链表

# 1. Java算法中常用的数据结构 #

## 1.1 写在前面的话 ##

大家好，我是技术宅星云，这篇文章给大家分享下java算法中常用的数据结构。

我们都知道, Java 是一个面向对象的高级语言, 它内置了几种常用的数据结构类型，像我们大学C语言基础课程中所学到的 数组(array), 链表（list）, 队列（Queue ），栈（stack）等。

但在Java中，万事万物皆为对象，为了更方便，更简单容易地使用这些数据结构，Java 又将这几种内置的数据结构封装成了类（比如ArrayList,HashMap,LinkedList 等），屏蔽了底层实现的复杂性。

也许对于初级和中级工程师来说，只需要会调用这些封装好的数据结构类即可，但是对于高级工程师来说，却应该去了解下这些内置的数据结构，这样的好处是可以知其然并知其所以然。

在一些比较复杂的业务场景下，如果我们对这些数据结构类的底层实现有所了解，将有助于我们更好更恰当地使用这些数据结构。

## 1.2 Java算法中常用的数据结构 ##

>  *  1.2.1 数组
>  *  1.2.2 字符串
>  *  1.2.3 动态数组
>  *  1.2.4 双向链表 LinkedList
>  *  1.2.5 哈希表 HashMap
>  *  1.2.6 哈希集合 HashSet
>  *  1.2.7 队列 Queue
>  *  1.2.8 堆栈 Stack
>  *  1.2.9 二叉树
>  *  1.2.10 单链表

### 1.2.1 数组 ###

初始化方法

int m=5,n=10;
    
    // 初始化一个大小为10的int数组
    // 其中的值默认初始化为0
    int[] nums=new int[n];
    
    // 初始化一个m*n的二维布尔数组
    // 其中的元素默认初始化为false
    boolean[][] visited=new boolean[m][n];

Java中的这种数组类似C语言中的数组，在有的题目中会以函数参数的形式传，一般来说要在函数开头做一个非空检查，然后用索引下标访问其中的元素。

if(nums.length==0){ 
        return ;
    }
    
    for(int i=0;i<nums.length;i++){ 
    // 访问nums[i]
    }

### 1.2.2 字符串 String ###

Java的字符串处理起来很麻烦，因为它不支持用\[\]直接访问其中的字符，而且不能直接修改，要转换成char\[\]类型后才能修改。

String s1="hello world";
    char c=s1.charAt(2);
    
    char[] chars=s1.toCharArray();
    chars[1]='a';
    String s2=new String(chars);
    // 输出 hallo world
    System.out.println(s2);
    
    // 注意，一定要用equals 方法判断字符串是否相同
    if(s1.equals(s2)){ 
        // s1 和s2 相同
    }else{ 
       // s1 和s2 不相同
    }

字符串可以用加号进行拼接

String s3=s1+"!";
    // 输出 hello world!
    System.out.println(s3);

Java的字符串不能直接修改，要用toCharArray 转化成char\[\]类型的数组后进行修改，然后转换回String类型。

另外，虽然字符串支持用+进行拼接，但是效率并不高，不建议在for循环中使用。如果需要进行频繁的字符串拼接，推荐单线程环境下使用`StringBuilder`，多线程环境下使用`StringBuffer`.

StringBuilder sb=new StriingBuilder();
    
    for(char c='a'; c<'f';c++){ 
         sb.append(c);
    }
    // append 方法支持拼接字符，字符串数字等类型。
    sb.append('g').append('hij').append(123);
    
    String res=sb.toString();
    // 输出：abcdefghij123
    System.out.println(res);

### 1.2.3 动态数组ArrayList ###

类似C++ 的vector 容器，ArrayList 相当于把Java内置的数组类型做了包装初始化方法：

// 初始化一个存储String类型数据的动态数组
    ArrayList<String> nums=new ArrayList<>();
    
    // 初始化一个存储int类型数据的动态数组
    ArrayList<Integer> strings=new ArrayList<>();

> 值得注意的是，如果我们看过源码了解ArrayList 使用内置数据结构的代码封装逻辑，就会明白，在初始化的时候如果知道会存多少条数据，那么最好指定下初始化扩容大小，避免代码运行过程中频繁调整数组大小，造成额外开销。

上面代码优化后就变成了这样：

// 初始化一个存储String类型数据的动态数组
    ArrayList<String> nums=new ArrayList<>(16);
    
    // 初始化一个存储int类型数据的动态数组
    ArrayList<Integer> strings=new ArrayList<>(16);

**ArrayList 默认初始化大小是10.** 这个值最好根据实际情况设值。

> **常用方法（E 代表元素类型）**：
> 
>  *  // 判断数组是否为空  
>     `boolean isEmpty()`
>  *  // 返回数组中元素的个数  
>     `int size();`
>  *  // 返回索引index的元素  
>     `E get(int index)`
>  *  // 在数组尾部添加元素e  
>     `boolean add(E e)`

### 1.2.4 双向链表 LinkedList ###

ArrayList 列表底层是用数组实现的，而LinkedList 底层是用双链表实现的，初始化方法也是类似的，初始化方法也是类似的。

// 初始化一个存储int类型的数据的双向链表
    LinkedList<Integer> nums=new LinkedList<>();
    
    // 初始化一个存储String类型数据的双向链表
    LinkedList<String> strings=new LinkedList<>();
    
    //判断链表是否为空
    boolean isEmpty();
    
    // 返回链表中元素的个数
    int size();
    
    // 判断链表中是否存在元素o
    boolean contains(Object o);
    
    // 在链表尾部添加元素e
    void add(E e);
    
    // 在链表头部添加元素
    void addFirst(E e);
    
    // 删除链表头部第一个元素
    E removeFirst();
    
    // 删除链表尾部最后一个元素
    E removeLast();

> 其中只有contains 方法的时间复杂度是O(N),因为必须遍历整个链表才能判断元素是否存在。

### 1.2.5 哈希表 HashMap ###

初始化方法

// 整数映射到字符串的哈希表
    HashMap<Integer,String> map=new HashMap<>();
    
    // 字符串映射到数组的哈希表
    HashMap<String,int[]> map=new HashMap<>();

K 代表键的类型，V代表值的类型。

// 判断哈希表中是否存在键key
    boolean containsKey(Object key);
    // 获得键key对应的值 若值不存在，则返回null
    V get(Object key);
    // 将key和value键值对存入哈希表
    V put(K key,V value);
    // 如果key存在删除key 并返回对应的值
    V remove(Object key);
    // 获得key 的值，如果key不存在则返回defaultValue
    V getOrDefault(Object key,V defualtValue);
    
    // 获得哈希表中的所有key
    Set<K> keySet();
    
    // 如果key不存在，则将键值对key 和value 存入哈希表
    V putIfAbsend(K key,V value);

### 1.2.6 哈希集合 HashSet ###

Set<String> set= new HashSet<>();
    
    // 如果e 不存在则将e 添加到哈希集合
    boolean add(E e);
    
    // 判断元素 o 是否存在于哈希集合中
    boolean contains(Object o);
    
    // 如果元素o存在，则删除元素o
    boolean remove(Object o);

### 1.2.7 队列 Queue ###

Queue 是一个接口,比如新建一个存储String的队列如下：

// 新建一个存储String的队列
    Queue<Stirng> q=new LinkedList<>();
    
    // 判断队列是否为空
    boolean isEmpty();
    
    // 返回队列中元素的个数
    E peek();
    
    // 删除并返回队头的元素
    E poll();
    
    // 将元素e 插入队尾
    boolean offer(E e);

### 1.2.8 堆栈 Stack ###

Stack<Integer> s=new Stack<>();
    
    // 判断堆栈是否为空
    boolean isEmpty();
    
    // 返回堆栈中元素的个数
    int size();
    
    // 将元素压入栈顶
    E push(E item);
    
    // 返回栈顶元素
    E peek();
    
    // 删除并返回栈顶元素
    E  pop();

### 1.2.9 二叉树 ###

在Java中，如果想定义一个二叉树，那么需要编码如下：

public class TreeNode{ 
       /** * 节点存储的值 */
       int val;
       /** * 指向左侧子节点的指针 */
       TreeNode left;
      /** * 指向右侧子节点的指针 */
       TreeNode right;
       /** * 构造函数 */
       TreeNode(int val){ 
           this.val=val;
           this.left=null;
           this.right=null;
       }
    }

一般的使用方法是：

TreeNode node1=new TreeNode(2);
    TreeNode node2=new TreeNode(4);
    TreeNode node3=new TreeNode(6);
    node1.val=10;
    node1.left=node2;
    node1.right=node3;

以上操作图形化示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhZHVlcw_size_16_color_FFFFFF_t_70]

> 注意：其中2 是根节点存储的值，4 是左子树节点的值，6 是右子树节点的值。  
> 根据node1.val=10; 命令执行后便将根结点的值从2 变成了10.

### 1.2.10 单链表 ###

ListNode 是单链表节点类型，其结构定义如下：

class ListNode{ 
        int val;
        ListNode next;
        ListNode(int val){ 
            this.val=val;
            this.next=nul;
       }
    }

一般的使用用法是：

ListNode node1=new ListNode(1);
    ListNode node2=new ListNode(2);
    ListNode node3=new ListNode(3);
    node1.val=9;
    node2next=node3;
    node1next=node2;

以上代码图形化示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhZHVlcw_size_16_color_FFFFFF_t_70 1]

> node1.val=9; 将 根结点的值从1 变成了9

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhZHVlcw_size_16_color_FFFFFF_t_70]: /images/20221022/4d80c156b2fb46bd9aa33c5fc05fa036.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhZHVlcw_size_16_color_FFFFFF_t_70 1]: /images/20221022/61009d32850249778b6c63d506fe5756.png