Java学习路线-13：链表定义与实现

第30 章 ： 链表的定义与使用 134 链表实现简介

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

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

实现链表，需要一个公共结构-节点： 1、保存数据 2、连接下一个结构

Node
-E data
-next

还需要一个管理Node节点的类

客户端：数据的增删改查
链表LinkImpl：处理Node细节 -> ILink
Node：存储数据

private class Node{
    private T data;   // 数据
    private Node nextNode; // 下一节点

    public Node(T data){
        this.data = data ;
    }

    public void setNextNode(Node nextNode){
        this.nextNode = nextNode ;
    }

    public Node getNextNode(){
        return this.nextNode ;
    }

    public T getData(){
        return this.data;
    }
}

简单的单向链表实现 135 数据增加

public void add(E e);

136 获取数据集合个数

public int size();

137 空集合判断

public boolean isEmpty();

138 返回集合数据

public Object[] toArray();

139 根据索引取得数据

public E get(int index);

数组获取数据的时间复杂度为1 链表获取数据的时间复杂度为n

140 修改链表指定索引数据

public void set(int index, E data);

141 判断链表数据是否存在

public boolean contains(E data);

142 删除链表数据

public void remove(E data);

两种情况 删除根节点数据 删除非根节点数据

引用修改

143 清空链表

public void clean();

只用设置头节点为空即可

完整代码

// 定义链表的接口
interface ILink{
    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 boolean remove(E data);  // 链表数据
    public void clean();  // 清空链表
}


// 实现链表
class LinkImpl implements ILink{
    private Node rootNode;  // 记录头指针

    private int count ;    // 计数统计

    private Object[] dataList; // 数据列表
    private int foot; //角标

    // 链表节点，内部类，便于外部类直接访问其私有属性
    private class Node{
        private T data;   // 数据
        private Node nextNode; // 下一节点

        public Node(T data){
            this.data = data ;
        }

        public void addNode(Node node){
            if(!this.hasNextNode()){
                this.nextNode = node;
            } else{
                this.nextNode.addNode(node);
            }
        }

        public boolean hasNextNode(){
            return this.nextNode != null;
        }

        public void toArrayNode(){
            LinkImpl.this.dataList[LinkImpl.this.foot++] = this.data;

            if(this.hasNextNode()){
                this.nextNode.toArrayNode();
            }
        }

        public Node getNode(int index){
            if(LinkImpl.this.foot++ == index){
                return this ;
            }else{
                return this.nextNode.getNode(index);
            }
        }

        public boolean containsNode(T data){
            // 比较对象 不能是null
            if(this.data.equals(data)){
                return true;
            } else {
                // 有后续节点继续
                if(this.hasNextNode()){
                    return this.nextNode.containsNode(data);
                } else {
                    // 没有找到数据
                    return false;
                }
            }
        }
        public boolean removeNode(Node preNode, T data){
            if(this.data.equals(data)){
                preNode.nextNode = this.nextNode;
                return true;
            } else {
                // 有后续节点，继续移除操作
                if(this.hasNextNode()){
                    return this.nextNode.removeNode(this, data);    
                } else{
                    return false;
                }
            }
        }

    }

    public void add(T data){
        // 不接受null 类型的值
        if(!isValidData(data)){
            return;
        }

        Node newNode = new Node(data);

        // 添加第一个元素的时候，头节点为null
        if (this.count == 0){
            this.rootNode = newNode;
        } else {
            this.rootNode.addNode(newNode);
        }

        this.count++;
    }

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

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


    public Object[] toArray(){
        if(this.isEmpty()){
            return null;
        }

        // 角标清零，创建空数组
        this.foot = 0;
        this.dataList = new Object[this.count];
        
        // 递归获取节点数据
        this.rootNode.toArrayNode();

        return this.dataList;

    }

    // 检查索引是否在有效范围内
    private boolean isValidIndex(int index){
        if(index = count){
            return false;
        } else{
            return true;
        }
    }

    // 检查是否为有效数据
    private boolean isValidData(T data){
        if(data == null){
            return false;
        } else{
            return true;
        }
    }

    public T get(int index){
        if(!this.isValidIndex(index) || this.isEmpty()){
            return null ;
        }

        // 重置下标
        this.foot = 0;
        return this.rootNode.getNode(index).data;
    }

    public void set(int index, T data){
        if(!this.isValidIndex(index) || this.isEmpty() ){
            return ;
        }

        // 重置下标
        this.foot = 0;
        this.rootNode.getNode(index).data = data;
    }

    public boolean contains(T data){
        if(!isValidData(data) || this.isEmpty()){
            return false;
        }
        return this.rootNode.containsNode(data);
    }

    public boolean remove(T data){
        if(!isValidData(data) || this.isEmpty()){
            return false;
        }

        boolean removeResult = false;

        // 移除头节点
        if(this.rootNode.data.equals(data)){
            this.rootNode = this.rootNode.nextNode; 
            removeResult = true;
        } else{
            removeResult = this.rootNode.nextNode.removeNode(this.rootNode, data);
        }
        
        if(removeResult == true){
            this.count --;
        }

        return removeResult;
    }

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

    public void printLink(){
        Object[] list = this.toArray();
        
        if (list == null){
            System.out.println("null");
            return;
        }

        for(int i=0; i  3-> 4-> 5 ]

        System.out.println(link.get(2));
        // 4

        link.set(2, 6);
        System.out.println(link.get(2));
        // 6

        System.out.println(link.contains(10)); // false
        System.out.println(link.contains(5)); // true

        link.printLink();
        // [ 2-> 3-> 6-> 5 ]

        link.remove(2);
        System.out.println(link.contains(2));

        link.printLink();
        // [ 3-> 6-> 5 ]

        link.clean();
        link.printLink();
        // null

    }
}

144 综合实战：宠物商店

要求 宠物上架，下架，查询宠物信息

设计 宠物接口 -猫 -狗

宠物链表接口 -宠物链表

宠物商店 -宠物列表

根据接口标准定义信息

145 综合实战：超市购物车

类与标准有关，降低类与类之间耦合

146 Eclipse简介

Eclipse 中文意思：日蚀

开发工具 + 操作系统 + 中间件 + 数据库 Eclipse EE + Linux + Tomcat + MySQL

https://www.eclipse.org/downloads/

147 使用JDT开发Java程序

项目目录

src *.java 
bin *.class

UTF-8编码

快捷方式： 自动导包 代码格式化 代码纠正提示 代码提示 复制当前行 单行注释 代码自动生成

148 代码调试

断点break point

单步跳入 进入代码 单步跳过 直接到结果 单步返回 进入之后直接返回 恢复执行 取消断点，程序正常执行

149 junit测试工具

白盒测试 黑盒测试 用例测试 junit

testCase 一个测试 testSuite 一组测试