ArrayList和顺序表

水深无声 2023-10-05 23:39 38阅读 0赞

#### 1.线性表 ####

##### 1.1定义 #####

> 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：**顺序表、链表、栈、队列**…  
> 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是**在物理结构上并不一定是连续的**，线性表在物理上存储时，通常以**数组和链式结构**的形式存储。

![在这里插入图片描述][f93e80ee61d7425d987af4954ad9e037.png]  
![在这里插入图片描述][fa2de1feee78478cb17332051b1d646b.png]

#### 2.顺序表 ####

##### 2.1定义 #####

> 顺序表是用一段**物理地址连续**的存储单元依次存储数据元素的线性结构，**一般情况下采用数组存储**。在数组上完成 数据的增删查改。

#### 3.ArrayList ####

##### 3.1定义 #####

> ArrayList简介 在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下

![bc1bd95880b34b67b97c4d23b40cc72f.png][]

> **说明**
> 
> 1.  ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
> 2.  ArrayList实现了Cloneable接口，表明ArrayList是可以clone的 3. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
> 3.  和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者  
>     CopyOnWriteArrayList
> 4.  ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

##### 3.2ArrayList的构造 #####

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ArrayList()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>ArrayList(Collection&lt;? extends E&gt; c)</td> 
   <td>利用其他 Collection 构建 ArrayList</td> 
  </tr> 
  <tr> 
   <td>ArrayList(int initialCapacity)</td> 
   <td>指定顺序表初始容量</td> 
  </tr> 
 </tbody> 
</table>

##### 3.3ArrayList常用的使用方法 #####

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean add(E e)</td> 
   <td>尾插 e</td> 
  </tr> 
  <tr> 
   <td>void add(int index, E element)</td> 
   <td>将 e 插入到 index 位置</td> 
  </tr> 
  <tr> 
   <td>boolean addAll(Collection&lt;? extends E&gt; c)</td> 
   <td>尾插 c 中的元素</td> 
  </tr> 
  <tr> 
   <td>E remove(int index)</td> 
   <td>删除 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>boolean remove(Object o)</td> 
   <td>删除遇到的第一个 o</td> 
  </tr> 
  <tr> 
   <td>E get(int index)</td> 
   <td>获取下标 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>E set(int index, E element)</td> 
   <td>将下标 index 位置元素设置为 element</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>清空</td> 
  </tr> 
  <tr> 
   <td>boolean contains(Object o)</td> 
   <td>判断 o 是否在线性表中</td> 
  </tr> 
  <tr> 
   <td>int indexOf(Object o)</td> 
   <td>返回第一个 o 所在下标</td> 
  </tr> 
  <tr> 
   <td>int lastIndexOf(Object o)</td> 
   <td>返回最后一个 o 的下标</td> 
  </tr> 
  <tr> 
   <td>List subList(int fromIndex, int toIndex)</td> 
   <td>截取部分 list</td> 
  </tr> 
 </tbody> 
</table>

> 接下来介绍插入和删除的思路

##### 3.3.1插入算法的思路 #####

> **思路**  
> 1.如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量  
> 2.如果插入位置不合理，抛出异常  
> 3.从最后一个元素开始向前遍历到第i个位置,分别将他们向后移动一个位置  
> 4.将要插入元素填入位置i处  
> 5.表长加1

// 在 pos 位置新增元素，插入
        public void add(int pos, int data) throws PosWrongfulException{
        
            if(isFull()){
        
                System.out.println("满了");
                this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
            }
            if(pos < 0 || pos > this.useSize){
        
                System.out.println("位置不合法");
                throw new PosWrongfulException("pos位置不合法");
            }
            for (int i = this.useSize-1; i >=pos ; i--) {
        
                this.elem[i+1] = this.elem[i];
            }
            this.elem[pos] = data;
    
            this.useSize++;
    
        }

##### 3.3.2删除算法的思路 #####

> **思路**  
> 1.如果删除位置不合理，抛出异常  
> 2.取出删除元素  
> 3.从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置  
> 4.表长减1

// 删除pos位置
        public void delete(int pos, int data) throws PosWrongfulException {
        
            if (pos < 0 || pos > this.useSize) {
        
                System.out.println("位置不合法");
                throw new PosWrongfulException("pos位置不合法");
            }
            int index = this.indexOf(data);
            if (index == -1) {
        
                System.out.println("找不到该元素");
            } else {
        
                for (int i = index; i < this.useSize - 1; i++) {
        
                    this.elem[index] = this.elem[index + 1];
                }
                this.useSize--;
            }
        }
            // 查找某个元素对应的位置
        public int indexOf(int toFind) {
        
            for (int i = 0; i < this.useSize; i++) {
        
                if(this.elem[i] == toFind){
        
                    return i;
                }
            }
            return -1;
        }

##### 3.4ArrayList的遍历 #####

> ArrayList的遍历 ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

public static void main(String[] args) {
        
            List<Integer> list = new ArrayList<>();
            list.add(1);
            list.add(2);
            list.add(3);
            list.add(4);
            list.add(5);
            // 使用下标+for遍历
            for (int i = 0; i < list.size(); i++) {
        
                System.out.print(list.get(i) + " ");
            }
            System.out.println();
            // 借助foreach遍历 
            for (Integer integer : list) {
        
                System.out.print(integer + " ");
            }
            System.out.println();
            
            Iterator<Integer> it = list.listIterator();
            while(it.hasNext()){
        
                System.out.print(it.next() + " ");
            }
            System.out.println();
        }

##### 3.5ArrayList的优缺点 #####

> **优点**  
> 无需为表示表中元素之间的逻辑关系而增加额外的储存空间  
> 可以快速地存取表中任意位置的元素，即随机存取  
> **缺点**  
> 插入和删除需要移动大量元素  
> 当线性表长度变化较大时，难以确定存储空间的容量  
> 造成存储空间的"碎片"

[f93e80ee61d7425d987af4954ad9e037.png]: https://img-blog.csdnimg.cn/f93e80ee61d7425d987af4954ad9e037.png
[fa2de1feee78478cb17332051b1d646b.png]: https://img-blog.csdnimg.cn/fa2de1feee78478cb17332051b1d646b.png
[bc1bd95880b34b67b97c4d23b40cc72f.png]: https://img-blog.csdnimg.cn/bc1bd95880b34b67b97c4d23b40cc72f.png