此算法实现简单,就是单纯地将键值对存入链表中,get()、put()、delete()操作和普通链表的操作原理完全相同。
在含有N对键值对的基于无序链表实现的符号表中,未命中查找和插入操作都需要N次比较;命中的查找平均需要N/2次比较;特别的,从零构造一个N的符号表需要~N^2次比较。
无序链表实现的符号表效率较其他方法低。
public class SequentialSearchST<Key,Value> {
private Node first; //头指针
private int size; //链表结点数
public SequentialSearchST() {size = 0;first = null;}
//节点类
private class Node{
Key key;
Value value;
Node next;
public Node(Key key,Value value,Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
//get()方法,根据键查找值
public Value get(Key key) {
for(Node x = first;x!=null;x=x.next)
if(key.equals(x.key))
return x.value; //命中
return null; //未命中
}
//put()方法,加入键值对
public void put(Key key,Value value,Node next) {
for(Node x = first;x!=null;x=x.next)
if(key.equals(x.key)) {
x.value = value;return ; //命中,更新
}
first = new Node(key,value,first); //未命中,新建,连接到链表的最前面
size++;
}
//返回键值对个数
public int size() {return size;}
//delete()方法,删除键值对
public void delete(Key key) {
for(Node x = first;x!=null;x=x.next)
if(x.next.key.equals(key)) {
x.next = x.next.next;
break;
}
}
//获取链表中的所有key
public Iterable<Key> keys() {
Queue<Key> queue = new Queue<Key>();
for (Node x = first; x != null; x = x.next)
queue.enqueue(x.key);
return queue;
}
}