寒光博客

[java] 用数组实现列表(顺序表) MyArrayList
分为三个部分 列表接口 接口实现 和 测试 线性表 与 列表的接口定义 package _09_Linear.li...
扫描右侧二维码阅读全文
24
2019/09

[java] 用数组实现列表(顺序表) MyArrayList

分为三个部分 列表接口 接口实现 和 测试

线性表 与 列表的接口定义

package _09_Linear.list;

/**
 * 线性表或者列表的接口定义
 */
public interface MyList {
    //新增一个元素
    void add(Object element);

    //删除相同元素
    void delete(Object element);

    //根据索引删除元素
    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 at(int index);

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

顺序存储实现列表

package _09_Linear.list;

/**
 * 用顺序存储{数组}的方式来实现列表
 */
public class MyArrayList implements MyList {
    //全局变量
    private Object[] elements;//真正处从元素的底层结构

    private int size = 0;//元素个数

    private int capacity = 10;//容量

    public MyArrayList(int capacity) {
        this.capacity = capacity;
        elements = new Object[capacity];
    }

    public MyArrayList() {
        elements = new Object[capacity];
    }

    @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;

    }

    @Override
    public void delete(Object element) {
        int index = indexOf(element);
        if(index>=0){
            delete(index);
        }
    }

    @Override
    public void delete(int index) {
        for (int i = index; i <size ; i++) {
            elements[i]=elements[i+1];
        }
        size--;
    }

    @Override
    public void update(int index, Object newElement) {
        elements[index] = newElement;
    }

    @Override
    public boolean contains(Object target) {
        return indexOf(target) >= 0;//巧用indexOf判断
    }

    @Override
    public Object at(int index) {
        return elements[index];
    }

    @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 ? "]" : ","));
        }
        return "MyArrayList{" +
                "elements=" + sb.toString() +
                '}';
    }

}

测试

测试代码 挂org.junit.Test 这个包 然后 标注@Test即可
主要测试 delete方法 和 数据超过定义的空间add方法的扩容

package _09_Linear.list;

import org.junit.Test;

public class MyArrayListTest {

    @Test
    public void test() {
        MyArrayList list = new MyArrayList();
        list.add("nike");
        list.add("addidiaos");
        list.add("NB");
        list.add("NB");
        list.add("NB");
        list.add("NB");
        list.add("NB");
        list.add("NB");
        list.add("NB");
        list.add("NB");
        list.add("NB");
        list.add("NB");
        list.add("NB");
        list.add("ab");
        list.add("NB");
        list.add("NB");
        list.add("NB");
        list.add("ss");
        list.delete("ab");
        System.out.println(list);
    }
}
本文作者:Author:     文章标题:[java] 用数组实现列表(顺序表) MyArrayList
本文地址:https://dxoca.cn/dataStructure/280.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:September 24th, 2019 at 03:16 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment