算法3.1 无序链表中的顺序查找

实现:符号表的实现使用私有内部类Node保存键值对,get()会顺序地搜索链表查找给定的值,put()的实现会顺序搜索链表查找给定的键,找到则更新值,否则创建新结点并插在链表开头.

  1. public class SequentialSearchST<Key, Value>{
  2.     int size = 0;
  3.     private Node first;
  4.     private class Node{
  5.         Key key;
  6.         Value value;
  7.         Node next;
  8.         public  Node(Key key, Value value, Node next){
  9.             this.key = key;
  10.             this.value = value;
  11.             this.next = next;
  12.         }
  13.     }
  15.     private Value get(Key key){
  16.         for (Node x = first; x != null; x = x.next){
  17.             if (key.equals(x.key))
  18.                 return x.value;//找到键值,并返回
  19.         }
  20.         return null;//无键值
  21.     }
  23.     private void put(Key key, Value value){
  24.         for (Node x = first; x != null; x = x.next){
  25.             if (key.equals(x.key)) {
  26.                 x.value = value;//找到键值,并更新
  27.                 return;
  28.             }
  29.         }
  30.         first = new Node(key, value, first);//无键值,则在头结点插入新键值
  31.         size++;
  32.     }
  34.     private int size(){ return size;}
  35.     private void delete(Key key){
  36.         //延时删除先将键值置空put(key, null),之后一并删除空值结点
  37.         //即时删除
  38.         for (Node x = first; x != null; x = x.next){
  39.             if (x.next.key.equals(key))
  40.                 x.next = x.next.next;
  41.         }
  42.     }
  43. }

算法分析

  • 查找在最坏情况下序O(N),插入N个不同键需要~N²/2次比较(1+2+…+N)
  • 基于链表实现符号表和顺序查找都是非常低效的