投稿
  1. 极客之音首页
  2. 技术随笔

Java链表的定义和使用

小半 • • 技术随笔 • 阅读 230

导读：本篇文章讲解 Java链表的定义和使用，希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

​ 链表的本质是一个动态的数组，它可以实现若干对象的存储。

链表使用简介

​ 传统对象数组的开发操作依赖于脚标（索引）的控制，如果想要实现内容的动态维护，那么难度太高了，而且复杂度攀升，对于一成不变的数据可以使用对象数组来实现，但是对于随时可能变化的数据，就需要一个 可以动态扩充的对象数组。

​ 链表的实质是利用引用的逻辑关系来实现类似于数组处理操作。

链表的结构：

在这里插入图片描述

数据增加

​ 在进行链表操作的过程中，为了避免转型的异常应该使用泛型，同时也应该设计一个链表的标准接口。同时具体实现该接口时还应该通过Node类做出节点的关系描述。

interface ILink<E>{//设置泛型避免安全隐患
    public void add(E e);
}
class LinkImpl<E> implements ILink<E>{
    //-------------Node保存数据的节点以及关系---------------
    private class Node{
		//没有设置set和get方法时因为外部类可以直接访问内部类的私有成员
        private E data;
        private Node next;
        public Node(E data){
            this.data=data;
        }
        public void addNode(Node newNode){//保存新的数据
            if(this.next==null){
                this.next=newNode;//保存当前节点
            }else{
                this.next.addNode(newNode);
            }

        }
    }
    //-------------以下为Link类中定义的成员-----------------
    private Node root;
    //-------------以下为Link类中定义的方法-----------------

    @Override
    public void add(E e) {
        if(e==null){
            return ;//数据为空
        }
        Node node = new Node(e);
        if(this.root==null){
            this.root=node;//第一个节点作为根节点
        }else {//根节点存在
            this.root.addNode(node);//将新节点保存到合适的位置

        }


    }
}
    public class JavaDemo {

        public static void main(String[] args) {

            LinkImpl<String> link = new LinkImpl<>();
            link.add("a");
            link.add("b");

        }
    }

获取集合个数

  1. ILink中增加

    public int size()

  2. LinkImpl实现子类中追加统计属性private int count

  3. add（）方法执行后this.count++;

空集合判断

  1. ILink中增加

    public boolean isEmpty()

  2. LinkImpl覆写 return this.count==0或者this.root=null

返回集合数据

​ 链表本身就属于一个动态对象数组，既然是一个数组，就应该可以把所有的数据以数组的形式返回来。

  1. ILink中增加

    public Object[] toArray();

  2. LinkImpl中追加两个属性

    private int foot;//描述的是数组操作的脚标
private Object[] returnDate;//返回的数据保存

  3. 在Node类中根据递归获取数据

    public void toArray(){//以数组形式返回数据
            LinkImpl.this.returnDate[LinkImpl.this.foot++]=this.data;
            if(this.next!=null){
                this.next.toArray();
            }

        }

  4. LinkImpl中覆写方法 获取数据时一定要先进行非空判断

    public Object[] toArray() {
        if(this.isEmpty()){
            return null;//没有数据
        }
        this.foot=0;//脚标清零
        this.returnDate=new Object[this.count];//根据已有的长度开辟数组
        //利用Node类进行递归数据获取
        this.root.toArray();
        return this.returnDate;

    }

根据索引取得数据

  1. 在ILink中增加

    public E get(int Index)

  2. 在Node 中增加根据索引获取数据的方法

     public E get(int index){
            if(LinkImpl.this.count==index){
                return this.data;
            }else{
                return this.next.get(index);
            }
        }

  3. LinkImpl中实现方法

    public E get(int index) {
        if(index>=this.count){
            return null;//索引应该在指定的范围内
        }
        this.foot=0;//重置索引的下标

        return  this.root.get(index);
    }

