热门标签 | 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;
}

国庆节快乐

扫描二维码

获取更多精彩

方家小白




推荐阅读
  • 计算机存储系统的层次结构及其优势
    本文介绍了计算机存储系统的层次结构,包括高速缓存、主存储器和辅助存储器三个层次。通过分层存储数据可以提高程序的执行效率。计算机存储系统的层次结构将各种不同存储容量、存取速度和价格的存储器有机组合成整体,形成可寻址存储空间比主存储器空间大得多的存储整体。由于辅助存储器容量大、价格低,使得整体存储系统的平均价格降低。同时,高速缓存的存取速度可以和CPU的工作速度相匹配,进一步提高程序执行效率。 ... [详细]
  • 本文介绍了Redis的基础数据结构string的应用场景,并以面试的形式进行问答讲解,帮助读者更好地理解和应用Redis。同时,描述了一位面试者的心理状态和面试官的行为。 ... [详细]
  • Java容器中的compareto方法排序原理解析
    本文从源码解析Java容器中的compareto方法的排序原理,讲解了在使用数组存储数据时的限制以及存储效率的问题。同时提到了Redis的五大数据结构和list、set等知识点,回忆了作者大学时代的Java学习经历。文章以作者做的思维导图作为目录,展示了整个讲解过程。 ... [详细]
  • 本文详细介绍了PHP中与URL处理相关的三个函数:http_build_query、parse_str和查询字符串的解析。通过示例和语法说明,讲解了这些函数的使用方法和作用,帮助读者更好地理解和应用。 ... [详细]
  • 本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用,包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]
  • 本文介绍了Perl的测试框架Test::Base,它是一个数据驱动的测试框架,可以自动进行单元测试,省去手工编写测试程序的麻烦。与Test::More完全兼容,使用方法简单。以plural函数为例,展示了Test::Base的使用方法。 ... [详细]
  • 基于事件驱动的并发编程及其消息通信机制的同步与异步、阻塞与非阻塞、IO模型的分类
    本文介绍了基于事件驱动的并发编程中的消息通信机制,包括同步和异步的概念及其区别,阻塞和非阻塞的状态,以及IO模型的分类。同步阻塞IO、同步非阻塞IO、异步阻塞IO和异步非阻塞IO等不同的IO模型被详细解释。这些概念和模型对于理解并发编程中的消息通信和IO操作具有重要意义。 ... [详细]
  • Android JSON基础,音视频开发进阶指南目录
    Array里面的对象数据是有序的,json字符串最外层是方括号的,方括号:[]解析jsonArray代码try{json字符串最外层是 ... [详细]
  • 本文探讨了C语言中指针的应用与价值,指针在C语言中具有灵活性和可变性,通过指针可以操作系统内存和控制外部I/O端口。文章介绍了指针变量和指针的指向变量的含义和用法,以及判断变量数据类型和指向变量或成员变量的类型的方法。还讨论了指针访问数组元素和下标法数组元素的等价关系,以及指针作为函数参数可以改变主调函数变量的值的特点。此外,文章还提到了指针在动态存储分配、链表创建和相关操作中的应用,以及类成员指针与外部变量的区分方法。通过本文的阐述,读者可以更好地理解和应用C语言中的指针。 ... [详细]
  • 本文介绍了在Vue项目中如何结合Element UI解决连续上传多张图片及图片编辑的问题。作者强调了在编码前要明确需求和所需要的结果,并详细描述了自己的代码实现过程。 ... [详细]
  • javascript  – 概述在Firefox上无法正常工作
    我试图提出一些自定义大纲,以达到一些Web可访问性建议.但我不能用Firefox制作.这就是它在Chrome上的外观:而那个图标实际上是一个锚点.在Firefox上,它只概述了整个 ... [详细]
  • JavaSE笔试题-接口、抽象类、多态等问题解答
    本文解答了JavaSE笔试题中关于接口、抽象类、多态等问题。包括Math类的取整数方法、接口是否可继承、抽象类是否可实现接口、抽象类是否可继承具体类、抽象类中是否可以有静态main方法等问题。同时介绍了面向对象的特征,以及Java中实现多态的机制。 ... [详细]
  • 本文介绍了Oracle数据库中tnsnames.ora文件的作用和配置方法。tnsnames.ora文件在数据库启动过程中会被读取,用于解析LOCAL_LISTENER,并且与侦听无关。文章还提供了配置LOCAL_LISTENER和1522端口的示例,并展示了listener.ora文件的内容。 ... [详细]
  • 本文介绍了使用PHP实现断点续传乱序合并文件的方法和源码。由于网络原因,文件需要分割成多个部分发送,因此无法按顺序接收。文章中提供了merge2.php的源码,通过使用shuffle函数打乱文件读取顺序,实现了乱序合并文件的功能。同时,还介绍了filesize、glob、unlink、fopen等相关函数的使用。阅读本文可以了解如何使用PHP实现断点续传乱序合并文件的具体步骤。 ... [详细]
  • eclipse学习(第三章:ssh中的Hibernate)——11.Hibernate的缓存(2级缓存,get和load)
    本文介绍了eclipse学习中的第三章内容,主要讲解了ssh中的Hibernate的缓存,包括2级缓存和get方法、load方法的区别。文章还涉及了项目实践和相关知识点的讲解。 ... [详细]
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社区 版权所有