数据结构之顺序表的基本操作（java语言）

布满荆棘的人生 2021-11-22 10:52 325阅读 0赞

public class MyArrayList {
        //属性是什么
        private int[] array;//代表的是存在数据的数组
                             //array.length代表数组的容量
         private int size;   //记录顺序表的已有数据个数
        //构造方法
         public MyArrayList(){
             //1.申请空间
             array=new int[5];
             //2.初始化数据个数
             size=0;
         }
         //增
         //尾插
         public void pushBack(int element){
             ensureCapacity();
           array[size++]=element;//先从最后插入数据，然后size的计数器加1
         }
         //头插：从头开始插，数据是最后的数据先往后移一位，然后是倒数第二个，以此类推
          public void pushFront(int element){
              ensureCapacity();
              for(int i=size-1;i>=1;i--)
              {
                  array[i+1]=array[i];
              }
              array[0]=element;  //把空余出来的第一位给插上新的数据
              size++;
            }
         //从中间插:是从最后一个数据先往后移一位，然后是倒数第二个，一直到插入数据的那一位
         public void insert(int index,int element){
          //先排除要插入的数据下标错了的情况
          if(index<0||index>size)
          {
              System.err.println("下标错了");
              return;
          }
             ensureCapacity();
          //从插入的那个数据开始从前往后倒数据
          for(int i=size-1;i>=index;i--)
          {
              array[i+1]=array[i];
          }
          array[index]=element;//把空余出来的那位给插上新的数据
          size++;
         }
         //删除（重要）
         //尾删:直接让数组的数据少一个也就是最后一个，直接size--
         public void popBack(int index){
             if(size<=0)
             {
                 System.err.println("顺序表为空");
                 return;
             }
             size--;
         //array[--size]=0;
         // 这里array[]因为是一个整形数组，所以写size-- 也行，如果删除的是一个引用的话就不能这么做了,好的做法应该是把后边不要的那部分给置为空
         }
         //头删:从第二位开始行前往后一次往前倒，最后让数组的数据少一个也就是最后一个，直接size-1
         public void popFront(int index){
             if(size<=0)
             {
                 System.err.println("顺序表为空");
                 return;
             }
             for(int i=0;i<size-1;i++)
             {
                 array[i]=array[i+1];
             }
             size--; // array[size] = 0;
             //array[--size]=0;//这里不能用array[size-1];因为这样只是把最后一个数置为0了，并没有把数组中存在数据的长度减1
         }
         //从中间删除(这里是通过下标删除的)：从要删除后面的那一位开始行前往后一次往前倒，最后让数组的数据少一个也就是最后一个，直接size--
           public void earse(int index){
             if(size<=0)
             {
                 System.err.println("顺序表为空");
                 return;
             }
             if(index<0||index>=size){
                 System.err.println("下标错了");
                 return;
             }
             for(int i=index;i<size-1;i++)
             {
                 array[i]=array[i+1];
             }
             size--;
           }
         // 删掉某个元素，如果出现多次，删除第一次出现的
            public void remove(int element){
                int index =indexOf(element);
                if(index!=-1){
                    earse(index);
                }
            }
         //判断是不是为空
            public boolean isEmpty(){
             return size==0;
            }
         //删掉某个元素，如果出现多次，全部删除
         //第一种方法：直接遍历查找，然后，找到就删，不过这种方法时间复杂度是O(n^2),空间复杂度是O(1)
            public void removeAll_1(int element){
             int index;
             while ((index=indexOf(element))!=-1){
                 earse(index);
                 }
            }
         //第二种方法：创建一个新数组，把要删除的都移到新数组就完事了，这种方法的这种方法时间复杂度是O(n),空间复杂度是O(n)
         public void removeAll_2(int element){
             int[] newArray=new int [array.length];//定义一个新数组长度和以前的一样长
             int j=0;
             for(int i=0;i<size;i++)
             {
                 if(array[i]!=element)
                 {
                     newArray[j]=array[i];
                     j++;
                 }
             }
             array=newArray;
             size=j;
         }
         //第三种方法：看代码吧，有点说不清
         public void removeAll_3(int element){
            int j=0;
            for(int i=0;i<size;i++)
            {    //要知道如果相等了，i会++，j不会；不相等的话i，j都会++，这样就会把重复的那些数据给跳过
                if(array[i]!=element)
                {
                    array[j]=array[i];
                    j++;
                }
            }
            size=j;//这里很重要，可以把处理后的数据与后边的分割开来，然后打印，array[j]前边的数据都是不重复的
         }
         //查找(如果出现了多次返回第一次出现的位置)
            public int indexOf(int element){
             int i=0;
              for(i=0;i<size;i++)
              {
                  if(array[i]==element)
                  {
                     return i;
                  }
              }
                return -1;
            }
         //打印
          public void print(){
              for(int i=0;i<size;i++){
                  System.out.print(array[i]+"  ");
              }
              System.out.println();
          }
          //扩容数组
            private void ensureCapacity(){
               if(size<array.length)
               {
                   return;
               }
               int newCapacity=array.length*2;
               int[]newArray=new int[newCapacity];
               for(int i=0;i<size;i++)
               {
                   newArray[i]=array[i];
               }
               array=newArray;
            }
        public static void main(String[] args){
             MyArrayList list=new MyArrayList();
             list.print();
             list.pushBack(1);
             list.pushBack(2);
             list.pushBack(3);
             list.print();
             list.pushFront(10);
             list.pushFront(11);
             list.print();
             list.insert(3,20);
             list.print();
             list.insert(2,30);
             list.print();
             list.popBack(6);
             list.print();
             list.popFront(0);
             list.print();
             list.earse(2);
             list.print();
             list.earse(1);
             list.print();
             list.removeAll_2(2);
             list.print();
             }
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]: /images/20211122/255933cfb2b74268955553139744bc7e.png