Part1 一、线性表数据结构
线性表也称为有序表(Ordered List),是具体有相同数据类型的 n(n≥0)个元素的有序表集合，通常记为
(a[0],a[1],a[2],···,a[n-1])
复制代码
线性表的特征
1、表中的元素个数 n 称为表的长度，n=0 时称为空表。2、当 1<i<n 时：①第 i 个元素 a[i]的直接前驱是 a[i-1],a[0]无直接前驱;②第 i 个元素 a[i]的直接后继是 a[i+1],a[n-1]无直接后继；3、所有元素的类型必须相同，且不能出现缺项。4、每个数据元素既可以是基本的数据类型，也可以是复杂的数据类型。
线性表抽象类型 List
List 定义了如下核心接口：
import java.util.Arrays;import java.util.Collection;import java.util.Comparator;import java.util.Iterator;import java.util.ListIterator;import java.util.Objects;import java.util.function.UnaryOperator;
public interface List<E> extends Collection<E> { // 查询操作 int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a); // 修改操作
boolean add(E e);
boolean remove(Object o);
// 整体修改操作 boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
default void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(operator); final ListIterator<E> li = this.ListIterator(); while (li.hasNext()) { li.set(operator.apply(li.next())); } }
@SuppressWarnings({ "unchecked", "rawtypes" }) default void sort(Comparator<? super E> c) { Object[] a = this.toArray(); Arrays.sort(a, (Comparator) c); ; ListIterator<E> i = this.ListIterator(); for (Object e : a) { i.next(); i.set((E) e); } }
void clear();
// 比较与散列 boolean equals(Object o);
int hashCode();
// 按位置访问操作 E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
// 搜索操作 int indexOf(Object o);
int lastIndexOf(Object o);
// 迭代器 ListIterator<E> ListIterator();
ListIterator<E> ListIterator(int index);
// 视图 List<E> subList(int fromIndex, int toIndex); }
复制代码
自定义线性表抽象类型 List
自定义线性表抽象类型 List 作为 java.util.List 接口的简化版本。自定义 List 的代码如下：
public interface List<E>{ //统计顺序表里数据元素的个数 int size(); //判断顺序表里数据元素是否为空 boolean isEmpty(); //判断是否包含某个数据元素 boolean contains(Object o); //添加数据元素 boolean add(E e); //按照索引获取数据元素 E get(int index,E element); //添加到表头 void addFirst(E e); //添加到表尾 void addLast(E e); //移除表头 E removefirst(); //移除表尾 E removeLast();}
复制代码
Part2 二、使用数组实现顺序表 SequentialList
顺序表的特征
①顺序表可以理解为线性表的一种特殊场景，其线性表的元素按照逻辑顺序存在一组地址连续的存储单元中。Java 中数组就是一种典型的顺序表。②顺序存储总是在内存中占用一片连续存储空间，该连续存储空间的首地址用数组名或一个引用变量来表示。③属性存储最重要的特征是存储结构反映了逻辑结构，数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现的。
成员变量及构造函数
SequentialList 成员变量结构函数代码如下：
import java.rmi.server.ObjID;
public class SequentialList<E> implements List<E>{ //默认容量 private static final int DEFAULT_CAPACITY = 10; //顺序表中的数据元素 private Object[] elementData; //实际顺序表中的元素个数 //不能直接取elementData.length private int size; //初始化 public SequentialList(int capacity){ elementData = new Object[capacity]; } public SequentialList(){ this(DEFAULT_CAPACITY); } ···}
复制代码
上述代码中：1、初始化时可以设置容量。如果未设置容量，则会按照常量 DEFAULT_CAPACITY 的值 10 作为容量。2、elementData 是一个数组结构，用于存储数据元素。3、size 用于记录已经存入顺序表的元素。需要注意的是，size 不能直接取 elementData.length。elementData.length 是数组的长度(初始化时的容量)。4、初始化 SequentialList 的时间复杂度是 O(1)
统计数据元素的个数
统计数据元素的个数就是返回当前已经放入 elementData 的个数。代码如下：
public int size(){ return size;}
复制代码
判断顺序表里数据元素是否为空
判断顺序表里元素是否为空，就是判断 size 是否为 0。代码如下：
public boolean isEmpty(){ return size == 0;}
复制代码
上述代码类似于如下 if-else 语句：
public boolean isEmpty(){ if (size == 0){ return true; }else{ return false; }}
复制代码
判断是否包含某个数据元素
判断顺序表里是否包含某个数据元素就需要遍历顺序表中的所有元素，与传入的参数进行逐个比较，代码如下：
public boolean contains(Object o) { //遍历数组，判断是否存在指定的数据元素 //o可能为null，也可能不为null，需分开处理 if(o == null){ for(int i=0; i<size;i++){ if(elementData[i]==null){ return true; } } }else{ for(int i=0; i<size; i++){ if(elementData[i].equals(o)){ return true; } } } return flase;}
复制代码
上述遍历用了两个不同的处理分支。这是因为在 java 语言中，不同的数据类型其比较方式是不同的。如果是基本数据类型或是 null，则可以采用==进行比较，否则需要使用 equals 进行比较。因此，首先要对传入进行判断，即 o 是否为 null。
添加数据元素
添加数据元素就是把数据元素添加到 elementData 的最后，并且 size 要加一位。代码如下：
public boolean add(E e){ //判断是否越界 if (size == elementData.length){ throw new IndexOutfBoundsException("list is full"); } elementData[size] = e; //添加到数组的最后 size = size + 1; //size累加1位 return true;}
复制代码
这里需要注意的是添加元素前判断数组是否满足了。如果数组满了就不能添加数据元素，同时还要抛出 IndexOutfBoundsException 异常。
按照索引获取数据元素
按照索引获取数据元素，此处的索引其实就对应数据中的索引。代码如下：
public E get(int index){ //判断是否越界 if (index<0 ||index> elementData.length-1){ throw new IndexOutOfBoundsException("index" + index + "out of bounds"); } return (E)elementData[index];}
复制代码
这里需要注意的是如果给定的索引超过了实际容量，还要抛出 IndexOutOfBoundsException 异常。
按照索引设置数据元素
按照索引设置数据元素时，要区分有两种情况：1、索引已经设置过数据元素。2、索引未设置元素。代码如下：
public E set(int index, E element) { //判断是否越界 if (index < 0|| index > elementData.length - 1 ){ throw new IndexOutOfBoundsException("index" + index+"out of bounds"); } E oldValue = (E)elementData[index]; elementData[index] = element; //有可能index对应的位置之前并未设置 if (index > size - 1){ size = index + 1; } return oldValue;}
复制代码
这里需要注意的是，如果给定的索引超过了实际容量，抛出 IndexOutOfBoundsException 异常。
按照索引移除数据元素
按照索引移除数据元素，需要将被移除数据元素的所有后继元素往前移动一位。数据元素前移后，数据中最后一个数据元素需设置为 null。代码如下:
public E remove(int index) { //判断是否越界 if (index < 0||index > elementData.length - 1){ throw new IndexOutOfBoundsException("index"+index+"out of bounds"); } E result = (E) elementData[index]; for (int j = index; j < size - 1; j++){ elementData[j] = elementData[j + 1];//数据元素前移 } elementData[--size] = null;//最后的数据置null return result;}
复制代码
如果给定的索引超过了容量，还要抛出 IndexOutOfBoundsException 异常。
评论