基于数组、链表、哈希表实现自定义的List、Map接口
一、基于数组实现自定义的List接口 1.数组介绍
- 数组长度固定，不允许动态定义数组大小，在使用之前必须确定大小；
- 存储数据类型相同；
- 各个元素存储是有先后顺序的，在内存中按照一定先后顺序连续存放在一起；
/*自定义List接口*/
public interface MyList {
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 implements MyList, Iterable {
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 iterator() {
return new ArrayListIterator();
}@SuppressWarnings("unchecked")
private class ArrayListIterator implements Iterator {
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 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 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 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 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 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 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 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 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 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 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释放已分配的空间，避免内存空间浪费；
/*基于链表实现自定义List接口*/
public class MyLinkedList implements MyList {
private int size;
public Node beginNode;
public Node 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 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 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 node = getNode(index);
node.e = e;
return true;
}
}@Override
public E get(int index) {
return getNode(index).e;
}private Node getNode(int index) {
Node 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 prev, E e) {
Node newNode = new Node<>(e, prev.prev, prev);
newNode.prev.next = newNode;
prev.prev = newNode;
this.size++;
}private static class Node {
public E e;
public Node prev;
public Node next;
public Node(E element) {
this.e = element;
}public Node(E element, Node prev, Node next) {
this.e = element;
this.prev = prev;
this.next = next;
}
}
}
/*自定义LinkedList 测试类*/
public class MyLinkedListTest {
@Test
public void should_return_size_of_linked_list() {
MyLinkedList 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 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 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 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 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 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 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 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 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）的时间级；
- 基于数组，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重；
/*自定义Map接口*/
public interface MyMap {
V put(K key, V value);
V remove(K key);
V get(K key);
int size();
public interface Entry {
K getKey();
V getValue();
}
}
/*基于哈希表实现自定义Map接口*/
public class MyHashMap implements MyMap {
private static int defaultSize = 10;
private Entry[] 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 entry = table[index];
if (entry == null) {
table[index] = new Entry<>(key, value, null);
} else {
while (entry != null) {
if (entry.getKey() == key) {
V oldValue = https://www.it610.com/article/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 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 = https://www.it610.com/article/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 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 implements MyMap.Entry {
K k;
V v;
Entry next;
public Entry(K k, V v, Entry 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 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 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 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）空间分配方面： 【基于数组、链表、哈希表实现自定义的List、Map接口】(静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小。 链表从堆中分配空间, 自由度大但是申请管理比较麻烦。
（6）哈希表既能够具备数组的快速查询的优点又能融合链表方便快捷的增加删除元素的优势： 2.ArrayList、LinkedList、HashMap的小结
- List的特征是其元素以线性方式存储，集合中可以存放重复对象。
- List接口主要实现类包括：
- ArrayList() : 代表长度可以改变得数组。可以对元素进行随机的访问，向ArrayList()中插入与删除元素的速度慢。
- LinkedList(): 在实现中采用链表数据结构。插入和删除速度快，访问速度慢。
推荐阅读
- 一个人的碎碎念
- 野营记-第五章|野营记-第五章 讨伐梦魇兽
- Shell-Bash变量与运算符
- 清明，是追思、是传承、是感恩。
- 牛人进化+|牛人进化+ 按自己的意愿过一生
- 基于微信小程序带后端ssm接口小区物业管理平台设计
- 七老修复好敏感、角质层薄、红血丝
- 华为旁！大社区、地铁新盘，佳兆业城市广场五期！
- 标签、语法规范、内联框架、超链接、CSS的编写位置、CSS语法、开发工具、块和内联、常用选择器、后代元素选择器、伪类、伪元素。
- 基于|基于 antd 风格的 element-table + pagination 的二次封装