Java数据结构之单向链表,兼谈对象引用

Wesley13
• 阅读 555

昨天参加中兴笔试,被一个单项链表的编程题给弄崩了。于是这几天开始学习Java与数据结构之间的知识。上过数据结构的课程,当时使用C++演示的,导致了我一直觉得Java和数据结构之间的关系不是很大。直到今天,看了《Java数据结构与算法》,才如梦方醒。恩,要好好学习。下面贴一下我的代码:

package datastructure;
/**
 * Java 数据结构-单向链表
 * @author aaaafei
 *
 */
class Link{
    /**
     * 链表节点
     */
    int value;
    Link next;
    
    public Link(){
        
    }
    public Link(int value) {
        this.value = value;
    }
    
    public void display() {
        if(this != null){
            System.out.println("{value:" + this.value + "}");
        }
    }
}

class LinkList{
    /**
     * 链表
     */
    private Link first;
    
    public boolean isEmpty(){
        if(first == null){
            System.out.println("Null LinkList");
            return true;
        }else{
            return false;
        }
    }
    public void display(){
        Link node = this.first;
        if(!isEmpty()){
            System.out.print("{value:");
            while(node.next != null){
                System.out.print(node.value +"->");
                node = node.next;
            }
            System.out.println(node.value + "}");
        }    
    }
    public void insertFirst(int value){
        Link node = new Link(value);
        node.next = first;
        first = node;
    }
    public Link find(int value){
        Link node = this.first;
        if(!isEmpty()){
            while(node.value != value){
                if(node.next == null){
                    return null;
                }else{
                    node = node.next;
                }
            }
            return node;
        }
        System.out.println("Not Found");
        return null;
    }
    public void delete(int value){
        Link node = this.first;
        Link previous = this.first;
        if(!isEmpty()){
            while(node.value != value){
                if(node.next != null){
                    previous = node;
                    node = node.next;
                }
            }
            if(node == first){
                first = first.next;
            }else{
                previous.next = node.next;
            }
        }
    }
}

public class LinkNodeApp {

    public static void main(String args[]){
        LinkList linklist = new LinkList();
//        linklist.display();
        linklist.insertFirst(1);
        linklist.insertFirst(2);
        linklist.insertFirst(3);
        linklist.insertFirst(4);
        linklist.insertFirst(5);
        linklist.display();
        linklist.delete(3);
        linklist.display();
    }
}

这里先主要讲下基本组成部分,第一部分是构建链表中单个节点的结构,这里在一个节点中值放了一个值。第二部分是构建链表,并且在这个类中完成新增、查找和删除功能。第三部分是测试用的,用来测试LinkList中的方法效果。代码不复杂,接下来我想在继续说下我在写的过程中遇到的几个问题:

(1).链表新增时,都是将新来的数据插入链表的头部,比如第一个新增的数为1,第二个为2,那么链表就是由2指向1,就是2→1.如果依次新增1,2,3,4,5.那么指向关系就是5→4→3→2→1.

(2)我在进行查找时,遍历链表,一开始是用的向display方法中的遍历思路来进行遍历,在查看了那本经典之作后,才改为这种方式,确实这种方式更加直观,直接判断当前的节点的值是否相等,在判断是否为最后一个节点;而不是判断当前是否还有下个节点,在判断当前节点值是否相等。这样确实更巧妙。

(3)最后一个是我想重点阐述的部分。那就是在删除方法中,一开始我一直不理解,全程都没有对first对象进行操作,为什么就会删除成功呢。想了之后,意识到应该是Java中对象引用以及对象赋值的知识点,这部分不少教材都说的不是很清楚,我也说下我现在的理解,如有不对,请大家指正。

第一,上文中说的first对象,这种说法就是错误的。因为first只是一个对象引用变量,它不是一个对象,而是指向一个对象的值。那么什么是对象呢。举个例子,Link node; node = new Link(); 这两句中,node是对象引用值,这是刚创建出来,它是null,也就是没有指向任何一个对象。new表明在堆空间中开辟存储区域,存储对象实体,Link表明是Link类型的实体,()表明调用Link类的构造方法。=符号的含义就是将node指向堆空间中的对象实体。例如在写一句,Link node2 = node;表明新建一个对象引用的值,指向和node相同,那么现在就是说有两个对象引用指向同一个实体。图不是很准确,毕竟链表在内存中并不是连续的。

Java数据结构之单向链表,兼谈对象引用

那么就用这个知识点来看下display方法,方法体中创建一个新的对象引用值,共同指向一个对象实体,其中first的指向一直没有变,而node的指向却是在一格一格的向后跳。图不是很准确,毕竟链表在内存中并不是连续的。所以,因为first一直指向着,所以这个内存实体一直存在,并没有被JVM当做垃圾给回收了。

第二,用这个知识点来看delete方法,同样有下面的图:

Java数据结构之单向链表,兼谈对象引用

一开始,first、node和previous都是同一个指向,接下来,三者有了不同的指向,接着发现了要删除的元素了,previous.next = node.next,表达了这样的含义,将previous指向的节点的next值变为node指向的节点的next值,而这时first依然指向第一个节点,但是之后的节点的内容已经被改变了。这时,node指向那个节点就已经被舍弃了,随着node生命周期的结束,其指向的对象实体,就被JVM当做垃圾了。

因此,正是对象引用的特点,才有了delete中的写法。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Wesley13 Wesley13
2年前
Java爬虫之JSoup使用教程
title:Java爬虫之JSoup使用教程date:201812248:00:000800update:201812248:00:000800author:mecover:https://imgblog.csdnimg.cn/20181224144920712(https://www.oschin
Stella981 Stella981
2年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Stella981 Stella981
2年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Docker 部署SpringBoot项目不香吗?
  公众号改版后文章乱序推荐,希望你可以点击上方“Java进阶架构师”,点击右上角,将我们设为★“星标”!这样才不会错过每日进阶架构文章呀。  !(http://dingyue.ws.126.net/2020/0920/b00fbfc7j00qgy5xy002kd200qo00hsg00it00cj.jpg)  2
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
4个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这