修改指定索引数据

  1. 在ILink中增加方法

    public void set(int index,E data);

  2. 在Node中增加方法

     public void addNode(Node newNode){
            if(this.next==null){
                this.next=newNode;//保存当前节点
            }else{
                this.next.addNode(newNode);
            }
        }

  3. LinkImpl中覆写方法

     public E get(int index) {
        if(index>=this.count){
            return null;//索引应该在指定的范围内
        }
        this.foot=0;//重置索引的下标

        return  this.root.get(index);
    }

判断数据是否存在

  1. ILink中增加方法

    public boolean contains(E data)

  2. 在Node类中进行判断

    public boolean contains(E data){
            if(data.equals(this.data)){ //!!!!!注意这里把data放在前面进行比较能够避免链表中有空数据而产生的错误
                return true;
            }else{
                if(this.next==null){
                    return false;
                }
                else{
                    return this.next.contains(data);
                }
            }
        }

  3. LinkImpl实现类

      public boolean contains(E data) {
        if(data==null){
            return false;//判断数据是否为空
        }
        return root.contains(data);
    }

数据删除

要注意删除的节点是root结点还是中间结点

  1. ILink中增加方法

    public void remove(E data)

  2. Node中增加方法

     public void remove(Node previous,E data){
            if(this.data.equals(data)){
                previous.next=this.next;//空出当前节点
            }
            else{
                if(this.next!=null){//有后续节点
                    this.next.remove(this,data);
                }
            }
        }

  3. LinkImpl中覆写方法

    public void remove(Node previous,E data){
            if(this.data.equals(data)){
                previous.next=this.next;//空出当前节点
            }
            else{
                if(this.next!=null){//有后续节点
                    this.next.remove(this,data);
                }
            }
        }

清空链表

  1. ILink中增加方法

    public void clean()

  2. LinkImpl覆写方法

    public void clean() {
        this.root=null;
        this.count=0;
    }

链表相关操作完整代码


interface ILink<E>{//设置泛型避免安全隐患
    public void add(E e);//增加数据
    public int size();//获取数据个数
    public boolean isEmpty();//集合空集合判断
    public Object[] toArray();//将集合元素以数组的形式返回
    public E get(int Index);//根据索引获取数据
    public void set(int index,E data);//修改指定索引数据
    public boolean contains(E data);//判断数据是否存在
    public void remove(E data);//删除数据
    public void clean();//清空链表
}
class LinkImpl<E> implements ILink<E>{
    //-------------Node保存数据的节点以及关系---------------
    private class Node{
        private E data;
        private Node next;
        public Node(E data){
            this.data=data;
        }
        //保存新的数据
        public void addNode(Node newNode){
            if(this.next==null){
                this.next=newNode;//保存当前节点
            }else{
                this.next.addNode(newNode);
            }
        }
        //以数组形式返回数据
        public void toArray(){
            LinkImpl.this.returnDate[LinkImpl.this.foot++]=this.data;
            if(this.next!=null){
                this.next.toArray();
            }
        }
        //根据索引获取数据
        public E get(int index){
            if(LinkImpl.this.foot++==index){
                return this.data;
            }else{
                return this.next.get(index);
            }
        }
        //更改指定索引数据
        public void setNode(int index,E data){
            if (LinkImpl.this.foot++==index){
                this.data=data;
            }
            else{
                this.next.setNode(index,data);
            }
        }
        //判断数据是否存在
        public boolean contains(E data){
            if(data.equals(this.data)){
                return true;
            }else{
                if(this.next==null){
                    return false;
                }
                else{
                    return this.next.contains(data);
                }
            }
        }
        //数据删除
        public void remove(Node previous,E data){
            if(this.data.equals(data)){
                previous.next=this.next;//空出当前节点
            }
            else{
                if(this.next!=null){//有后续节点
                    this.next.remove(this,data);
                }
            }
        }
    }
    //-------------以下为Link类中定义的成员-----------------
    private Node root;
    private int count;//保存数据个数
    private int foot;//描述的是数组操作的脚标
    private Object[] returnDate;//返回的数据保存
    //-------------以下为Link类中定义的方法-----------------

    @Override
    public void add(E e) {
        if(e==null){
            return ;//数据为空
        }
        Node node = new Node(e);
        if(this.root==null){
            this.root=node;//第一个节点作为根节点
        }else {//根节点存在
            this.root.addNode(node);//将新节点保存到合适的位置
        }
        this.count++;
    }

    @Override
    public int size() {
        return this.count;
    }

    @Override
    public boolean isEmpty() {
        return this.count==0;
    }

    @Override
    public Object[] toArray() {
        if(this.isEmpty()){
            return null;//没有数据
        }
        this.foot=0;//脚标清零
        this.returnDate=new Object[this.count];//根据已有的长度开辟数组
        //利用Node类进行递归数据获取
        this.root.toArray();
        return this.returnDate;
    }

    @Override
    public E get(int index) {
        if(index>=this.count){
            return null;//索引应该在指定的范围内
        }
        this.foot=0;//重置索引的下标
        return  this.root.get(index);
    }

    @Override
    public void set(int index, E data) {
        if(index>=this.count){//判断索引
            return;
        }
        this.foot=0;//重置
        this.root.setNode(index,data);
    }

    @Override
    public boolean contains(E data) {
        if(data==null){
            return false;//判断数据是否为空
        }
        return root.contains(data);
    }

    @Override
    public void remove(E data) {
        if(this.contains(data)){
            if(this.root.data.equals(data)){
                this.root=this.root.next;//根节点为要删除的节点
            }else{//删除的节点为中间节点
                this.root.remove(this.root,data);

            }
            this.count--;
        }
    }

    @Override
    public void clean() {
        this.root=null;
        this.count=0;
    }
}
    public class JavaDemo {

        public static void main(String[] args) {

            LinkImpl<String> link = new LinkImpl<>();
            //增加数组
            link.add("a");
            link.add("b");
            link.add("c");
            //链表的长度
            System.out.println(link.size());
            //返回数据
            Object[] result=link.toArray();
            for (Object obj : result) {
                System.out.println(obj);
            }
            //根据索引查询数据
            System.out.println(link.get(0));
            //根据索引修改数据
//            link.set(0,"hhahahha");
//            System.out.println(link.get(0));
            //判断数据是否存在
            System.out.println(link.contains("b"));
            //删除数据
            link.remove("b");
            System.out.println(link.get(1));
        }
    }

综合实战:宠物商城

​ 假设有一个宠物商店，里面可以出售各种宠物，要求可以实现宠物的上架处理、下架处理、也可以根据关键字查询出宠物的信息。

在这里插入图片描述

interface ILink<E>{//设置泛型避免安全隐患
    public void add(E e);//增加数据
    public int size();//获取数据个数
    public boolean isEmpty();//集合空集合判断
    public Object[] toArray();//将集合元素以数组的形式返回
    public E get(int Index);//根据索引获取数据
    public void set(int index,E data);//修改指定索引数据
    public boolean contains(E data);//判断数据是否存在
    public void remove(E data);//删除数据
    public void clean();//清空链表
}
class LinkImpl<E> implements ILink<E>{
    //-------------Node保存数据的节点以及关系---------------
    private class Node{
        private E data;
        private Node next;
        public Node(E data){
            this.data=data;
        }
        //保存新的数据
        public void addNode(Node newNode){
            if(this.next==null){
                this.next=newNode;//保存当前节点
            }else{
                this.next.addNode(newNode);
            }
        }
        //以数组形式返回数据
        public void toArray(){
            LinkImpl.this.returnDate[LinkImpl.this.foot++]=this.data;
            if(this.next!=null){
                this.next.toArray();
            }
        }
        //根据索引获取数据
        public E get(int index){
            if(LinkImpl.this.foot++==index){
                return this.data;
            }else{
                return this.next.get(index);
            }
        }
        //更改指定索引数据
        public void setNode(int index,E data){
            if (LinkImpl.this.foot++==index){
                this.data=data;
            }
            else{
                this.next.setNode(index,data);
            }
        }
        //判断数据是否存在
        public boolean contains(E data){
            if(data.equals(this.data)){
                return true;
            }else{
                if(this.next==null){
                    return false;
                }
                else{
                    return this.next.contains(data);
                }
            }
        }
        //数据删除
        public void remove(Node previous,E data){
            if(this.data.equals(data)){
                previous.next=this.next;//空出当前节点
            }
            else{
                if(this.next!=null){//有后续节点
                    this.next.remove(this,data);
                }
            }
        }
    }
    //-------------以下为Link类中定义的成员-----------------
    private Node root;
    private int count;//保存数据个数
    private int foot;//描述的是数组操作的脚标
    private Object[] returnDate;//返回的数据保存
    //-------------以下为Link类中定义的方法-----------------

