目录

前言

一、顺序表的实现

总结

前言

        由于CSDN的撤销功能和自动保存功能导致我写的博客直接GG,心态爆炸。所以长话短说。算法复杂度包括时间复杂度以及空间复杂度。算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。具体怎么计算不再赘述。多写几道题就懂了。线性结构具有以下主要特点

有序

除首和尾外，所有元素均有前后元素（“前驱”、“后继”）

顺序表见正文

一、顺序表的实现

        这个是一个简单的顺序表的实现，其中用到的思想在之前的文章中也出现过，不在过多的介绍。

package data_structure;import java.util.Arrays;//在数组对象的基础上继续封装出顺序表对象
/*
需要满足以下条件
1）size<=array.length
2）有用的元素的下标为[0,size)
3)由于顺序表不允许出现空洞,可选的下标范围[0,size]
4)[size,array.length)都应该是无效的元素
*/
public class MyArrayList {private long[] array;     //  1）存元素的空间  2）空间的容量private int size;         //元素的个数private  void expand(){if(size<array.length){return;}else {int newlength=array.length*2;long[] longs = Arrays.copyOf(array,newlength);Arrays.fill(longs,size,newlength,Long.MIN_VALUE);array=longs;}}public MyArrayList() {array = new long[2];size = 0;//理论上非必须Arrays.fill(array, Long.MIN_VALUE);}public void add(long e) {expand();//将元素放在size处array[size] = e;//让size变化也就是+1size++;}public void add(int index,long e){if(index<0||index>size){throw new RuntimeException();}else if(size==0||index==size){add(e);}else{size++;expand();for (int i = size-1; i >index ; i--) {array[i]=array[i-1];}array[index]=e;}}public int getSize() {return size;}public long get(int index){if(index<0||index>=size){throw new RuntimeException();}return array[index];}public void check() {if (array == null) {throw new RuntimeException();}if (array.length == 0) {throw new RuntimeException();}if (size < 0) {throw new RuntimeException();}if (size > array.length) {throw new RuntimeException();}for (int i = 0; i < size; i++) {if (array[i] == Long.MIN_VALUE) {throw new RuntimeException();}}for (int i = size; i < array.length; i++) {if (array[i] != Long.MIN_VALUE) {throw new RuntimeException();}}}/*public static void main(String[] args) {MyArrayList l1 = new MyArrayList();l1.add(1);l1.add(1);}
*/
}

总结

        我们通过顺序表来简单的了解以下数据结构。我们学习数据结构并不是单纯的去学习链表。栈和队列、树等等的实现方法、使用方法以及概念形式，这样的行为无异于买椟还珠。而是我们通过这些数据结构去体会这样的数据组织的形式，这样的算法思想。这样才能结合实际情况，灵活的去对数据进行一个组织。