专栏首页营旗的小记录算法:数组和链表-理论

算法:数组和链表-理论


我们先看看百度百科关于数组和链表的介绍吧。

数组

所谓数组,是有序的元素序列。若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。

数组

既然我们刚刚讲到了算法的时间复杂度。

数组访问的时间复杂度是多少呢!O(1)。

数组插入和删除的时间复杂度呢!

下标保持,变量改变

插入:平均O(n)。

删除:平均O(n)。

Java的数组是怎么实现

那既然我们在学Java,那看看Java的数组是怎么实现的吧。

java.lang.reflect.Array类

可以看到,Array类构造方法是私有的,剩下的大部分是未实现的静态方法。

那我们看看有没有什么类继承Array类,找找API,发现并没有?

???三个问号,怎么没有呢!那我们Google看看。

先上链接,自己看会。我得到的信息是,这是一个java的规范

Java里数组不是类,所以也没有对应的Class文件。数组类型是由JVM从元素类型合成出来的。

下面是个人猜测

我们知道,一个Java程序的运行,先要经过编译器生成字节码文件,JVM再读取字节码,生成机器码,最后到计算机运行。

int[] array = new int[n];

既然数组不是一个类,那么生成字节码是

。。。
int[] list1; 
descriptor: [I 
flags:
。。。

那么告诉JVM的是 int 一个整型数据类型,[] 是要一个连续的内存空间 。再把int值存入这个连续的存储空间中,这样就产生了一个常用数组。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

链表

简单讲,就是一个当前的对象中,保存有下一个对象的引用。下一个对象保存有下下一个对象的引用。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

Java的链表是怎么实现

LinkedList继承结构图

根据源码可以大概知道,我们先看看添加的方法。下面代码有注释,就不一一说了。

public class LinkedList<E>{
//添加
 public boolean add(E e) {
        linkLast(e);
        return true;
    }
//实际添加的方法
void linkLast(E e) {
        final Node<E> l = last;//获取上一个节点
        final Node<E> newNode = new Node<>(l, e, null);//获取当前添加元素的节点
        last = newNode;//预先把当前节点保存为上一节点。 相当首节点的概念
        if (l == null)//判断上一个节点是否为空/
            first = newNode;
        else//节点不为空
            l.next = newNode;//设上一节点的下一个节点为当前添加的节点
        size++;
        modCount++;
    }
private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
transient Node<E> first;
transient Node<E> last;
transient int size = 0;

}

这一篇文章为数组和链表的理论

数组和链表算法的实战为 : 算法:数组和链表-实战

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Golang 基础篇

    我们使用go run运行后,会在控制台终端看到Hello, 世界的输出。我们来看下这段代码:

    爱敲代码的猫
  • Java 基础 | Collection 集合概览

    老读者都知道,我是自学转行到 java 的。那时迫于生存压力,学得比较快,很多知识点仅停留在会用的层面。最近,光会用不知道原理,没什么意思。每次使用时都是机械性...

    一个优秀的废人
  • Arrays.asList 存在的坑

    阿里巴巴 java 开发规范说到使用工具类 Arrays.asList() 方法把数组转换成集合时,不能使用其修改集合相关的方法,它的 add/remove/c...

    一个优秀的废人
  • 面试官常问的 20 道 Java 题目(附答案)

    2. Math.round(11.5)等于多少?Math.round(-11.5)等于多少?

    一个优秀的废人
  • Java 基础 | Object 源码解

    Java 是一门面向对象的语言,在 Java 里面一切都可以看作是一个对象,而 Java 里面所有的对象都默认继承于 Object 类,所以狗哥今天就从源码角度...

    一个优秀的废人
  • Golang 包管理(一)

    我们在使用其他语言,比如Java,是有包的概念的,它是Java语言中组织我们的Java文件的一个概念,比如java.lang这个包,他里面有很多我们常用的类,比...

    爱敲代码的猫
  • 代码中太多 if else 怎么办?

    前段时间,我将公司系统中的批量审单的功能进行了重构,用到了java的并发编程进行异步化处理,数据库的乐观锁机制处理多线程并发更新数据。其中批量审单的业务处理涉及...

    一个优秀的废人
  • MyBatis 动态 SQL 详解

    MyBatis 令人喜欢的一大特性就是动态 SQL。 在使用 JDBC 的过程中, 根据条件进行 SQL 的拼接是很麻烦且很容易出错的。MyBatis 动态 S...

    一个优秀的废人
  • 推荐两个关于 Java 面试的 Github 项目

    哈喽,大家好。相信大家都知道金九银十,在人才市场上是指每年的 9 月和 10 月是企业的招聘高峰期。这个时候企业往往有大量招聘需求,求职者在这个时候就找工作无疑...

    一个优秀的废人
  • 图解 Java 垃圾回收机制

    自动垃圾回收是一种在堆内存中找出哪些对象在被使用,还有哪些对象没被使用,并且将后者删掉的机制。

    一个优秀的废人

扫码关注云+社区

领取腾讯云代金券