基于数组、链表、哈希表实现自定义的List、Map接口

一、基于数组实现自定义的List接口

1.数组介绍

数组长度固定，不允许动态定义数组大小，在使用之前必须确定大小；
存储数据类型相同；
各个元素存储是有先后顺序的，在内存中按照一定先后顺序连续存放在一起；

2.简单代码实现

/*自定义List接口*/
public interface MyList<E> {
    int size();

    boolean isEmpty();

    boolean contains(E e);

    void clear();

    void add(E e);

    void add(int index, E e);

    boolean remove(int index);

    boolean set(int index, E e);

    E get(int index);
}

/*基于数组实现自定义List接口*/
public class MyArrayList<E> implements MyList<E>, Iterable<E> {
    private static final int DEFAULT_CAPACITY = 10;

    private int capacity;

    private int size;

    private Object[] arrayList;

    public MyArrayList() {
        this.capacity = DEFAULT_CAPACITY;
        initArrayList();
    }

    public MyArrayList(int capacity) {
        this.capacity = capacity;
        initArrayList();
    }

    private void initArrayList() {
        this.size = 0;
        this.arrayList = new Object[this.capacity];
    }

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

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @SuppressWarnings("unchecked")
    @Override
    public boolean contains(E e) {
        if (e == null) {
            return false;
        }
        for (Object o : arrayList) {
            E element = (E) o;
            if (e.equals(element)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public void clear() {
        this.capacity = DEFAULT_CAPACITY;
        initArrayList();
    }

    @Override
    public void add(E e) {
        add(size(), e);
    }

    @Override
    public void add(int index, E e) {
        if (size >= capacity) {
            this.capacity *= 2;
            Object[] newArrayList = new Object[capacity];
            System.arraycopy(this.arrayList, 0, newArrayList, 0, size);
            this.arrayList = newArrayList;
        }
        if (size - index >= 0) {
            System.arraycopy(this.arrayList, index, this.arrayList, index + 1, size - index);
        }
        this.arrayList[index] = e;
        size++;
    }

    @Override
    public boolean remove(int index) {
        if (index < 0 || index >= this.size) {
            throw new IndexOutOfBoundsException();
        } else {
            if (size - 1 - index >= 0) {
                System.arraycopy(arrayList, index + 1, arrayList, index, size - 1 - index);
            }
            size--;
            return true;
        }
    }

    @Override
    public boolean set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        } else {
            arrayList[index] = e;
            return true;
        }
    }

    @SuppressWarnings("unchecked")
    @Override
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        } else {
            return (E) arrayList[index];
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new ArrayListIterator();
    }

    @SuppressWarnings("unchecked")
    private class ArrayListIterator implements Iterator<E> {
        private int current = 0;

        @Override
        public boolean hasNext() {
            return current < size();
        }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return (E) (arrayList[current++]);
        }

        @Override
        public void remove() {
            MyArrayList.this.remove(--current);
        }
    }
}

/*自定义ArrayList 测试类*/
public class MyArrayListTest {
    @Test
    public void should_return_size_of_array_list() {
        MyArrayList<String> arrayList = new MyArrayList<>();
        assertThat(arrayList.size()).isEqualTo(0);
        arrayList.add("hello");
        assertThat(arrayList.size()).isEqualTo(1);
        arrayList.add("world");
        assertThat(arrayList.size()).isEqualTo(2);
    }

    @Test
    public void should_return_is_empty_of_array_list() {
        MyArrayList<Integer> arrayList = new MyArrayList<>();
        assertThat(arrayList.isEmpty()).isTrue();
        arrayList.add(1);
        assertThat(arrayList.isEmpty()).isFalse();
    }

    @Test
    public void should_return_is_array_list_contains_element() {
        MyArrayList<Integer> arrayList = new MyArrayList<>();
        assertThat(arrayList.isEmpty()).isTrue();
        arrayList.add(1);
        assertThat(arrayList.isEmpty()).isFalse();
        assertThat(arrayList.contains(1)).isTrue();
        assertThat(arrayList.contains(0)).isFalse();
    }

    @Test
    public void should_print_array_list_use_iterator_for() {
        MyArrayList<Integer> arrayList = new MyArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        int i = 1;
        for (Integer a : arrayList) {
            assertThat(a).isEqualTo(i++);
        }
    }

    @Test
    public void should_clear_array_list() {
        MyArrayList<Integer> arrayList = new MyArrayList<>();
        assertThat(arrayList.isEmpty()).isTrue();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        arrayList.clear();
        assertThat(arrayList.isEmpty()).isTrue();
    }

