Java数据结构之顺序表及实现

小灰灰 2023-01-21 11:17 8阅读 0赞

**线性表**（**linear\_list**）是最常用且最简单的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。

# 1、线性表相关概念 #

**前驱元素**：一个A元素在B元素的前面，则称A是B的前驱元素。

**后继元素**：若B元素在A元素的后面，则称B为A的后继元素。

**线性表的特征**：

*  第一个数据元素没有前驱，这个数据元素被称为**头结点**。
 *  最后一个数据元素没有后继，这个数据元素被称为**尾结点**。
 *  除了第一个和最后一个数据元素外，其他的数据元素都有一个前驱和一个后继。

# 2、线性表的分类 #

线性表中的**数据存储方式**可以是顺序存储，也可以是链式存储，就可以分为**顺序表**和**链表**。

# 3、顺序表 #

**顺序表**是在计算机内存中**以数组的形式保存**的线性表，线性表的顺序存储是指用**一组地址连续的存储单元**，**依次存储**线性表中的**各个元素**。

![20210515194256624.png][]

## 顺序表的实现 ##

**顺序表API设计**：

<table> 
 <tbody> 
  <tr> 
   <td style="text-align:center;"><strong>类名</strong></td> 
   <td style="text-align:center;"><strong>Squencelist</strong></td> 
  </tr> 
  <tr> 
   <td>构造方法</td> 
   <td>Squencelist (int capacity)：<span style="color:#f33b45;"><strong>创建容量为capacity</strong></span>的Squencelist<strong><span style="color:#f33b45;">对象</span></strong></td> 
  </tr> 
  <tr> 
   <td>成员变量</td> 
   <td> <p>private int N;当前线性表的长度</p> <p>private T[] elements; 存储元素的数组</p> </td> 
  </tr> 
  <tr> 
   <td> <p>成员方法</p> <p>&nbsp;</p> </td> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td style="text-align:center;">public void clear()</td> 
       <td>&nbsp;清空线性表</td> 
      </tr> 
      <tr> 
       <td style="text-align:center;">public boolean isEmpty()</td> 
       <td>获取线性表中元素的个数</td> 
      </tr> 
      <tr> 
       <td style="text-align:center;">public int length()</td> 
       <td>获取线性表中元素的个数</td> 
      </tr> 
      <tr> 
       <td style="text-align:center;">public T get(int i)</td> 
       <td>获取并返回线性表中的第i个元素的值</td> 
      </tr> 
      <tr> 
       <td style="text-align:center;">public void add(T t)</td> 
       <td>向线性表中添加一个元素t</td> 
      </tr> 
      <tr> 
       <td style="text-align:center;">public void add(T t, int i)</td> 
       <td>在线性表的第i个位置上添加元素t</td> 
      </tr> 
      <tr> 
       <td style="text-align:center;">public T remove(int i)</td> 
       <td>删除并返回线性表的第i个位置的元素</td> 
      </tr> 
      <tr> 
       <td style="text-align:center;">public int indexof(T t)</td> 
       <td>返回线性表中首次出现元素t的索引下标，若不存在，则返回-1</td> 
      </tr> 
     </tbody> 
    </table></td> 
  </tr> 
 </tbody> 
</table>

## Java代码实现API ##

public class Squencelist<T>{
        private T[]elements;//保存
        private int N;//元素个数
    
        public Squencelist(int captatity) {
            elements = (T[])new Object[captatity];
            this.N=0;
        }
        /**
         * 清空列表
         */
        public void clear(){
            this.N=0;
        }
        /**
         * 判断线性表为空
         * @return
         */
        public boolean isEmpty(){
            return this.N==0;
        }
        /**
         * 获取线性表中元素个数
         * @return
         */
        public int length(){
            return this.N;
        }
        /**
         * 获取线性表的第i个元素的值
         * @param i
         * @return
         */
        public T get(int i){
            if (i<0 || i>=N){
                throw new RuntimeException("当前元素不存在！");
            }
            return elements[i];
        }
    
        /**
         * 向线性表添加元素T
         * @param t
         */
        public void add(T t){
            if(this.N==elements.length){
                throw new RuntimeException("当前表已满");
            }
            elements[N++]=t;
        }
        /**
         * 在i位置插入元素T
         * @param t
         * @param i
         */
        public void add(T t,int i){
            if (i==elements.length){
                throw new RuntimeException("当前表已满");
            }
            if (i<0 || i>N){
                throw new RuntimeException("插入的位置不合法");
            }
            for(int index=N;index>i;index--){
                elements[index]=elements[index-1];
            }
            elements[i] = t;
            this.N++;
        }
        /**
         * 删除第i个位置的元素
         * @param i
         * @return
         */
        public T remove(int i){
            if(i<0 || i>this.N){
                throw new RuntimeException("删除的位置不合法");
            }
            T t =elements[i];
            for(int index=i;index<this.N-1;index++){
                elements[index]=elements[index+1];
            }
            return t;
        }
        /**
         * 返回线性表中首次出现的指定 数据元素的位置，不存在就返回-1
         * @param t
         * @return
         */
        public int indexof(T t){
            for(int i=0;i<this.N;i++){
                if(elements[i].equals(t)){
                    return i;
                }
            }
            return -1;
        }
    
    }

## 顺序表的遍历 ##

一般作为容器存储数据，都会向外提供遍历的方式。在Java中，遍历集合的方式一般都是用foreach循环，如果想让squenceList也可以支持foreach循环，则需要做下面的操作：

