【数据结构】线性表与顺序表

野性酷女 2024-04-23 20:29 89阅读 0赞

> ⭐ 作者：小胡\_不糊涂  
> ? 作者主页：[小胡\_不糊涂的个人主页][Link 1]  
> ? 收录专栏：[浅谈数据结构][Link 2]  
> ? 持续更文，关注博主少走弯路，谢谢大家支持 ?

#### 线性表与顺序表 ####

*  1. 线性表
 *  2. 顺序表
 *   *  2.1 接口的实现
 *  3. ArrayList简介
 *  4. ArrayList使用
 *   *  4.1 ArrayList构造
     *  4.2 ArrayList常见操作
     *  4.3 ArrayList的遍历

![在这里插入图片描述][5e65f0d499434f2cb86df73178b47eff.gif_pic_center]

## 1. 线性表 ##

**线性表（linear list）** 是n个具有相同特性的数据元素的有限序列。 它是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

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

## 2. 顺序表 ##

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

### 2.1 接口的实现 ###

实现顺序表的插入、删除、修改、查找工作：

import java.util.Arrays;
    public class MyArrayList {
        
        public int[] elem ;//定义一个数组
        public int usedSize;//0，用来记录元素个数
        //顺序表的 默认大小
        public static final int DEFAULT_SIZE = 10;
        public MyArrayList() {
        
            this.elem = new int[DEFAULT_SIZE];
        }
        public MyArrayList(int capacity) {
        
            this.elem = new int[capacity];
        }
    
        //顺序表尾部插入元素
        public void add(int data) {
        
            checkCapacity();
            this.elem[this.usedSize] = data;
            this.usedSize++;
        }
    
        //判断顺序表是否为空
        public boolean isFull() {
        
            /*if(usedSize == elem.length) {
                return true;
            }
            return false;*/
            return usedSize == elem.length;
        }
    
        //指定pos位置添加元素data
        public void add(int pos, int data) {
        
            try {
        
                checkPosOnAdd(pos);
            }catch (PosIllegality e) {
        
                e.printStackTrace();
            }
            checkCapacity();
            //1、从最后一个有效的数据开始往后移动 //2、当i < pos 就结束
            for (int i = usedSize-1; i >= pos; i--) {
        
                elem[i+1] = elem[i];
            }
            //3、存放元素到pos 位置
            elem[pos] = data;
            //4、usedSize++;
            usedSize++;
        }
    
        //检查插入位置pos的合法性
        private void checkPosOnAdd(int pos) throws PosIllegality{
        
            if(pos < 0 || pos > usedSize) {
        
                System.out.println("不符合法！");
                throw new PosIllegality("插入元素下标异常: "+pos);
            }
        }
    
        private void checkCapacity() {
        
            if(isFull()) {
        
                //扩容
                elem = Arrays.copyOf(elem,elem.length*2);
            }
        }
    
        //判定是否包含某一元素
        public boolean contains(int toFind) {
        
            if(isEmpty()) {
        
                return false;
            }
            for (int i = 0; i < usedSize; i++) {
        
                //如果是查找引用数据类型 一定记住 重写方法
                if(elem[i] == toFind) {
        
                    return true;
                }
            }
            return false;
        }
    
        //判断线性表是否为空
        public boolean isEmpty() {
        
            return usedSize == 0;
        }
    
        //查找某个元素对应位置
        public int indexOf(int toFind) {
        
            if(isEmpty()) {
        
                return -1;
            }
            for (int i = 0; i < usedSize; i++) {
        
                //如果是查找引用数据类型 一定记住 重写方法
                if(elem[i] == toFind) {
        
                    return i;
                }
            }
            return -1;
        }
    
        //获取pos位置元素
        public int get(int pos) throws MyArrayListEmpty{
        
            checkPosOnGetAndSet(pos);
            if(isEmpty()) {
        
                throw new MyArrayListEmpty("获取指定下标元素时" +
                        "顺序表为空！");
            }
            return elem[pos];
        }
    
        private void checkPosOnGetAndSet(int pos) throws PosIllegality{
        
            if(pos < 0 || pos >= usedSize) {
        
                System.out.println("不符合法！");
                throw new PosIllegality("获取指定下标的元素异常: "+pos);
            }
        }
    
        //给pos位置设为元素value
        public void set(int pos, int value) {
        
            checkPosOnGetAndSet(pos);
            elem[pos] = value;
        }
    
        //删除第一次出现的这个数字
        public void remove(int toRemove) {
        
            int index = indexOf(toRemove);//获取元素下标
            if(index == -1) {
        
                System.out.println("没有这个数字！");
                return;
            }
            for(int i = index; i < usedSize-1;i++) {
        
                elem[i] = elem[i+1];
            }
            usedSize--;
        }
    
        //获取顺序表长度
        public int size() {
        
            return this.usedSize;
        }
    
        //清空顺序表
        public void clear() {
        
            this.usedSize = 0;
        }
    
        //打印顺序表中元素
        public void display() {
        
            for (int i = 0; i < this.usedSize; i++) {
        
                System.out.print(this.elem[i]+" ");
            }
            System.out.println();
        }
    
    }

