Java集合框架的一些小知识

悠悠 2024-04-23 15:39 55阅读 0赞

**目录**

一、List和ArraysList

二、Queue和Deque

三、ArrayList和LinkList的区别与联系

四、其他相关知识

--------------------

## 一、List和ArraysList ##

?**List是一个接口，而ArrayList是List接口的一个实现类。**

ArrayList类继承并实现了List接口。   
?因此，List接口不能被构造，也就是我们说的不能创建实例对象，但是我们可以像下面那样为List接口创建一个指向自己的对象引用，而ArrayList实现类的实例对象就在这充当了这个指向List接口的对象引用。

> List<Integer> res = new ArrayList<Integer>();

![a3d9f93b144a42b796b49c34e95aaa58.png][]

![efedf47909e248c8b317925063b2da35.png][]

?**List a=new ArrayList();**

> ?则a拥有List的所有属性和方法，不会拥有其实现类ArrayList的独有的属性和方法。
> 
> **a只能调用类ArrayList中重写List类的抽象方法**

> ?如果List与ArrayList中有**相同的属性(如int i),有相同的方法(如void f()),**
> 
> 则a.i是调用了List中的i，**成员变量不会被重写**
> 
> **a.f()是调用了ArrayList中的f();——因为list中的成员方法f()在ArraysList中进行了重写**

--------------------

## 二、Queue和Deque ##

?**Queue和Deque是接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口**

> **Queue<Integer> q = new LinkedList<>()**

![30f8225bad1a4309a16e931c9114bb2b.png][]

*  add 增加一个元素
 *  offer 添加一个元素并返回true 如果队列已满，则返回false
 *  remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
 *  poll 移除并返问队列头部的元素 如果队列为空，则返回null
 *  element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
 *  peek 返回队列头部的元素 如果队列为空，则返回null

--------------------

> **Deque<TreeNode> stack = new LinkedList<TreeNode>();**

**Deque的一些方法**

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>头部</th> 
   <th></th> 
   <th>尾部</th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>当操作失败时</td> 
   <td>抛出异常</td> 
   <td>false或null</td> 
   <td>抛出异常</td> 
   <td>false或null</td> 
  </tr> 
  <tr> 
   <td>插入</td> 
   <td>addFirst(e)</td> 
   <td>offerFirst(e)</td> 
   <td>addLast(e)</td> 
   <td>offerLast(e)</td> 
  </tr> 
  <tr> 
   <td>删除</td> 
   <td>removeFirst()</td> 
   <td>offerFirst()</td> 
   <td>removeLast()</td> 
   <td>offerLast()</td> 
  </tr> 
  <tr> 
   <td>检查获取</td> 
   <td>getFirst()</td> 
   <td>peekFrist()</td> 
   <td>getLast()</td> 
   <td>peekLast()</td> 
  </tr> 
 </tbody> 
</table>

![2ab9dc460c7d4a4e9baea5cd0a01b573.png][]

![ce7dfa7bfb7046e8a4d220fe4e9f3cea.png][]

![5736134c0f1d43d6b810af5fd3ae02fa.png][]![4bb890f7948942759fd95de14847fd38.png][]

--------------------

## 三、ArrayList和LinkList的区别与联系 ##

> **List：是一个接口，规范了ArrayList 和 LinkedList中要实现的方法  
> ArrayList：实现了List接口，底层为动态类型顺序表  
> LinkedList：实现了List接口，底层为双向链表**  
>

1. ArrayList的实现是基于数组，LinkedList的实现是基于双向链表。

2. **对于随机访问，ArrayList优于LinkedList ,** ArrayList可以根据下标以O(1)时间复杂度对元素进行get()随机访问。而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起，在这种情况下，随机访问某个元素的时间复杂度是O(n)

3. **对于插入和删除操作，LinkedList优于ArrayList，**因为当元素被添加到LinkedList任意位置的时候，**不需要像ArrayList那样重新计算大小或者是更新索，但LinkedList在中间插入数据时间复杂度是O（n）**

4. LinkedList比ArrayList更占内存，因为**LinkedList的节点除了存储数据，还存储了两个引用**，一个指向前一个元素，一个指向后一个元素。

时间复杂度的分析

**对于查找indexOf()，ArrayList时间复杂度是O（n）。LinkedList也是O(n)**

> ArrayList 是线性表（数组）  
> get() 直接读取第几个下标，复杂度 O(1)  
> add(E) 添加元素，直接在后面添加，复杂度O（1）  
> add(index, E) 添加元素，在第几个元素后面插入，后面的元素需要向后移动，复杂度O（n）  
> remove（）删除元素，后面的元素需要逐个移动，复杂度O（n）  
>   
> LinkedList 是链表的操作  
> get() 获取第几个元素，依次遍历，复杂度O(n)  
> add(E) 添加到末尾，复杂度O(1)  
> add(index, E) 添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n)  
> remove（）删除元素，直接指针指向操作，复杂度O(1) （*此处描述不严谨）*

--------------------

## 四、其他相关知识 ##

**?上一张图总结一些**

![908d2e0cab35441cbc4fcb0221419b67.png][]

![8354fd7d1a24457aad31ffa6460417bc.png][]

**?一些简单的解释和说明**

>  *  **1. Collection：是一个接口，包含了大部分容器常用的一些方法**
>  *  
>  *  **2. List：是一个接口，规范了ArrayList 和 LinkedList中要实现的方法**
>  *   **ArrayList：实现了List接口，底层为动态类型顺序表**
>  *   **LinkedList：实现了List接口，底层为双向链表**
>  *  
>  *  **3. Stack：底层是栈，栈是一种特殊的顺序表**
>  *  
>  *  **4. Queue：底层是队列，队列是一种特殊的顺序表**
>  *   **Deque：是一个接口**
>  *  
>  *  **5. Set：集合，是一个接口，里面放置的是K模型**
>  *   **HashSet：底层为哈希桶，查询的时间复杂度为O(1)**
>  *   **TreeSet：底层为红黑树，查询的时间复杂度为O( ),关于key有序的**
>  *  
>  *  **6. Map：映射，里面存储的是K-V模型的键值对**
>  *   **HashMap：底层为哈希桶，查询时间复杂度为O(1)**
>  *   **TreeMap：底层为红黑树，查询的时间复杂度为O( )，关于key有序**

**来张图总结一下**

![593b001d9f034803b0170c778ff02b09.png][]

[a3d9f93b144a42b796b49c34e95aaa58.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/efb4f536a4e14692bc3bb57ebe6bb530.png
[efedf47909e248c8b317925063b2da35.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e1ac4a0eb86a46ee91d28bdb8754fd22.png
[30f8225bad1a4309a16e931c9114bb2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/9b19382172964b5faa0745790bf0a308.png
[2ab9dc460c7d4a4e9baea5cd0a01b573.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c65f402143064b65b89796e7fdffdbef.png
[ce7dfa7bfb7046e8a4d220fe4e9f3cea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/83d6025fcb7e405c89160c03eb61cc84.png
[5736134c0f1d43d6b810af5fd3ae02fa.png]: https://img-blog.csdnimg.cn/5736134c0f1d43d6b810af5fd3ae02fa.png
[4bb890f7948942759fd95de14847fd38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e4a871c50623460bb82b105950003e7a.png
[908d2e0cab35441cbc4fcb0221419b67.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d9c8abdebfac4059bc130ab4c55090df.png
[8354fd7d1a24457aad31ffa6460417bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/687acffcd4f44078818c67146c4a61e4.png
[593b001d9f034803b0170c778ff02b09.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e84882e8deab4ed88095f6cb149992ab.png