热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

数据结构系列1数组和链表

数组,链表,l

数组

数组是一种线性表数据结构,它是一组连续的内存空间。它存储一组具有相同类型的数据。

查询: O(1)
插入: O(n)
删除: O(n)

思考题: 数组是如何实现元素的快速访问的呢?

计算会为记录每个数据类型的大小,由于数据的内存空间是连续的,所以知道了首地址,知道的元素的下标,就可以计算出来:
findItemAddr = firstItemAddr + sizeOf(dataType) * index

思考题: 数组的下标为什么从0开始的呢?

从数据存储的内存模型上看,下标其实是"偏移". 正是因为下标是从0开始的,所以我们才能使用上面的计算公式来确定元素的问题。如果从1开始的时候,上面的公式就变成了 findItemAddr = firstItemAddr + sizeOf(dataType) * (index-1)
这样对CPU来说,是多一次减法指令.

链表

非定长的,地址不连续的. 链表通过指针将一组零散的内存块串联在一起。

查找: O(n)
插入,删除 O(1)

LeetCode题目

206反转链表

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

代码实现
迭代

public ListNode reverseList(ListNode head) {
ListNode cur = null;
ListNode pre = null;
while (head != null) {
(cur = new ListNode(head.val)).next = pre;
pre = cur;
head = head.next;
}
return cur;
}

时间复杂度O(n)
, 空间复杂度O(n)

递归实现

public ListNode reverseList(ListNode head) {
ListNode cur = null;
ListNode reverse = reverse(head, cur);
return reverse;
}
private ListNode reverse(ListNode head,
ListNode pre)
{
ListNode newHead = null;
if (head != null) {
newHead = reverse(head.next, head);
head.next = pre;
} else {
newHead = pre;
}
return newHead;
}

时间复杂度O(n)
, 空间复杂度O(n)

最优解
迭代

public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}

时间复杂度O(n)
, 空间复杂度O(n)

递归

public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}

时间复杂度O(n)
, 空间复杂度O(n)

24两两交换链表中的节点

题目描述

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

给定 1->2->3->4, 你应该返回 2->1->4->3.

代码实现

public ListNode swapPairs(ListNode head) {

ListNode newHead = head;
ListNode pre = null;
while (null != head && null != head.next) {
ListNode n2 = head.next;
head.next = head.next.next;

if(null == pre){
newHead = n2;
}else{
pre.next = n2;
}

n2.next = head;
pre = head;
head = head.next;
}

return newHead;
}

国庆节快乐

扫描二维码

获取更多精彩

方家小白




