专栏首页云霄雨霁查找----基于无序链表

查找----基于无序链表

此算法实现简单,就是单纯地将键值对存入链表中,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;
    }
} 

下一篇:基于有序数组的查找

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SpringMVC--服务端校验笔记

    SuperHeroes
  • SpringMVC--Json数据交互笔记

    SuperHeroes
  • 数据压缩----霍夫曼树和霍夫曼压缩

    SuperHeroes
  • 快乐游戏,解放双手

    上回说到这个PyUserInput这个库能够模拟鼠标和键盘点击(没看过的朋友底部有传送门),今天老肥再来实战一波游戏脚本制作。

    老肥码码码
  • Canal binlog 日志管理器与GTID简介

    正如上文提到的那样,在 Canal Instance 启动的时候,首先会查询日志管理器中查找上一次的同步位点,如果没有查询到,则默认会从最新的位点开始同步,但如...

    丁威
  • PHP函数

    可变函数类似于可变变量,通过在变量名后面添加一对括号,PHP就会自动寻找与变量名的值相同的函数,并且执行该函数

    白胡杨同学
  • 新加坡用抗体测试追踪疫情,可检测已康复病例,帮助还原传染链

    截止到3月1日,COVID-19已传播至62个国家和地区,累计确诊8841例,死亡129例,海外的确诊病例增长数已经超过国内。

    大数据文摘
  • 《数据结构与算法之美》- 栈

    提到“栈”,做Java的同学还会想起Java内存模型中的“栈”,与之紧密关联的还有一个名词——堆,但是这里,此栈非彼栈。

    JackieZheng
  • 上期公众号活动中奖名单

    ? 感谢大家对WeTest公众号活动的积极参与,《无AI不测试:人工智能时代背景下,如何发展与应用自动化测试?》文末限时活动的中奖名单如下: 留言活动中奖名单...

    WeTest质量开放平台团队
  • 提升测试效率,自动化智能探索课程上线腾讯课堂啦!

    ? 导读   移动终端种类繁多,品牌众多,操作系统也分iOS和Android两大类。仅以Android举例,排除各大厂商优化定制的版本就高达十几种。   为了...

    WeTest质量开放平台团队

扫码关注云+社区

领取腾讯云代金券