Java实现数组和双向链表存储两种功能

1、设计思路：包名arrBox，设计一个名为box的接口，由子类实现当中的主要方法。

2、需要大量遍历操作，我们选择数组；增加、删除操作较多，我们使用链表

3、实现数组的存储结构

package arrbox;

public class ArrBox implements Box {
    //存放真实数据
    private int DEFAULT_SIZE = 10;
    private int[] arrBox = new int[DEFAULT_SIZE];
    private int length = 0;

    public void add (int elem) {}

    //用来将给定的element数组存起来
    public void add (int...elemArr) {
        if(checkSpace(elemArr.length)){
            this.updateArrBox(elemArr);
        }else{
            for(int i = 0; i < elemArr.length; i++){
                this.arrBox[this.length++] = elemArr[i];
            }
        }
    }

    //更新数组为添加新数组后的元素
    private void updateArrBox (int[] arr) {
        int len = this.length+arr.length;
        int[] newArr = new int[len];
        for(int i = 0; i < len ;i++ ){
            if(i < this.length){
                newArr[i] = this.arrBox[i];
            }else{
                newArr[i] = arr[i - this.length];
            }
        }
        this.arrBox = newArr;
        this.length = len;
        newArr = null;
    }

    //检测空间
    private boolean checkSpace (int size) {
        boolean bool = false;
        if(this.length + size > this.DEFAULT_SIZE){
            bool = true;
        }
        return bool;
    }

    //用来获取给定索引的元素
    public int getElemByIndex (int index){
        checkIndex(index);
        return this.arrBox[index];
    }

    //用来删除给定位置的元素
    public int removeElemByIndex (int index){
        int oldValue = this.arrBox[index];
        checkIndex(index);
        //将指定索引元素移到最后
        for(int i = index; i < this.length - 1; i++){
            arrBox[i] = arrBox[i]^arrBox[i+1];
            arrBox[i+1] = arrBox[i]^arrBox[i+1];
            arrBox[i] = arrBox[i]^arrBox[i+1];
        }
        int[] newArr = new int[this.length-1];
        for(int j = 0; j < this.length - 1; j++){
            newArr[j] = arrBox[j];
        }
        //更新arrBox和this.length
        this.arrBox = newArr;
        newArr = null;
        this.length--;
        return oldValue;
    }

    //设置初始的默认长度
    public void setDefaultSize (int defaultSize) {
        if(defaultSize < 0){
            throw new BoxIndexOutOfBoundsException("默认长度非法.");
        }
        this.DEFAULT_SIZE = defaultSize;
        arrBox = new int[DEFAULT_SIZE];
    }

    //检查arrBox中的所有元素
    public void checkAllElemInBox () {
        System.out.print("arrBox中的所有元素：");
        for(int i = 0; i < this.length; i++){
            System.out.print(" "+arrBox[i]);
        }
        System.out.println();
    }

    //检测索引是否合法
    private void checkIndex (int index) {
        if(index < 0 || index > this.length){
           throw new BoxIndexOutOfBoundsException("index越界");
        }
    }

    //查看数组长度
    public int getBoxLength () {
        return this.length;
    }
}

4、实现双向链表的存储结构

//双向链表
package arrbox;

public class LinkedBox implements Box {
    //链表，链式
    private Node first;
    private Node last;
    private int size = 0;

    //添加元素
    public void add(int element){
        this.linkLast(element);
    }

    //根据索引找寻对象
    public int getElemByIndex(int index){
        //检查越界
        this.rangeCheck(index);
        return this.lookForNode(index).item;
    }

    //删除元素
    public int removeElemByIndex(int index){
        this.rangeCheck(index);
        Node targetNode = this.lookForNode(index);
        this.removeNode(targetNode);
        return targetNode.item;
    }

    //删除节点，使当前节点无关联，被GC回收
    private void removeNode (Node targetNode) {
        Node prev = targetNode.prev;
        Node next = targetNode.next;
        //判断节点如果为第一个节点
        if(prev == null){
            first = next;
        }else{
            prev.next = next;
        }
        //判断节点为最后一个节点
        if(next == null){
            last = prev;
        }else{
            next.prev = prev;
        }
        this.size--;
    }

    //获取box长度
    public int getBoxLength (){
        return this.size;
    }

    //寻找节点
    private Node lookForNode (int index) {
        Node targetNode;
        if(index < (size>>1)){
            targetNode = first;
            for(int i = 0;i < index - 1;i++){
                targetNode = targetNode.next;
            }
        }else{
            targetNode = last;
            //执行次数要判断清楚
            for(int j = this.size - 1; j > index;j--){
                targetNode = targetNode.prev;
            }
        }
        return targetNode;
    }

    private void linkLast (int element) {
        //用l保存上一个节点
        Node l = last;
        //创建新节点
        Node newNode = new Node(l,element,null);
        //最后节点改为新节点
        last  = newNode;
        //如果最后一个节点，为空，新节点就是最后一个节点
        if(l == null) {
            first = newNode;
        }else{
            //将上一次最后节点链接上新的最后节点
            l.next = newNode;
        }
        this.size++;
    }

    private void rangeCheck (int index) {
        if(index < 0 || index >= this.size) {
            throw new BoxIndexOutOfBoundsException("index越界.");
        }
    }
}

对你有用的话支持一下吧>__<