数据结构——实现list

只实现最基本的add,remove,size,get方法。

定义接口

实现JDK的list对初学者难度太大，这里自己定义一个。

public interface IList<E> {

    public void add(E e);

    public E remove(E e);

    public int size();

    public E get(int index) throws Exception;
}

实现

数组实现

import java.util.Arrays;

public class MyArrayList<E> implements IList<E> {

    private int size;

    private static Object[] ELEMENT_DATA;

    private static Object[] EMPTY_ELEMENT_DATA = {};

    private final static int DEFAULT_SIZE = 10;

    public MyArrayList(){
        ELEMENT_DATA = EMPTY_ELEMENT_DATA;
    }

    @Override
    public void add(E e) {
        checkCapacity(size+1);
        ELEMENT_DATA[size++] = e;
    }

    @Override
    public E remove(E e) {
        if (size == 0){
            return null;
        }
        if (e != null){
            // 遍历数组
            for (int i = 0; i < this.size; i++) {
                if (e.equals(ELEMENT_DATA[i])){
                    // 如果删除的不是最后一位
                    ELEMENT_DATA[i] = null;
                    // 删除相匹配的第一个元素
                    if (i != this.size-1){
                        // 索引i之后的所有元素左移一位
                        for (int j = i; j < this.size; j++) {
                            ELEMENT_DATA[j] = ELEMENT_DATA[j+1];
                        }
                    }
                    break;

                }
            }
            this.size--;
            // 返回删除元素
            return e;
        }

        return null;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public E get(int index) {
        if (index >= this.size){
            return null;
        }


        return (E)ELEMENT_DATA[index];
    }

    public static void checkCapacity(int minCapacity){
        // 取当前元素个数和默认长度的最大值
        minCapacity = Math.max(minCapacity,DEFAULT_SIZE);
        // 数组扩容
        expansionCapacity(minCapacity);
    }

    public static void expansionCapacity(int minCapacity){
        // 如果当前数组为空
        if (ELEMENT_DATA.length == 0) {
            ELEMENT_DATA = new Object[DEFAULT_SIZE];
        }
        // 如果当前数组长度大于等于默认长度
        if (minCapacity >= ELEMENT_DATA.length){
            // 默认扩容一倍
            ELEMENT_DATA = Arrays.copyOf(ELEMENT_DATA,ELEMENT_DATA.length*2);
        }
    }
}

单链表实现

public class MySingleList<E> implements IList<E> {

    private int size = 0;

    private Node<E> first;

    private Node<E> last;

    public MySingleList(){}

    @Override
    public void add(E e) {
        Node<E> newNode = new Node<>(e,null);
        //首次插入
        if (last == null){
            first = newNode;
            last = first;
        }else{
            //否则尾指针指向新插入的元素
            last.next = newNode;
            last = newNode;
        }
        size++;
    }

    @Override
    public E remove(E e) {
        //定义一个临时节点用于存储被删除节点的前趋节点
        Node<E> temp,target = null;
        //首先遍历链表找到需要删除的元素
        if (e == null){
            for(Node<E> x = first;x != null;x = x.next){
                //找到需要删除的元素的前趋节点
                if (x.e == null){
                    temp = x;
                    target = x.next;
                    //将前趋节点的下一节点指向被删除节点的下一节点
                    temp.next = target.next;
                    size--;
                    //删除成功
                    return null;
                }
            }
        }
        else{
            for(Node<E> x = first;x != null;x = x.next){
                //找到需要删除的元素的前趋节点
                if (x.next != null&&e.equals(x.next.e)){
                    temp = x;
                    target = x.next;
                    //将前趋节点的下一节点指向被删除节点的下一节点
                    temp.next = target.next;
                    size--;
                    //删除成功
                    return (E)target.e;
                }
            }
        }

        //删除失败返回null
        return null;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public E get(int index) throws Exception{
        checkSize(index);
        int i = 1;
        Node<E> x = first;
        while (i < index){
            x = x.next;
            i++;
        }
        return x == null ? null : (E)x.e;
    }

    private void checkSize(int i) throws Exception{
        if (i > this.size || i <= 0){
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * 单链表
     * @param <E>
     */
    class Node<E>{
        E e;
        Node<E> next;

        public Node(E e,Node<E> next){
            this.e = e;
            this.next = next;
        }
    }
}

双链表实现

双链表实现相对简单

public class MyDequeList<E> implements IList<E> {

    private int size;

    private Node<E> head,tail;

    public MyDequeList(){super();};

    @Override
    public void add(E e) {
        Node<E> node = new Node<E>(e);

        if (this.head == null){
            this.head = node;
            this.tail = this.head;
        }else{
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
        size++;
    }

    @Override
    public E remove(E e) {
        //空队列
        if (this.head == null){
            return null;
        }

        //从头结点开始遍历
        for(Node<E> current = this.head;current != null;current = current.next){
            if (checkVal(e,current.val)){
                //如果是头结点
                if (current.prev == null){
                    this.head = current.next;
                }else{
                    current.prev.next = current.next;
                }

                if (current.next != null){
                    current.next.prev = current.prev;
                }else{
                    this.tail = current.prev;
                }

                this.size--;
                return e;
            }
        }
        return null;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public E get(int index) throws Exception {
        if (index > this.size){
            throw new IndexOutOfBoundsException();
        }

        //从头结点开始遍历
        Node<E> current = this.head;
        int i = 0;
        while(i < index){
            current = current.next;
            i++;
        }

        return current.val;
    }

    private boolean checkVal(E target,E val){
        return target == null ? false : target.equals(val);
    }

    class Node<E>{
        E val;
        Node<E> prev,next;

        public Node(E val){
            this.val = val;
        }
    }
}