推荐阅读
  • Spring框架的核心组件与架构解析 ... [详细]
  • 本课程深入探讨了 Python 中自定义序列类的实现方法,涵盖从基础概念到高级技巧的全面解析。通过实例演示,学员将掌握如何创建支持切片操作的自定义序列对象,并了解 `bisect` 模块在序列处理中的应用。适合希望提升 Python 编程技能的中高级开发者。 ... [详细]
  • 在腾讯云服务器上部署Nginx的详细指南中,首先需要确保安装必要的依赖包。如果这些依赖包已安装,可直接跳过此步骤。具体命令包括 `yum -y install gcc gcc-c++ wget net-tools pcre-devel zlib-devel`。接下来,本文将详细介绍如何下载、编译和配置Nginx,以确保其在腾讯云服务器上顺利运行。此外,还将提供一些优化建议,帮助用户提升Nginx的性能和安全性。 ... [详细]
  • Netty框架中运用Protobuf实现高效通信协议
    在Netty框架中,通过引入Protobuf来实现高效的通信协议。为了使用Protobuf,需要先准备好环境,包括下载并安装Protobuf的代码生成器`protoc`以及相应的源码包。具体资源可从官方下载页面获取,确保版本兼容性以充分发挥其性能优势。此外,配置好开发环境后,可以通过定义`.proto`文件来自动生成Java类,从而简化数据序列化和反序列化的操作,提高通信效率。 ... [详细]
  • 本文探讨了如何利用Java 8 Stream API 对数组进行高效排序和筛选处理。具体而言,通过 `stream()` 方法将 `listResult` 转换为流,然后使用 `sorted(Comparator.comparing())` 方法按伴随度进行降序排序,并最终收集结果。此外,还介绍了如何结合过滤条件进一步优化数据处理流程,提升代码的可读性和执行效率。 ... [详细]
  • HBase Java API 进阶:过滤器详解与应用实例
    本文详细探讨了HBase 1.2.6版本中Java API的高级应用,重点介绍了过滤器的使用方法和实际案例。首先,文章对几种常见的HBase过滤器进行了概述,包括列前缀过滤器(ColumnPrefixFilter)和时间戳过滤器(TimestampsFilter)。此外,还详细讲解了分页过滤器(PageFilter)的实现原理及其在大数据查询中的应用场景。通过具体的代码示例,读者可以更好地理解和掌握这些过滤器的使用技巧,从而提高数据处理的效率和灵活性。 ... [详细]
  • 在C#中开发MP3播放器时,我正在考虑如何高效存储元数据以便快速检索。选择合适的数据结构,如字典或数组,对于优化性能至关重要。字典能够提供快速的键值对查找,而数组则在连续存储和遍历方面表现优异。根据具体需求,合理选择数据结构将显著提升应用的响应速度和用户体验。 ... [详细]
  • 在Python网络编程中,多线程技术的应用与优化是提升系统性能的关键。线程作为操作系统调度的基本单位,其主要功能是在进程内共享内存空间和资源,实现并行处理任务。当一个进程启动时,操作系统会为其分配内存空间,加载必要的资源和数据,并调度CPU进行执行。每个进程都拥有独立的地址空间,而线程则在此基础上进一步细化了任务的并行处理能力。通过合理设计和优化多线程程序,可以显著提高网络应用的响应速度和处理效率。 ... [详细]
  • 揭秘腾讯云CynosDB计算层设计优化背后的不为人知的故事与技术细节
    揭秘腾讯云CynosDB计算层设计优化背后的不为人知的故事与技术细节 ... [详细]
  • 探索偶数次幂二项式系数的求和方法及其数学意义 ... [详细]
  • 在分析 Nginx 配置不当导致的频繁重定向问题时,发现项目根路径不为空是主要原因。为避免前后端之间的反复重定向,建议在配置中增加一层路径映射。具体配置示例如下:`server { listen 80; server_name pmp.mussessein.cn; location / { root /path/to/project; try_files $uri $uri/ /index.html; } }`。通过这种方式,可以有效减少不必要的重定向,提升用户体验和系统性能。 ... [详细]
  • 为了在 Oracle 中实现将多个绑定变量一次性插入到查询语句的 WHERE 子句中,可以利用 SQL 的字符串处理功能将输入的字符串转换为行集,并将其作为普通联接的输入。例如,可以通过定义一个 VARCHAR2 类型的变量 `acct` 来存储绑定变量的值,然后使用动态 SQL 执行查询。这种方法不仅提高了查询的灵活性,还简化了多条件筛选的实现。 ... [详细]
  • 利用Python进行学生学业表现评估与成绩预测分析
    利用Python进行学生学业表现评估与成绩预测分析 ... [详细]
  • 设计实战 | 10个Kotlin项目深度解析:首页模块开发详解
    设计实战 | 10个Kotlin项目深度解析:首页模块开发详解 ... [详细]
  • 利用Python与Android进行高效移动应用开发
    通过结合Python和Android,可以实现高效的移动应用开发。首先,需要安装Scripting Layer for Android (SL4A),这是一个开源项目,旨在为Android系统提供脚本语言支持。SL4A不仅简化了开发流程,还允许开发者使用Python等高级语言编写脚本,从而提高开发效率和代码可维护性。此外,SL4A还支持多种其他脚本语言,进一步扩展了其应用范围。通过这种方式,开发者可以快速构建功能丰富的移动应用,同时保持较高的灵活性和可扩展性。 ... [详细]
author-avatar
9158Zsc
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有