java数据结构与算法：顺序表SequentiaList

顺序表SequentiaList

创建List接口并定义方法

packagecom.lhs;importjava.util.Objects;publicinterfaceList<E>{intsize();booleanisEmpty();booleancontains(Object o);booleanadd(E e);Eget(int index);Eset(int index,E e);Eremove(int index);voidaddFirst(E e);voidaddLast(E e);EremoveFirst();EremoveLast();}

实现方法

packagecom.lhs;importjava.util.Collection;importjava.util.Iterator;importjava.util.ListIterator;publicclassSequentiaList<E>implementsList<E>{privatestaticfinalintDEFAULT_CAPACITY=10;privateint size;privateObject[] elementData;publicSequentiaList(int capacity){
        elementData =newObject[capacity];
        size =0;}publicSequentiaList(){this(DEFAULT_CAPACITY);}// 返回列表中元素的数量@Overridepublicintsize(){return size;}// 判断列表是否为空@OverridepublicbooleanisEmpty(){return size ==0;}// 判断列表中是否包含某个元素@Overridepublicbooleancontains(Object o){if(size ==0){returnfalse;}for(int i =0; i < size; i++){if(elementData[i]== o)returntrue;}returnfalse;}// 向列表中添加一个元素@Overridepublicbooleanadd(E e){if(size == elementData.length){thrownewIndexOutOfBoundsException("list is full");}
        elementData[size]= e;
        size++;returntrue;}// 获取列表中指定索引位置的元素@OverridepublicEget(int index){if(index >= size){thrownewIndexOutOfBoundsException(index +" is out of bounds");}return(E) elementData[index];}// 设置列表中指定索引位置的元素@OverridepublicEset(int index,E e){if(index >= size){thrownewIndexOutOfBoundsException(index +" is out of bounds");}E oldVal =(E) elementData[index];
        elementData[index]= e;return oldVal;}// 移除列表中指定索引位置的元素@OverridepublicEremove(int index){if(index >= size){thrownewIndexOutOfBoundsException(index +" is out of bounds");}E oldVal =(E) elementData[index];for(int i = index ;i < size -1;i++){
            elementData[i]=  elementData[i+1];}
        size--;return oldVal;}// 向列表开头添加一个元素@OverridepublicvoidaddFirst(E e){if(size == elementData.length){thrownewIndexOutOfBoundsException("list is full");}for(int i = size ;i >0;i--){
            elementData[i]= elementData[i-1];}
        elementData[0]= e;
        size++;}// 向列表结尾添加一个元素@OverridepublicvoidaddLast(E e){if(size == elementData.length){thrownewIndexOutOfBoundsException("list is full");}
        elementData[size]= e;
        size++;}// 移除列表开头的一个元素@OverridepublicEremoveFirst(){returnremove(0);}// 移除列表结尾的一个元素@OverridepublicEremoveLast(){returnremove(size-1);}}

测试

packagecom.lhs;importorg.junit.Test;importstaticjunit.framework.TestCase.*;importstaticorg.junit.Assert.assertThrows;publicclassSequentiaListTest{@TestpublicvoidtestSize(){// 实例化SequentialListList<String> list =newSequentiaList<>(5);assertTrue(list.size()==0);

        list.add("Java");assertTrue(list.size()==1);}@TestpublicvoidtestIsEmpty(){// 实例化SequentialListList<String> list =newSequentiaList<>(5);assertTrue(list.isEmpty());

        list.add("Java");assertFalse(list.isEmpty());}@TestpublicvoidtestContains(){// 实例化SequentialListList<String> list =newSequentiaList<>(5);
        list.add("Java");
        list.add("C++");
        list.add("C");
        list.add("Python");
        list.add("TypeScript");// 判断存在assertTrue(list.contains("Java"));// 判断不存在assertFalse(list.contains("Java++"));}@TestpublicvoidtestAdd(){// 实例化SequentialListList<Integer> list =newSequentiaList<>(5);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);Throwable excpetion =assertThrows(IndexOutOfBoundsException.class,()->{
            list.add(6);// 抛异常});assertEquals("list is full", excpetion.getMessage());}@TestpublicvoidtestGet(){// 实例化SequentialListList<String> list =newSequentiaList<>(5);
        list.add("Java");
        list.add("C++");
        list.add("C");// 判断存在assertEquals("C++", list.get(1));// 判断不存在assertNull(list.get(4));}@TestpublicvoidtestSet(){// 实例化SequentialListList<String> list =newSequentiaList<>(5);
        list.add("Java");
        list.add("C++");
        list.add("C");// 判断存在assertEquals("C", list.set(2,"Python"));// 判断不存在assertEquals(null, list.set(4,"TypeScript"));}@TestpublicvoidtestRemove(){// 实例化SequentialListList<String> list =newSequentiaList<>(5);
        list.add("Java");
        list.add("C++");
        list.add("C");// 判断存在assertEquals("C", list.remove(2));// 判断不存在int index =6;Throwable excpetion =assertThrows(IndexOutOfBoundsException.class,()->{
            list.remove(index);// 抛异常});assertEquals(index +" is out of bounds", excpetion.getMessage());}@TestpublicvoidtestAddFirst(){// 实例化SequentialListList<String> list =newSequentiaList<>(5);
        list.addFirst("Java");
        list.addFirst("C++");
        list.addFirst("C");// 判断存在assertEquals("C", list.get(0));assertEquals("C++", list.get(1));assertEquals("Java", list.get(2));}@TestpublicvoidtestAddLast(){// 实例化SequentialListList<String> list =newSequentiaList<>(5);
        list.addLast("Java");
        list.addLast("C++");
        list.addLast("C");// 判断存在assertEquals("Java", list.get(0));assertEquals("C++", list.get(1));assertEquals("C", list.get(2));}@TestpublicvoidtestRemoveFirst(){// 实例化SequentialListList<String> list =newSequentiaList<>(5);
        list.add("Java");
        list.add("C++");
        list.add("C");// 判断存在assertEquals("Java", list.removeFirst());assertEquals("C++", list.removeFirst());assertEquals("C", list.removeFirst());}@TestpublicvoidtestRemoveLast(){// 实例化SequentialListList<String> list =newSequentiaList<>(5);
        list.add("Java");
        list.add("C++");
        list.add("C");// 判断存在assertEquals("C", list.removeLast());assertEquals("C++", list.removeLast());assertEquals("Java", list.removeLast());}}