数据结构篇11、映射Map及其三种底层实现,精选Android面试真题集锦
public V get(K key){Node node = getNode(key);
return node == null ? null : node.value;
}
@Override
public void add(K key, V value){
Node node = getNode(key);
if(node == null){
dummyHead.next = new Node(key, value, dummyHead.next);
size ++;
}
else
node.value = value;
}
@Override
public void set(K key, V newValue){
Node node = getNode(key);
if(node == null)
throw new IllegalArgumentException(key + " doesn't exist!");
node.value = newValue;
}
@Override
public V remove(K key){
Node prev = dummyHead;
while(prev.next != null){
if(prev.next.key.equals(key))
break;
prev = prev.next;
}
if(prev.next != null){
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size --;
return delNode.value;
}
return null;
}
}
3、二分搜索树实现的映射Map
二分搜索树实现的映射Map如下所示,因为我们在数据结构篇05实现的二分搜索树只有一个泛型,但实现映射这种数据结构需要两种泛型K和V,因此我们使用两种泛型重新实现了一遍二分搜索树,不过重新实现的二分搜索树除了多了一个泛型,底层原理和实现方法与数据结构篇05实现的二分搜索树完全一致,我们在此就不过多解释,有不明白的可以去查看数据结构篇05;
public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> {
private class Node{
public K key;
public V value;
public Node left, right;
public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
}
}
private Node root;
private int size;
public BSTMap(){
root = null;
size = 0;
}
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size == 0;
}
// 向二分搜索树中添加新的元素(key, value)@Overridebr/>@Override
页:
[1]