测试类：

public class TestMAL{
        
        public static void main(String[] arg) {
        
            MyArrayList arr = new MyArrayList();
            arr.add(1);
            arr.add(2);
            arr.add(3);
            arr.add(4);
            arr.add(5);
           arr.display();
           System.out.println("-------");
           arr.add(1);
            arr.display();
            System.out.println("-------");
            arr.add(6,2);
            arr.display();
            System.out.println("-------");
            System.out.println(arr.indexOf(3));
            arr.display();
            System.out.println("-------");
            arr.get(9);
        }
    }

## 3. ArrayList简介 ##

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

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

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

## 4. ArrayList使用 ##

### 4.1 ArrayList构造 ###

<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>

ArrayList的创建：

public static void main(String[] arg){
        
        // ArrayList创建，推荐写法
        // 构造一个空的列表
            List<Integer> list1 = new ArrayList<>();
        // 构造一个具有10个容量的列表
            List<Integer> list2 = new ArrayList<>(10);
            list2.add(1);
            list2.add(2);
            list2.add(3);
        // list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素
        // list3构造好之后，与list中的元素一致
            ArrayList<Integer> list3 = new ArrayList<>(list2);
        // 避免省略类型，否则：任意类型的元素都可以存放，使用时将是一场灾难
            List list4 = new ArrayList();
            list4.add("111");
            list4.add(100);
            System.out.println(list4);//[111,100]
        }

### 4.2 ArrayList常见操作 ###

<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>

ArrayList操作方法的使用：

public static void main(String[] args) {
        
            List<String> list = new ArrayList<>();
            list.add("JavaSE");
            list.add("JavaWeb");
            list.add("JavaEE");
            list.add("JVM");
            list.add("测试课程");
            System.out.println(list);
    // 获取list中有效元素个数
            System.out.println(list.size());
    // 获取和设置index位置上的元素，注意index必须介于[0, size)间
            System.out.println(list.get(1));
            list.set(1, "JavaWEB");
            System.out.println(list.get(1));
    // 在list的index位置插入指定元素，index及后续的元素统一往后搬移一个位置
            list.add(1, "Java数据结构");
            System.out.println(list);
    // 删除指定元素，找到了就删除，该元素之后的元素统一往前搬移一个位置
            list.remove("JVM");
            System.out.println(list);
    // 删除list中index位置上的元素，注意index不要超过list中有效元素个数,否则会抛出下标越界异常
            list.remove(list.size()-1);
            System.out.println(list);
            // 检测list中是否包含指定元素，包含返回true，否则返回false
            if(list.contains("测试课程")){
        
                list.add("测试课程");
            }
    // 查找指定元素第一次出现的位置：indexOf从前往后找，lastIndexOf从后往前找
            list.add("JavaSE");
            System.out.println(list.indexOf("JavaSE"));
            System.out.println(list.lastIndexOf("JavaSE"));
    // 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
            List<String> ret = list.subList(0, 4);
            System.out.println(ret);
            list.clear();
            System.out.println(list.size());
        }

### 4.3 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();
        }

[Link 1]: https://blog.csdn.net/iLoyo_
[Link 2]: http://t.csdnimg.cn/pu3jy
[5e65f0d499434f2cb86df73178b47eff.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/691e0a6e39784dd381e0e2f8bcbc6c80.gif
[bff1efb176ae4585a674cf16736cf895.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/d4efc15158e84a48960fed790a90c218.png
[e2402fb878334f32b806df1ef7d9e370.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c4b54d457e1441e3a9d0ef797b48402a.png