一、基于數(shù)組實現(xiàn)自定義的List接口

1.數(shù)組介紹

• 數(shù)組長度固定磺送，不允許動態(tài)定義數(shù)組大小驻子，在使用之前必須確定大小估灿；
• 存儲數(shù)據(jù)類型相同崇呵；
• 各個元素存儲是有先后順序的，在內(nèi)存中按照一定先后順序連續(xù)存放在一起馅袁；

2.簡單代碼實現(xiàn)

/*自定義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);
}

/*基于數(shù)組實現(xiàn)自定義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");
    }
}

二域慷、基于鏈表實現(xiàn)自定義的List接口

1.鏈表介紹

image.png

• 單鏈表、雙鏈表汗销、循環(huán)單鏈表
• 物理存儲單元上非連續(xù)芒粹、沒有順序，各個元素的邏輯順序根據(jù)指針鏈接的次序大溜；
• 不需要提前知道數(shù)據(jù)大小，實現(xiàn)內(nèi)存動態(tài)管理估脆；
• 元素需要時用new分配內(nèi)存空間钦奋，不需要時delete釋放已分配的空間，避免內(nèi)存空間浪費；

2.簡單代碼實現(xiàn)

/*基于鏈表實現(xiàn)自定義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");
    }
}

三付材、基于哈希表實現(xiàn)自定義的Map接口

1.哈希表介紹

image.png

• hash table 根據(jù)關(guān)鍵碼值key value值之間進行訪問朦拖；
• 將關(guān)鍵碼值映射到表中的一個位置來訪問記錄，映射函數(shù)為散列函數(shù)厌衔，存放記錄的數(shù)組叫散列表璧帝；
• 左邊是個數(shù)組，數(shù)組的每個成員包括一個指針富寿，指向一個鏈表的頭睬隶，當然這個鏈表可能為空，也可能元素很多页徐。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去苏潜，也是根據(jù)這些特征，找到正確的鏈表变勇，再從鏈表中找出這個元素恤左。
• 哈希表運算得非常快搀绣，不論哈希表中有多少數(shù)據(jù)飞袋，查找、插入链患、刪除（有時包括刪除）只需要接近常量的時間即0(1）的時間級巧鸭；
• 基于數(shù)組，數(shù)組創(chuàng)建后難于擴展锣险，某些哈希表被基本填滿時蹄皱，性能下降得非常嚴重；

2.簡單代碼實現(xiàn)

/*自定義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();
    }
}

/*基于哈希表實現(xiàn)自定義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");
    }
}

四芯肤、小結(jié)

1.數(shù)組巷折、鏈表、哈希表的小結(jié)

（1）存儲空間上：

鏈表鏈表中的元素在內(nèi)存中不是順序存儲的崖咨，而是通過元素中的指針聯(lián)系到一起锻拘，存放的內(nèi)存空間可以是連續(xù)的，也可以是不連續(xù)的击蹲；數(shù)組則是將元素在內(nèi)存中連續(xù)存放署拟。一般情況下存放相同多的數(shù)據(jù)時，數(shù)組占用較小的內(nèi)存歌豺，而鏈表還需要存放其前驅(qū)和后繼的空間推穷。

（2）長度的可變性：

數(shù)組必須事先定義固定的長度，不能適應(yīng)數(shù)據(jù)動態(tài)地增減的情況类咧。當數(shù)據(jù)增加時馒铃，可能超出原先定義的元素個數(shù)蟹腾，會出現(xiàn)溢出現(xiàn)象；當數(shù)據(jù)減少時区宇，造成內(nèi)存浪費娃殖。鏈表的長度是按實際需要可以伸縮的，動態(tài)地進行存儲分配议谷，可以適應(yīng)數(shù)據(jù)動態(tài)地增減的情況炉爆。

（3）查找效率：

按序號查找時，數(shù)組可以隨機訪問卧晓，時間復(fù)雜度為O(1)芬首，而鏈表不支持隨機訪問，平均需要O(n)禀崖；　
按值查找時衩辟，若數(shù)組無序，數(shù)組和鏈表時間復(fù)雜度均為O(n)波附，但是當數(shù)組有序時艺晴，可以采用折半查找將時間復(fù)雜度降為O(logn)；

（4）插入刪除時：

數(shù)組平均需要移動n/2個元素掸屡，而鏈表只需修改指針即可封寞；

（5）空間分配方面：

(靜態(tài))數(shù)組從棧中分配空間, 對于程序員方便快速,但是自由度小。 鏈表從堆中分配空間, 自由度大但是申請管理比較麻煩仅财。

（6）哈希表既能夠具備數(shù)組的快速查詢的優(yōu)點又能融合鏈表方便快捷的增加刪除元素的優(yōu)勢：

2.ArrayList狈究、LinkedList、HashMap的小結(jié)

• List的特征是其元素以線性方式存儲盏求，集合中可以存放重復(fù)對象抖锥。
• List接口主要實現(xiàn)類包括：
• ArrayList() : 代表長度可以改變得數(shù)組∷榉＃可以對元素進行隨機的訪問磅废，向ArrayList()中插入與刪除元素的速度慢。
• LinkedList(): 在實現(xiàn)中采用鏈表數(shù)據(jù)結(jié)構(gòu)荆烈。插入和刪除速度快拯勉，訪問速度慢。