    @Test
    public void should_add_element_of_array_list() {
        MyArrayList<String> arrayList = new MyArrayList<>();
        assertThat(arrayList.size()).isEqualTo(0);
        arrayList.add("hello");
        assertThat(arrayList.size()).isEqualTo(1);
        arrayList.add("world");
        assertThat(arrayList.size()).isEqualTo(2);
        assertThat(arrayList.get(1)).isEqualTo("world");
    }

    @Test
    public void should_add_element_of_array_list_given_index() {
        MyArrayList<String> arrayList = new MyArrayList<>();
        assertThat(arrayList.size()).isEqualTo(0);
        arrayList.add("hello");
        assertThat(arrayList.size()).isEqualTo(1);
        arrayList.add("world");
        assertThat(arrayList.size()).isEqualTo(2);
        arrayList.add(0, "!");
        assertThat(arrayList.size()).isEqualTo(3);
        assertThat(arrayList.get(0)).isEqualTo("!");
        assertThat(arrayList.get(1)).isEqualTo("hello");
        assertThat(arrayList.get(2)).isEqualTo("world");
    }

    @Test
    public void should_delete_element_of_array_list_given_index() {
        MyArrayList<String> arrayList = new MyArrayList<>();
        arrayList.add("hello");
        arrayList.add("world");
        assertThat(arrayList.remove(1)).isTrue();
        assertThat(arrayList.size()).isEqualTo(1);
        assertThat(arrayList.remove(0)).isTrue();
        assertThat(arrayList.size()).isEqualTo(0);
    }

    @Test
    public void should_set_element_of_array_list_given_index_and_element() {
        MyArrayList<String> arrayList = new MyArrayList<>();
        arrayList.add("hello");
        arrayList.add("world");
        assertThat(arrayList.set(1, "lisa")).isTrue();
        assertThat(arrayList.size()).isEqualTo(2);
        assertThat(arrayList.get(1)).isEqualTo("lisa");
    }

    @Test
    public void should_get_element_of_array_list_given_index() {
        MyArrayList<String> arrayList = new MyArrayList<>();
        arrayList.add("hello");
        arrayList.add("world");
        assertThat(arrayList.get(0)).isEqualTo("hello");
        assertThat(arrayList.get(1)).isEqualTo("world");
    }
}

二、基于链表实现自定义的List接口

1.链表介绍

image.png

单链表、双链表、循环单链表
物理存储单元上非连续、没有顺序，各个元素的逻辑顺序根据指针链接的次序；
不需要提前知道数据大小，实现内存动态管理；
元素需要时用new分配内存空间，不需要时delete释放已分配的空间，避免内存空间浪费；

2.简单代码实现

/*基于链表实现自定义List接口*/
public class MyLinkedList<E> implements MyList<E> {
    private int size;
    public Node<E> beginNode;
    public Node<E> endNode;


