用java数组实现线性表的增删改查(可扩容)

时间:2020-8-2 作者:admin


线性表的接口定义

/**
 * 线性表(列表)的接口定义
 */
public interface MyList {

    /**
     * 新增一个元素
     *
     * @param element 要新增的那个元素
     */
    public void add(Object element);

    /**
     * 删除相同元素
     *
     * @param element 要删除的那个元素
     */
    void delete(Object element);

    /**
     * 根据索引删除元素
     *
     * @param index 要删除元素的索引
     */
    void delete(int index);

    /**
     * 将指定索引位置的元素替换成新元素
     *
     * @param index 被替换元素的索引
     * @param newElement 替换成的新元素
     */
    void update(int index, Object newElement);

    /**
     * 当前列表中是否含有target这个元素
     *
     * @param target 要查找的元素
     * @return 返回是否含有这个元素
     */
    boolean contains(Object target);

    /**
     * 返回指定索引处的元素
     *
     * @param index 要返回元素的索引
     * @return 返回这个元素对象
     */
    Object elementAt(int index);

    /**
     * 查找element所在的索引,如果没有返回-1
     * @param element 要查找的元素
     * @return 返回元素索引
     */
    int indexOf(Object element);
}

 

线性表的实现类

/**
 * 用顺序存储(数组)方式来实现列表
 */
 public class MyArrayList implements MyList {

    //真正存储元素的底层结构
    private Object[]elements;

    //已存元素的个数
    private int size = 0;

    //容量(最多可存元素的个数,默认容量设为10)
    private int capacity = 10;

    /**
     * 用户指定列表的容量
     * @param capacity 列表容量
     */
    public MyArrayList(int capacity) {
        this.capacity = capacity;
        elements = new Object[capacity];
    }

    /**
     * 用户不指定容量,使用默认容量10
     */
    public MyArrayList() {
        elements = new Object[capacity];
    }

    /**
     * 新增一个元素
     *
     * @param element 要新增的那个元素
     */
    @Override
    public void add(Object element) {
        //列表容量用完后扩容
        if (size == capacity) {
            //增加一倍容量
            capacity *= 2;
            //新建一个数组
            Object[] newArr = new Object[capacity];
            for (int i = 0; i < size; ++i) {
                //将已满数组的元素复制到新数组
                newArr[i] = elements[i];
            }
            //将原数组丢弃(回收)
            elements = newArr;
        }
        elements[size++] = element;
    }

    /**
     * 删除相同元素
     *
     * @param element 要删除的那个元素
     */
    @Override
    public void delete(Object element) {
        //先找到要删除元素的下标
        int index = indexOf(element);
        if (index >= 0) {
            //调用根据索引删除元素的方法
            delete(index);
        }
    }

    /**
     * 根据索引删除元素
     *
     * @param index 要删除元素的索引
     */
    @Override
    public void delete(int index) {
        while (index < size - 1) {
            elements[index] = elements[++index];
        }
        --size;
    }

    /**
     * 将指定索引位置的元素替换成新元素
     *
     * @param index      被替换元素的索引
     * @param newElement 替换成的新元素
     */
    @Override
    public void update(int index, Object newElement) {
        elements[index] = newElement;
    }

    /**
     * 当前列表中是否含有target这个元素
     *
     * @param target 要查找的元素
     * @return 返回是否含有这个元素
     */
    @Override
    public boolean contains(Object target) {
        //调用查找元素下标的方法,如果等于-1则没查找到,
        //下标大于等于0则查找到了
        return indexOf(target) >= 0;
    }

    /**
     * 返回指定索引处的元素
     *
     * @param index 要返回元素的索引
     * @return 返回这个元素对象
     */
    @Override
    public Object elementAt(int index) {
        return elements[index];
    }

    /**
     * 查找element所在的索引,如果没有返回-1
     *
     * @param element 要查找的元素
     * @return 返回元素索引
     */
    @Override
    public int indexOf(Object element) {
        for (int i = 0; i < size; ++i) {
            if (elements[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; ++i) {
            sb.append(elements[i] + (i == size - 1 ? "" : ", "));
        }
        sb.append("]");

        return sb.toString();
    }
}

 

使用演示

import org.junit.jupiter.api.*;

public class MyArrayListTest {

    @Test
    void testAdd() {
        MyArrayList list = new MyArrayList();
        //添加一些元素
        list.add("nike");
        list.add("adidas");
        list.add("NB");
        //删除下标为1的元素
        list.delete(1);
        
        System.out.println(list);
    }
}

 

运行结果截图

用java数组实现线性表的增删改查(可扩容)

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。