    @Override
    public void add(E e) {
        if(e==null){
            return ;//数据为空
        }
        Node node = new Node(e);
        if(this.root==null){
            this.root=node;//第一个节点作为根节点
        }else {//根节点存在
            this.root.addNode(node);//将新节点保存到合适的位置
        }
        this.count++;
    }

    @Override
    public int size() {
        return this.count;
    }

    @Override
    public boolean isEmpty() {
        return this.count==0;
    }

    @Override
    public Object[] toArray() {
        if(this.isEmpty()){
            return null;//没有数据
        }
        this.foot=0;//脚标清零
        this.returnDate=new Object[this.count];//根据已有的长度开辟数组
        //利用Node类进行递归数据获取
        this.root.toArray();
        return this.returnDate;
    }

    @Override
    public E get(int index) {
        if(index>=this.count){
            return null;//索引应该在指定的范围内
        }
        this.foot=0;//重置索引的下标
        return  this.root.get(index);
    }

    @Override
    public void set(int index, E data) {
        if(index>=this.count){//判断索引
            return;
        }
        this.foot=0;//重置
        this.root.setNode(index,data);
    }

    @Override
    public boolean contains(E data) {
        if(data==null){
            return false;//判断数据是否为空
        }
        return root.contains(data);
    }

    @Override
    public void remove(E data) {
        if(this.contains(data)){
            if(this.root.data.equals(data)){
                this.root=this.root.next;//根节点为要删除的节点
            }else{//删除的节点为中间节点
                this.root.remove(this.root,data);

            }
            this.count--;
        }
    }

    @Override
    public void clean() {
        this.root=null;
        this.count=0;
    }
}
interface Pet{//1.定义宠物标准
    public String getName();//获得宠物名字
    public String getColor();//获得宠物颜色
}
class PetShop{//2.宠物商店 以宠物的标准为主
    private ILink<Pet> allPets=new LinkImpl<Pet>();//保存多个宠物
    //追加宠物 宠物上架
    public void add(Pet pet){
        this.allPets.add(pet);
    }
    //删除宠物 宠物下架
    public void delete(Pet pet){
        this.allPets.remove(pet);
    }
    //查询宠物
    public ILink<Pet> search (String keyword){
        ILink<Pet> searchResult = new LinkImpl<>();//保存查询的数据
        Object[] result = this.allPets.toArray();//查询所有的结果
        for (Object obj : result) {
            Pet pet=(Pet)obj;
            if(pet.getName().contains(keyword)||pet.getColor().contains(keyword)){
                searchResult.add(pet);//保存查询结果
            }
        }
        return searchResult;
    }
}
//3.根据宠物标准获得宠物信息
class Cat implements Pet{
    private String name;
    private String color;
    public Cat(String name,String color){
        this.name=name;
        this.color=color;
    }
    //覆写equals方法
    public boolean equals(Object obj){
        if(obj==null){
            return false;
        }
        if(!(obj instanceof Cat)){
            return false;
        }
        if(this==obj){
            return true;
        }
        Cat cat=(Cat)obj;
        return this.name.equals(cat.name)&&this.color.equals(cat.color);
    }
    @Override
    public String toString() {
        return "Cat{" +
                "name='" + name + '\'' +
                ", color='" + color + '\'' +
                '}';
    }

