• 近期将进行后台系统升级,如有访问不畅,请稍后再试!
  • 极客文库-知识库上线!
  • 极客文库小编@勤劳的小蚂蚁,为您推荐每日资讯,欢迎关注!
  • 每日更新优质编程文章!
  • 更多功能模块开发中。。。

数据结构笔记总结(6.2)基于链表的集合实现

文章目录[隐藏]

基于链表的集合实现

这一节我们用链表来实现一下集合这种数据结构

为什么我们要单独拿出链表来实现集合这种数据结构呢?

因为二分搜索树和链表都属于动态的数据结构。

对于二分搜索树来说,数据是存储在一个个 node 中,链表也是存储在一个个 node 中,只不过这两个 node 的定义是不同的。

二分搜索树有左右两个指针指向左子树和右子树,对于链表来说,每一个 node 都指向了下一个 node,由于都属于同样的动态数据结构,基于这两种数据结构为底层来实现集合之后可以相应的来比较其性能。

通过性能的比较,可以直观的看到二分搜索树这种数据结构优势所在。

代码演示

创建一个新的类 LinkedListSet.java,下面来具体的实现它

import java.util.ArrayList;

public class LinkedListSet<E> implements Set<E> {

    private LinkedList<E> list;

    public LinkedListSet(){
        list = new LinkedList<>();
    }

    @Override
    public int getSize(){
        return list.getSize();
    }

    @Override
    public boolean isEmpty(){
        return list.isEmpty();
    }

    @Override
    public void add(E e){
        if(!list.contains(e))
            list.addFirst(e);
    }

    @Override
    public boolean contains(E e){
        return list.contains(e);
    }

    @Override
    public void remove(E e){
        list.removeElement(e);
    }
    //下面我们来测试一下集合类,同样使用上一节的例子
    public static void main(String[] args) {

        System.out.println("Pride and Prejudice");

        ArrayList<String> words1 = new ArrayList<>();
        if(FileOperation.readFile("pride-and-prejudice.txt", words1)) {
            System.out.println("Total words: " + words1.size());

            LinkedListSet<String> set1 = new LinkedListSet<>();
            for (String word : words1)
                set1.add(word);
            System.out.println("Total different words: " + set1.getSize());
        }

        System.out.println();


        System.out.println("A Tale of Two Cities");

        ArrayList<String> words2 = new ArrayList<>();
        if(FileOperation.readFile("a-tale-of-two-cities.txt", words2)){
            System.out.println("Total words: " + words2.size());

            LinkedListSet<String> set2 = new LinkedListSet<>();
            for(String word: words2)
                set2.add(word);
            System.out.println("Total different words: " + set2.getSize());
        }
    }
}

运行结果

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(6.2)基于链表的集合实现
喜欢 (0)
[247507792@qq.com]
分享 (0)

欢迎 注册账号 登录 发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00