1.  让SquenceList**实现Iterable接口**，**重写iterator方法**。
2.  在SquenceList内部提供一个**内部类**或**者匿名内部类**重写hasNext方法和next（）方法（**hasNext 容器中是否还有元素**，next方法是**返回当前对象**）

## Java代码实现遍历 ##

import java.util.Iterator;
    
    public class Squencelist<T> implements Iterable<T> {
        private T[]elements;//保存
        private int N;//元素个数
    
        public Squencelist(int captatity) {
            elements = (T[])new Object[captatity];
            this.N=0;
        }
        /**
         * 清空列表
         */
        public void clear(){
            this.N=0;
        }
        /**
         * 判断线性表为空
         * @return
         */
        public boolean isEmpty(){
            return this.N==0;
        }
        /**
         * 获取线性表中元素个数
         * @return
         */
        public int length(){
            return this.N;
        }
        /**
         * 获取线性表的第i个元素的值
         * @param i
         * @return
         */
        public T get(int i){
            if (i<0 || i>=N){
                throw new RuntimeException("当前元素不存在！");
            }
            return elements[i];
        }
        /**
         * 向线性表添加元素T
         * @param t
         */
        public void add(T t){
            if(this.N==elements.length){
                throw new RuntimeException("当前表已满");
            }
            elements[N++]=t;
        }
        /**
         * 在i位置插入元素T
         * @param t
         * @param i
         */
        public void add(T t,int i){
            if (i==elements.length){
                throw new RuntimeException("当前表已满");
            }
            if (i<0 || i>N){
                throw new RuntimeException("插入的位置不合法");
            }
            for(int index=N;index>i;index--){
                elements[index]=elements[index-1];
            }
            elements[i] = t;
            this.N++;
        }
        /**
         * 删除第i个位置的元素
         * @param i
         * @return
         */
        public T remove(int i){
            if(i<0 || i>this.N){
                throw new RuntimeException("删除的位置不合法");
            }
            T t =elements[i];
            for(int index=i;index<this.N-1;index++){
                elements[index]=elements[index+1];
            }
            return t;
        }
        /**
         * 返回线性表中首次出现的指定 数据元素的位置，不存在就返回-1
         * @param t
         * @return
         */
        public int indexof(T t){
            for(int i=0;i<this.N;i++){
                if(elements[i].equals(t)){
                    return i;
                }
            }
            return -1;
        }
        @Override
        public Iterator<T> iterator() {
            return new Iterator<T>() {
                private int current=0;
                @Override
                public boolean hasNext() {
                    //容器中还是否还有元素
                    return current<N;
                }
    
                @Override
                public T next() {
                    return elements[current++];
                }
            };
        }
    }

## 顺序表的容量可变 ##

在我们使用SquenceList时，创建new SquenceList(10)创建一个对象，但是当我们**添加元素时超过容量的大小**呢？？这时就会报错，就会出现**数组越界错误**。

因此在添加元素时需要**考虑容量的伸缩性**，根据需要改变容量大小。

**添加元素时**：添加元素时，应该检查当前数组的大小是否可以容纳新的元素，**不能就需要考虑扩容**（思想：**创建一个新的数组大小为现在的2倍的数组来存储**）

**移除元素**：可以考虑检查数组的大小是否太大，造成内存空间太大浪费。

代码实现：**扩容和缩容**

/**
    * 扩容和缩容
    * @param capacity
    */
    public void reSize(int capacity){
        T []temp = elements;//保存原先数据
        elements =(T[])new Object[capacity];
        for(int i=0;i<temp.length;i++){
             elements[i]=temp[i];
        }
    }
    /**
    * 向线性表添加元素T
    * @param t
    */
    public void add(T t){
        if(N >= elements.length){
             reSize(elements.length*2);
        }
        elements[N++]=t;
    }
    /**
    * 在i位置插入元素T
    * @param t
    * @param i
    */
    public void add(T t,int i){
       if(N >= elements.length){
          reSize(elements.length*2);
        }
        if (i<0 || i>N){
           throw new RuntimeException("插入的位置不合法");
         }
        for(int index=N;index>i;index--){
            elements[index]=elements[index-1];
        }
        elements[i] = t;
        this.N++;
    }
    
    public T remove(int i){
       //缩容
       if(N < elements.length/4){
           reSize(elements.length/2);
       }
       if(i<0 || i>this.N){
           throw new RuntimeException("删除的位置不合法");
        }
       T t =elements[i];
       for(int index=i;index<this.N-1;index++){
           elements[index]=elements[index+1];
       }
       return t;
    }

## Java中ArrayList实现 ##

Java中的**ArrayList**集合的底层也是一种**顺序表**，使用数组实现，同样提供了增删改查以及扩容。

*  使用数组实现
 *  也有扩容操作
 *  也提供了遍历操作

## 顺序表的时间复杂度 ##

无论数据元素多大，**get(i)只需要elements\[i\]就可以取到对应元素**，所以时间复杂度为**O(1)**,**add(int i,T t)**每一次插入元素，都要**把i位置后面的元素移动一位**，所以时间复杂度为**O(n)**,**remove(int i）**移除元素都需要把i后面的位置往前移动一位，**时间复杂度为O(n)**.

可以可以看出对于顺序表的增删时间复杂为O(n),而对于获取只需要O(1).

[20210515194256624.png]: /images/20221020/3321e2d4d24b40dfb17cf1ae9538c510.png