java【链表实现】

本贴最后更新于 1476 天前,其中的信息可能已经时过境迁

一般我们在学习集合之前,都会去了解了解数据结构的相关知识,最常见的莫过于链表,在 List 集合里面,linkedList 这个子类就是使用的链表的数据结果进行实现的,

链表的优势:新增数据,删除数据,会很容易

动态数组优势:检索快

下面的有一个关于链表的数据结构,是我大学学习期间写的一个测试,便于我们加深对链表结构的掌握。

package ITaljavaT3; import org.junit.jupiter.api.Test; /* * 链表的的增加 */ interface Ilink<E>{ public abstract void add(E date);//进行元素的添加 public abstract int size();//进行长度的的获取 public abstract boolean isEmpty();//进行判断是否为空集合 public abstract Object[] toArray();//根据元素集合对应给数组获取数据 public abstract E getdate (int index);//根据指定出的索引获取数据 public abstract void setdate(int index,E date);//修改指定处索引处的值 public abstract boolean judge(E date);//判断链表中数据是否存在 public abstract void removedate(E date);//进行数据的删除 public abstract void clean();//清空集合数据 } class impLink<E> implements Ilink<E>{ /** * 节点内部类 * @author 米饭饭一族 * */ private class Node{ /** * 内部类成员变量 */ private E date; private Node next; public Node(E date) { this.date = date; } //第一次调用;this=impLink.root //第二次调用;this=impLink.root.next //第三次调用;this=impLink.root.next.next public void addnode(Node newnode) {//保存新的NODE数据 if(this.next == null) {//当前节点的下一个节点为null, this.next = newnode;//保存当前节点 }else { /* * 在第一次循环中这个地方this是 impLink.root * 第二次的时候就是implink.root.next.addnode(newnode); * 第三次的时候就是implink.root.next.next.addnode(newnode); */ this.next.addnode(newnode);//将这个节点(newnode)添加到上一个数据的节点中, } } //第一次调用 this=implink.root;根节点 //第二次调用 this=implink.root.next;根节点 //第一三调用 this=implink.root.next.next;根节点 public void returndate() { //外部类的中当前对象 impLink.this.returndate[impLink.this.foot ++]=this.date; if(this.next!=null) { this.next.returndate();//递归中出口 } } //根据索引获取相应的数据 public E getNode(int index) { if(impLink.this.foot++==index) { return this.date; } return this.next.getNode(index); } //根据索引修改相应的数据 public void setNode(int index,E date ) { if(impLink.this.foot++ ==index) { this.date=date; }else { this.next.setNode(index,date); } } //判断date数据是否存在 public boolean judgeNode(E date) { if(date.equals(this.date)) { return true; }else { if(this.next==null) { return false; }else { return this.next.judgeNode(date); } } } //进行数据的删除(把节点的下一个节点赋值给节点的上一个节点) public void removeNode(Node before,E date) { if(date.equals(this.date)) { before.next=this.next; }else { this.next.removeNode(this, date); } } } //------------------------linK类的成员变量----------------- private Node root;//保存根元素 private int count; private int foot; private Object[] returndate; //------------------------linK类的成员方法----------------- //Node node=this.root; @Override public void add(E date) { if(date==null) {//保存数据为空 return;//方法调用直接返回 } //date是一个数据,数据本身是没,要想实现关联性就必须使用Node来实现引用之间的 传递 Node newnode = new Node(date);//创建一个新的节点 if(this.root==null) {//根节点为空 this.root = newnode;//将newnode设定为根节点 }else {//节点存在 this.root.addnode(newnode);//将新的节点保存在合适的位置 //this.root为跟节点,跟节点调用方法 } this.count++; } //进行长度的的获取 public int size() { return this.count; } //进行判断是否为空集合 public boolean isEmpty() { return this.count==0; //return this.root==null; } //数据的返回 public Object[] toArray() { //先判断是否为空 if(this.isEmpty()) { return null; } this.foot=0; this.returndate = new Object[this.count]; //用node类去获取数据 this.root.returndate(); return this.returndate; } //根据索引获取指定的数据 public E getdate(int index) { if(index>=count) { return null; } this.foot=0; return this.root.getNode(index); } //修改指定处的数据 public void setdate(int index,E date) { if(index >= count) { return; }else { this.foot=0; this.root.setNode(index, date); } } //判断数据是否存在 public boolean judge(E date) { if(date == null) { return false; } return this.root.judgeNode(date); } //进行数据的删除 public void removedate(E date) { if(this.judge(date)) {//判断date是否存在 if(date.equals(this.root.date)) { this.root = this.root.next; }else { this.root.removeNode(this.root, date); } this.count--; } } //进行集合的清理 public void clean() { this.root = null;//根节点为空 this.count = 0;//索引清除 } } public class datascope { /** * 链表结构的测试操作 */ @Test public void testdataScope() { Ilink<String> link = new impLink<String>(); System.out.println(String.format("开始 【长度】%s,【值】%s,【是否为空】%s", link.size(),link.toString(),link.isEmpty())); link.add("第一个"); link.add("第二个"); link.add("第三个"); link.add("第四个"); link.add("第五个"); System.out.println(String.format("中间 【长度】%s,【值】%s,【是否为空】%s", link.size(),link.toString(),link.isEmpty())); //删除一个节点 link.removedate("第一个"); link.setdate(3, "修改第三个数据成功"); //进行数据清空 System.out.println(String.format("修改 【长度】%s,【值】%s,【是否为空】%s", link.size(),link.toString(),link.isEmpty())); link.clean(); System.out.println(String.format("结束 【长度】%s,【值】%s,【是否为空】%s", link.size(),link.toString(),link.isEmpty())); Object[] result = link.toArray(); if(result!=null) { for(Object temp:result) { System.out.println(temp); } } System.out.println("----------------指定数据的获取(索引)---------------"); if(!link.isEmpty()) { System.out.println(link.getdate(1)); System.out.println(link.getdate(2)); System.out.println(link.getdate(3)); System.out.println(link.getdate(19)); } System.out.println("----------------判断数据是否存在)---------------"); if(!link.isEmpty()) { System.out.println(link.judge("第一个")); System.out.println(link.judge("aaa")); } } }

将上述的链表进行扩展,实现一个购物车,写一个购物车的实体类小 demo

package ITaljavaT4; /* * 链表的的增加 */ interface Ilink<E>{ public abstract void add(E date);//进行元素的添加 public abstract int size();//进行长度的的获取 public abstract boolean isEmpty();//进行判断是否为空集合 public abstract Object[] toArray();//根据元素集合对应给数组获取数据 public abstract E getdate (int index);//根据指定出的索引获取数据 public abstract void setdate(int index,E date);//修改指定处索引处的值 public abstract boolean judge(E date);//判断链表中数据是否存在 public abstract void removedate(E date);//进行数据的删除 public abstract void clean();//清空集合数据 } class impLink<E> implements Ilink<E>{ private class Node{ private E date; private Node next; public Node(E date) { this.date=date; } //第一次调用;this=impLink.root //第二次调用;this=impLink.root.next //第三次调用;this=impLink.root.next.next public void addnode(Node newnode) {//保存新的NODE数据 if(this.next==null) {//当前节点的下一个节点为null, this.next=newnode;//保存当前节点 }else { /* * 在第一次循环中这个地方this是 impLink.root * 第二次的时候就是implink.root.next.addnode(newnode); * 第三次的时候就是implink.root.next.next.addnode(newnode); * */ this.next.addnode(newnode);//将这个节点(newnode)添加到上一个数据的节点中, } } //第一次调用 this=implink.root;根节点 //第二次调用 this=implink.root.next;根节点 //第一三调用 this=implink.root.next.next;根节点 public void returndate() { //外部类的中当前对象 impLink.this.returndate[impLink.this.foot ++]=this.date; if(this.next!=null) { this.next.returndate();//递归中出口 } } //根据索引获取相应的数据 public E getNode(int index) { if(impLink.this.foot++==index) { return this.date; } return this.next.getNode(index); } //根据索引修改相应的数据 public void setNode(int index,E date ) { if(impLink.this.foot++ ==index) { this.date=date; }else { this.next.setNode(index,date); } } //判断date数据是否存在 public boolean judgeNode(E date) { if(date.equals(this.date)) { return true; }else { if(this.next==null) { return false; }else { return this.next.judgeNode(date); } } } //进行数据的删除(把节点的下一个节点赋值给节点的上一个节点) public void removeNode(Node before,E date) { if(date.equals(this.date)) { before.next=this.next; }else { this.next.removeNode(this, date); } } } //------------------------linK类的成员变量----------------- private Node root;//保存根元素 private int count; private int foot; private Object[] returndate; //------------------------linK类的成员方法----------------- //Node node=this.root; @Override public void add(E date) { if(date==null) {//保存数据为空 return;//方法调用直接返回 } //date是一个数据,数据本身是没,要想实现关联性就必须使用Node来实现引用之间的 传递 Node newnode=new Node(date);//创建一个新的节点 if(this.root==null) {//根节点为空 this.root=newnode;//将newnode设定为根节点 }else {//节点存在 this.root.addnode(newnode);//将新的节点保存在合适的位置 //this.root为跟节点,跟节点调用方法 } this.count++; } //进行长度的的获取 public int size() { return this.count; } //进行判断是否为空集合 public boolean isEmpty() { return this.count==0; //return this.root==null; } //数据的返回 public Object[] toArray() { //先判断是否为空 if(this.isEmpty()) { return null; } this.foot=0; this.returndate=new Object[this.count]; //用node类去获取数据 this.root.returndate(); return this.returndate; } //根据索引获取指定的数据 public E getdate(int index) { if(index>=count) { return null; } this.foot=0; return this.root.getNode(index); } //修改指定处的数据 public void setdate(int index,E date) { if(index>=count) { return; }else { this.foot=0; this.root.setNode(index, date); } } //判断数据是否存在 public boolean judge(E date) { if(date==null) { return false; } return this.root.judgeNode(date); } //进行数据的删除 public void removedate(E date) { if(this.judge(date)) {//判断date是否存在 if(date.equals(this.root.date)) { this.root=this.root.next; }else { this.root.removeNode(this.root, date); } this.count--; } } //进行集合的清理 public void clean() { this.root=null;//根节点为空 this.count=0;//索引清除 } } /* * 写一个购物车的实现 * 1.收银台 * 包括一个计算总价的方法,一个获取商品商品数量的方法 * 2.购物车的接口标准 * 包括一个 添加商品,包括删除商品,包括获取所有的商品 * 3.商品类 * 包括一个商品的价格,名字 */ //商品标准 interface Igoods{ public String getName(); public double getprice(); } //购物车的标准 interface IShop{//购物车的接口 public void addshop(Igoods goods); public void delete(Igoods goods); public Object[] getall(); } class Shop implements IShop{ private Igoods goods; private Ilink<Igoods> shopgoogs =new impLink<Igoods>(); // public Shop(Igoods goods) { // this.goods=goods; // } @Override //添加商品 public void addshop(Igoods goods) { // TODO Auto-generated method stub this.shopgoogs.add(goods); } @Override //删除商品 public void delete(Igoods goods) { // TODO Auto-generated method stub this.shopgoogs.removedate(goods); } @Override //获取所有的商品 public Object[] getall() { // TODO Auto-generated method stub return this.shopgoogs.toArray(); } } class bag implements Igoods{ private String name; private double price; public bag(String name,double price ) { this.name=name; this.price=price; } @Override public String getName() { // TODO Auto-generated method stub return this.name; } @Override public double getprice() { // TODO Auto-generated method stub return this.price; } public String toString() { return "[商品信息:]"+this.name+" -- "+"[商品的价格:]"+this.price; } public boolean equals(Object obj) { if(obj==null) { return false; } if(!(obj instanceof bag)) { return false; } if(obj==this) { return true; } bag other=(bag)obj; return this.name.equals(other.name) && this.price==other.price; } } class book implements Igoods{ private String name; private double price; public book(String name,double price ) { this.name=name; this.price=price; } @Override public String getName() { // TODO Auto-generated method stub return this.name; } @Override public double getprice() { // TODO Auto-generated method stub return this.price; } public String toString() { return "[商品信息:]"+this.name+" -- "+"[商品的价格:]"+this.price; } public boolean equals(Object obj) { if(obj==null) { return false; } if(!(obj instanceof book)) { return false; } if(obj==this) { return true; } book other=(book)obj; return this.name.equals(other.name) && this.price==other.price; } } //收银台 class Cashier{ //结算总的价钱 public double allprice(IShop shop) { double allprice=0.0; Object obj[]=shop.getall(); for(Object temp:obj) { Igoods goods=(Igoods)temp; allprice+=goods.getprice(); } return allprice; } //结算商品的总数 public int allcount(IShop shop) { return shop.getall().length; } } public class ITaljava01 { public static void main(String[] args) { //添加商品 IShop shop =new Shop(); shop.addshop(new bag("超级书包",18.9)); shop.addshop(new bag("中级书包",18.9)); shop.addshop(new bag("低级书包",11.9)); shop.addshop(new bag("低级书包",11.9)); shop.addshop(new book("c++",19.9)); shop.addshop(new book("java",88.9)); //所有的信息 Object object1[] =shop.getall(); for(Object temp: object1) { System.out.println(temp); } //删除一个信息 shop.delete(new bag("低级书包",11.9)); //在此过去所有的删除以后的数据 System.out.println("---------删除以后获取数据--------------"); Object object2[] =shop.getall(); for(Object temp: object2) { System.out.println(temp); } System.out.println("--------计算购物车里面的价钱---------------"); Cashier cas=new Cashier(); System.out.println(cas.allprice(shop)); System.out.println(cas.allcount(shop)); } }

有兴趣的可以分析一下代码,也比较简单,主要是理解集合里面的一些数据结构。

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3201 引用 • 8216 回帖 • 1 关注
  • 链表
    12 引用 • 6 回帖
  • 数据结构
    87 引用 • 115 回帖 • 4 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • GitBook

    GitBook 使您的团队可以轻松编写和维护高质量的文档。 分享知识,提高团队的工作效率,让用户满意。

    3 引用 • 8 回帖 • 1 关注
  • Firefox

    Mozilla Firefox 中文俗称“火狐”(正式缩写为 Fx 或 fx,非正式缩写为 FF),是一个开源的网页浏览器,使用 Gecko 排版引擎,支持多种操作系统,如 Windows、OSX 及 Linux 等。

    7 引用 • 30 回帖 • 386 关注
  • CongSec

    本标签主要用于分享网络空间安全专业的学习笔记

    1 引用 • 1 回帖 • 31 关注
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 3 关注
  • 智能合约

    智能合约(Smart contract)是一种旨在以信息化方式传播、验证或执行合同的计算机协议。智能合约允许在没有第三方的情况下进行可信交易,这些交易可追踪且不可逆转。智能合约概念于 1994 年由 Nick Szabo 首次提出。

    1 引用 • 11 回帖 • 2 关注
  • 链书

    链书(Chainbook)是 B3log 开源社区提供的区块链纸质书交易平台,通过 B3T 实现共享激励与价值链。可将你的闲置书籍上架到链书,我们共同构建这个全新的交易平台,让闲置书籍继续发挥它的价值。

    链书社

    链书目前已经下线,也许以后还有计划重制上线。

    14 引用 • 257 回帖
  • Chrome

    Chrome 又称 Google 浏览器,是一个由谷歌公司开发的网页浏览器。该浏览器是基于其他开源软件所编写,包括 WebKit,目标是提升稳定性、速度和安全性,并创造出简单且有效率的使用者界面。

    63 引用 • 289 回帖
  • 开源

    Open Source, Open Mind, Open Sight, Open Future!

    412 引用 • 3588 回帖
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    7 引用 • 27 回帖
  • iOS

    iOS 是由苹果公司开发的移动操作系统,最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统,最初是设计给 iPhone 使用的,后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样,属于类 Unix 的商业操作系统。

    89 引用 • 150 回帖 • 2 关注
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    589 引用 • 3538 回帖
  • Follow
    4 引用 • 12 回帖 • 11 关注
  • Hprose

    Hprose 是一款先进的轻量级、跨语言、跨平台、无侵入式、高性能动态远程对象调用引擎库。它不仅简单易用,而且功能强大。你无需专门学习,只需看上几眼,就能用它轻松构建分布式应用系统。

    9 引用 • 17 回帖 • 636 关注
  • Node.js

    Node.js 是一个基于 Chrome JavaScript 运行时建立的平台, 用于方便地搭建响应速度快、易于扩展的网络应用。Node.js 使用事件驱动, 非阻塞 I/O 模型而得以轻量和高效。

    139 引用 • 269 回帖 • 1 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 80 关注
  • GAE

    Google App Engine(GAE)是 Google 管理的数据中心中用于 WEB 应用程序的开发和托管的平台。2008 年 4 月 发布第一个测试版本。目前支持 Python、Java 和 Go 开发部署。全球已有数十万的开发者在其上开发了众多的应用。

    14 引用 • 42 回帖 • 815 关注
  • RESTful

    一种软件架构设计风格而不是标准,提供了一组设计原则和约束条件,主要用于客户端和服务器交互类的软件。基于这个风格设计的软件可以更简洁,更有层次,更易于实现缓存等机制。

    30 引用 • 114 回帖 • 7 关注
  • Oracle

    Oracle(甲骨文)公司,全称甲骨文股份有限公司(甲骨文软件系统有限公司),是全球最大的企业级软件公司,总部位于美国加利福尼亚州的红木滩。1989 年正式进入中国市场。2013 年,甲骨文已超越 IBM,成为继 Microsoft 后全球第二大软件公司。

    107 引用 • 127 回帖 • 337 关注
  • Log4j

    Log4j 是 Apache 开源的一款使用广泛的 Java 日志组件。

    20 引用 • 18 回帖 • 30 关注
  • Windows

    Microsoft Windows 是美国微软公司研发的一套操作系统,它问世于 1985 年,起初仅仅是 Microsoft-DOS 模拟环境,后续的系统版本由于微软不断的更新升级,不但易用,也慢慢的成为家家户户人们最喜爱的操作系统。

    227 引用 • 476 回帖
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    239 引用 • 224 回帖 • 1 关注
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 613 关注
  • Visio
    1 引用 • 2 回帖 • 1 关注
  • 博客

    记录并分享人生的经历。

    273 引用 • 2388 回帖
  • Ruby

    Ruby 是一种开源的面向对象程序设计的服务器端脚本语言,在 20 世纪 90 年代中期由日本的松本行弘(まつもとゆきひろ/Yukihiro Matsumoto)设计并开发。在 Ruby 社区,松本也被称为马茨(Matz)。

    7 引用 • 31 回帖 • 249 关注
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    13 引用 • 57 回帖 • 6 关注
  • 自由行