    @Override
    public String getName() {
        return this.name;
    }

    @Override
    public String getColor() {
        return this.color;
    }
}
class Dog implements Pet{
    private String name;
    private String color;
    public Dog(String name,String color){
        this.name=name;
        this.color=color;
    }
    //覆写equals方法   该方法必须覆写，不覆写的话无法进行删除
    public boolean equals(Object obj){
        if(obj==null){
            return false;
        }
        if(!(obj instanceof Cat)){
            return false;
        }
        if(this==obj){
            return true;
        }
        Dog dog=(Dog)obj;
        return this.name.equals(dog.name)&&this.color.equals(dog.color);
    }
    @Override
    public String toString() {
        return "Dog{" +
                "name='" + name + '\'' +
                ", color='" + color + '\'' +
                '}';
    }

    @Override
    public String getName() {
        return this.name;
    }

    @Override
    public String getColor() {
        return this.color;
    }
}
public class JavaDemo{
    public static void main(String[] args) {
        PetShop shop=new PetShop();
        shop.add(new Dog("黄狗","黄色"));
        shop.add(new Dog("黄猫","黄色"));
        Object[] result = shop.search("黄").toArray();
        for (Object obj : result) {
            System.out.println(obj);

        }
    }
}

​ 所有的程序开发都是以接口为标准进行的，这样在进行后期程序处理的时候就可以非常的灵活。只要符合标准的对象就都可以保存。

综合实战：超市购物车

​ 使用面向对象概念表示出下面的生活场景：小明去超时买东西，所有买到的东西都放在购物车中，最后到收银台一起结账。

在这里插入图片描述

interface ILink<E>{...}
classs LinkImpl<E> implements ILink<E>{...}//代码同上
interface IGoods{//1.定义商品标准
    public String getName();
    public double getPrice();
}
interface IShopCar{//2.定义购物车标准
    public void add(IGoods good);
    public void delete(IGoods good);
    public Object[] getAll();

}
class ShopCarImpl implements IShopCar{//3.实现购物车
    private ILink<IGoods> allGoods=new LinkImpl<IGoods>();
    @Override
    public void add(IGoods good) {
            this.allGoods.add(good);
    }

    @Override
    public void delete(IGoods good) {
        this.allGoods.remove(good);
    }

    @Override
    public Object[] getAll() {
        return this.allGoods.toArray()  ;
    }
}

//4.收银台
class Crashier{
    private IShopCar shopCar;
    public Crashier(IShopCar shopCar){
        this.shopCar=shopCar;
    }
    public double getAllPrice(){//获得总价
        double sum=0.0;
        Object[] all = this.shopCar.getAll();
        for (Object obj : all) {
            IGoods good=(IGoods) obj;
            sum+=good.getPrice();
        }
        return sum;
    }
    public int getAllCount(){//获得总数
        return this.shopCar.getAll().length;
    }

}
//5.实现商品
class Book implements IGoods{
    private String name;
    private double price;
    public Book(String name,double price){
        this.name=name;
        this.price=price;
    }
    //覆写equals方法
    public boolean equals(Object obj){
        if(obj==null){
            return false;
        }
        if(!(obj instanceof Book)){
            return false;
        }
        if(this==obj){
            return true;
        }
        Book book=(Book)obj;
        return this.name.equals(book.name)&&this.price==book.price;
    }
    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", price='" + price + '\'' +
                '}';
    }

    @Override
    public String getName() {
        return this.name;
    }

    @Override
    public double getPrice() {
        return this.price;
    }
}

public class JavaDemo{
    public static void main(String[] args) {
        IShopCar shopCar = new ShopCarImpl();
        shopCar.add(new Book("book1",999));
        shopCar.add(new Book("book2",99));
        Crashier crashier = new Crashier(shopCar);
        Object[] all = shopCar.getAll();
        for (Object obj : all) {
            System.out.println((IGoods)obj);
        }

    }
}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/107587.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！