    public MyLinkedList() {
        beginNode = new Node<>(null, null, null);
        endNode = new Node<>(null, beginNode, null);
        beginNode.next = endNode;
        this.size = 0;
    }

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

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public boolean contains(E e) {
        if (e == null) {
            return false;
        }
        for (int i = 0; i < size; i++) {
            Node<E> node = getNode(i);
            if (e.equals(node.e)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public void clear() {
        beginNode = new Node<>(null, null, null);
        endNode = new Node<>(null, null, null);
        beginNode.next = endNode;
        this.size = 0;
    }

    @Override
    public void add(E e) {
        add(this.size, e);
    }

    @Override
    public void add(int index, E e) {
        addBefore(getNode(index), e);
    }

    @Override
    public boolean remove(int index) {
        if (index < 0 || index >= this.size) {
            throw new IndexOutOfBoundsException();
        } else {
            return remove(getNode(index));
        }
    }

    private boolean remove(Node<E> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        this.size--;
        return true;
    }

    @Override
    public boolean set(int index, E e) {
        if (index < 0 || index >= this.size) {
            throw new IndexOutOfBoundsException();
        } else {
            Node<E> node = getNode(index);
            node.e = e;
            return true;
        }
    }

    @Override
    public E get(int index) {
        return getNode(index).e;
    }

    private Node<E> getNode(int index) {
        Node<E> res;
        if (index < 0 || index > this.size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == this.size
        ) {
            return endNode;
        }
        if (index < this.size / 2) {
            res = beginNode.next;
            for (int i = 0; i < index; i++) {
                res = res.next;
            }
        } else {
            res = endNode;
            for (int i = this.size; i > index; i--) {
                res = res.prev;
            }
        }
        return res;
    }

    private void addBefore(Node<E> prev, E e) {
        Node<E> newNode = new Node<>(e, prev.prev, prev);
        newNode.prev.next = newNode;
        prev.prev = newNode;
        this.size++;
    }

    private static class Node<E> {
        public E e;
        public Node<E> prev;
        public Node<E> next;

        public Node(E element) {
            this.e = element;
        }

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

/*自定义LinkedList 测试类*/
public class MyLinkedListTest {
    @Test
    public void should_return_size_of_linked_list() {
        MyLinkedList<String> linkedList = new MyLinkedList<>();
        assertThat(linkedList.size()).isEqualTo(0);
        linkedList.add("hello");
        assertThat(linkedList.size()).isEqualTo(1);
        linkedList.add("world");
        assertThat(linkedList.size()).isEqualTo(2);
    }

    @Test
    public void should_return_is_empty_of_linked_list() {
        MyLinkedList<Integer> linkedList = new MyLinkedList<>();
        assertThat(linkedList.isEmpty()).isTrue();
        linkedList.add(1);
        assertThat(linkedList.isEmpty()).isFalse();
    }

    @Test
    public void should_return_is_linked_list_contains_element() {
        MyLinkedList<Integer> linkedList = new MyLinkedList<>();
        assertThat(linkedList.isEmpty()).isTrue();
        linkedList.add(1);
        assertThat(linkedList.isEmpty()).isFalse();
        assertThat(linkedList.contains(1)).isTrue();
        assertThat(linkedList.contains(0)).isFalse();
    }

    @Test
    public void should_print_linked_list_use_iterator_for() {
    }

    @Test
    public void should_clear_linked_list() {
        MyLinkedList<Integer> linkedList = new MyLinkedList<>();
        assertThat(linkedList.isEmpty()).isTrue();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.clear();
        assertThat(linkedList.isEmpty()).isTrue();
    }

    @Test
    public void should_add_element_of_linked_list() {
        MyLinkedList<String> linkedList = new MyLinkedList<>();
        assertThat(linkedList.size()).isEqualTo(0);
        linkedList.add("hello");
        assertThat(linkedList.size()).isEqualTo(1);
        linkedList.add("world");
        assertThat(linkedList.size()).isEqualTo(2);
        assertThat(linkedList.get(1)).isEqualTo("world");
    }

    @Test
    public void should_add_element_of_linked_list_given_index() {
        MyLinkedList<String> linkedList = new MyLinkedList<>();
        assertThat(linkedList.size()).isEqualTo(0);
        linkedList.add("hello");
        assertThat(linkedList.size()).isEqualTo(1);
        linkedList.add("world");
        assertThat(linkedList.size()).isEqualTo(2);
        linkedList.add(0, "!");
        assertThat(linkedList.size()).isEqualTo(3);
        assertThat(linkedList.get(0)).isEqualTo("!");
        assertThat(linkedList.get(1)).isEqualTo("hello");
        assertThat(linkedList.get(2)).isEqualTo("world");
    }

    @Test
    public void should_delete_element_of_linked_list_given_index() {
        MyLinkedList<String> linkedList = new MyLinkedList<>();
        linkedList.add("hello");

        linkedList.add("world");
        assertThat(linkedList.remove(1)).isTrue();
        assertThat(linkedList.size()).isEqualTo(1);
        assertThat(linkedList.remove(0)).isTrue();
        assertThat(linkedList.size()).isEqualTo(0);
    }

    @Test
    public void should_set_element_of_linked_list_given_index_and_element() {
        MyLinkedList<String> linkedList = new MyLinkedList<>();
        linkedList.add("hello");
        linkedList.add("world");
        assertThat(linkedList.set(1, "lisa")).isTrue();
        assertThat(linkedList.size()).isEqualTo(2);
        assertThat(linkedList.get(1)).isEqualTo("lisa");
    }

    @Test
    public void should_get_element_of_linked_list_given_index() {
        MyLinkedList<String> linkedList = new MyLinkedList<>();
        linkedList.add("hello");
        linkedList.add("world");
        assertThat(linkedList.get(0)).isEqualTo("hello");
        assertThat(linkedList.get(1)).isEqualTo("world");
    }
}

三、基于哈希表实现自定义的Map接口

1.哈希表介绍

image.png

hash table 根据关键码值key value值之间进行访问；
将关键码值映射到表中的一个位置来访问记录，映射函数为散列函数，存放记录的数组叫散列表；
左边是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
哈希表运算得非常快，不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1）的时间级；
基于数组，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重；

2.简单代码实现

/*自定义Map接口*/
public interface MyMap<K, V> {
    V put(K key, V value);

    V remove(K key);

    V get(K key);

    int size();

    public interface Entry<K, V> {
        K getKey();

        V getValue();
    }
}

/*基于哈希表实现自定义Map接口*/
public class MyHashMap<K, V> implements MyMap<K, V> {
    private static int defaultSize = 10;

    private Entry<K, V>[] table;
    private int size = 0;

    public MyHashMap() {
        this(defaultSize);
    }

    public MyHashMap(int length) {
        defaultSize = length;
        table = new Entry[defaultSize];
    }

    @Override
    public V put(K key, V value) {
        int index = hash(key);
        Entry<K, V> entry = table[index];
        if (entry == null) {
            table[index] = new Entry<>(key, value, null);
        } else {
            while (entry != null) {
                if (entry.getKey() == key) {
                    V oldValue = entry.getValue();
                    entry.v = value;
                    return oldValue;
                }
                entry = entry.next;
            }
            table[index] = new Entry<>(key, value, entry);
        }
        size++;
        return table[index].getValue();
    }

    @Override
    public V remove(K key) {
        int index = hash(key);
        Entry<K, V> entry = table[index];
        if (entry.getKey() == key) {
            table[index] = null;
            size--;
            return entry.getValue();
        }

        while (entry.next != null) {
            if (entry.next.getKey() == key) {
                V oldValue = entry.next.getValue();
                entry.next = entry.next.next;
                size--;
                return oldValue;
            }
            entry = entry.next;
        }
        return null;
    }

    @Override
    public V get(K key) {
        int index = hash(key);
        Entry<K, V> entry = table[index];
        while (entry != null) {
            if (entry.getKey() == key) {
                return entry.getValue();
            }
            entry = entry.next;
        }
        return null;
    }

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

    private int hash(K k) {
        int m = defaultSize;
        int i = k.hashCode() % m;
        return i > 0 ? i : -1;
    }

    class Entry<K, V> implements MyMap.Entry<K, V> {
        K k;
        V v;
        Entry<K, V> next;

        public Entry(K k, V v, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.next = next;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }
    }
}


/*自定义HashMap测试类*/
public class MyHashMapTest {
    @Test
    public void should_return_size_of_hash_map() {
        MyHashMap<Integer, String> map = new MyHashMap<>();
        assertThat(map.size()).isEqualTo(0);
        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");
        map.put(4, "three");
        map.put(5, "one");
        map.put(6, "two");
        map.put(7, "three");
        map.put(8, "three");
        map.put(9, "one");
        assertThat(map.size()).isEqualTo(9);
    }

    @Test
    public void should_remove_element_of_hash_map() {
        MyHashMap<Integer, String> map = new MyHashMap<>();
        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");
        assertThat(map.size()).isEqualTo(3);
        map.remove(1);
        assertThat(map.size()).isEqualTo(2);
        map.remove(3);
        assertThat(map.size()).isEqualTo(1);
    }

    @Test
    public void should_return_element_of_hash_map_given_key() {
        MyHashMap<Integer, String> map = new MyHashMap<>();
        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");
        assertThat(map.get(1)).isEqualTo("one");
        assertThat(map.get(2)).isEqualTo("two");
        assertThat(map.get(3)).isEqualTo("three");
    }
}

四、小结

1.数组、链表、哈希表的小结

（1）存储空间上：

链表链表中的元素在内存中不是顺序存储的，而是通过元素中的指针联系到一起，存放的内存空间可以是连续的，也可以是不连续的；数组则是将元素在内存中连续存放。一般情况下存放相同多的数据时，数组占用较小的内存，而链表还需要存放其前驱和后继的空间。

（2）长度的可变性：

数组必须事先定义固定的长度，不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数，会出现溢出现象；当数据减少时，造成内存浪费。链表的长度是按实际需要可以伸缩的，动态地进行存储分配，可以适应数据动态地增减的情况。

（3）查找效率：

按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均需要O(n)；　
按值查找时，若数组无序，数组和链表时间复杂度均为O(n)，但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)；

（4）插入删除时：

数组平均需要移动n/2个元素，而链表只需修改指针即可；

（5）空间分配方面：

(静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小。链表从堆中分配空间, 自由度大但是申请管理比较麻烦。

（6）哈希表既能够具备数组的快速查询的优点又能融合链表方便快捷的增加删除元素的优势：

2.ArrayList、LinkedList、HashMap的小结

List的特征是其元素以线性方式存储，集合中可以存放重复对象。
List接口主要实现类包括：
ArrayList() : 代表长度可以改变得数组。可以对元素进行随机的访问，向ArrayList()中插入与删除元素的速度慢。
LinkedList(): 在实现中采用链表数据结构。插入和删除速度快，访问速度慢。