Skip to main content
 首页 » 编程设计

java算法之自定义线性结构-有序Map

2022年07月18日23Leo_wl
/** 
 * @desc: 基于单链表实现有序Map
* 有序Map,主要是在插入元素时,保证队列有序即可,所以key需要实现Comparable接口。 *
@author: 毛会懂 * @create: 2020-12-30 13:31:00 **/ public class MyOrderMap<K extends Comparable<K>,V> implements Iterable<K>{ private Node head; private Integer count; public MyOrderMap() { this.head = new Node(null,null,null); count = 0; } //插入元素时,保证有序 public void put(K key,V value){ Node curNode = head; Node pre = null; Node newNode = new Node(key,value,null); while (curNode.next != null){ pre = curNode; curNode = curNode.next; if(curNode.key.compareTo(key) == 0){ curNode.value = value; return; }else if(curNode.key.compareTo(key) > 0){ pre.next = newNode; newNode.next = curNode; count++; return; } } //已经遍历到末尾,则直接添加 curNode.next = newNode; count++; } //获取元素 public V get(K key){ Node temp = head; while (temp.next != null){ temp = temp.next; if(temp.key.equals(key)){ return temp.value; } } return null; } //删除元素 public V del(K key){ if(isEmpty()){ return null; } Node node = head; Node pre = null; while (node.next != null){ //上一个节点 pre = node; //当前节点 node = node.next; if(node.key.equals(key)){ pre.next = node.next; return node.value; } } return null; } public Boolean isEmpty(){ return count == 0; } // public Integer size(){ return count; } @Override public Iterator<K> iterator() { return new MyIterator(); } public class MyIterator implements Iterator<K>{ private Node node; public MyIterator(){ node = head; } @Override public boolean hasNext() { return node.next != null; } @Override public K next() { node = node.next; return node.key; } } private class Node{ private K key; private V value; private Node next; public Node(K key, V value, Node next) { this.key = key; this.value = value; this.next = next; } } }

测试(Student的定义见上一篇文章):

 MyOrderMap<String,String> map = new MyOrderMap();
map.put("abc","abc");
map.put("bcd","dddd");
System.out.println("取元素:" + map.get("bcd"));
System.out.println("取元素:" + map.get("abcd")); //没有这个key,所以取出来是null
System.out.println("元素的个数:" + map.size());
System.out.println("元素是否为空:" + map.isEmpty());

System.out.println("--------以下演示key为Student对象的使用----------");
Student[] stus = {
new Student("b", 11),
new Student("a", 10),
new Student("c", 12),
new Student("b", 111),
new Student("a", 111),
new Student("c", 4)};
MyOrderMap<Student,Integer> stuMap = new MyOrderMap<>();
stuMap.put(stus[0],11);
stuMap.put(stus[1],111);
stuMap.put(stus[2],11);
stuMap.put(stus[3],122);
stuMap.put(stus[4],12); //这里根据年龄判断的key是否相同,所以stus[3]和stus[4] key相同
stuMap.put(stus[5],11);
Integer value = stuMap.get(stus[3]);
System.out.println(value);
System.out.println("遍历学生map");
Iterator<Student> iterator = stuMap.iterator();
while (iterator.hasNext()){
Student next = iterator.next();
System.out.println("姓名:" + next.getName() + " 年龄:" + next.getAge() + " 值:" + stuMap.get(next));
}
System.out.println("-----删除元素-----");
Integer del = stuMap.del(stus[5]);
System.out.println("删除的value=" + del);
}

本文参考链接:https://www.cnblogs.com/maohuidong/p/14216207.html