2.数组缺点 1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。...如果代码对内存的使用非常苛刻，那数组就更适合。 应用 1.如何分别用链表和数组实现LRU缓冲淘汰策略？ 1）什么是缓存？...初始已排序区间只有一个元素，即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置，直到未排序区间为空。...选择排序将数组分成已排序区间和未排序区间。...初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。
与数组一样，链表是一种线性数据结构。与数组不同，链表元素不存储在连续的位置；元素使用指针链接。 为什么使用链表？ 数组可用于存储类似类型的线性数据，但数组有以下限制。...2)在元素数组中插入一个新元素是昂贵的，因为必须为新元素创建房间，并且必须移动现有元素才能创建房间。 例如，在一个系统中，如果我们在数组 id[] 中维护一个已排序的 ID 列表。...而如果我们要插入一个新的ID 1005，那么为了保持排序顺序，我们必须将1000之后的所有元素（不包括1000）移动。 除非使用某些特殊技术，否则删除数组的代价也很高。...所以我们不能用它的默认实现有效地对链表进行二分搜索。在这里阅读。 2)列表的每个元素都需要额外的指针存储空间。 3) 对缓存不友好。...): self.data = data # 分配数据 self.next = None # 将 next 初始化为 null class LinkedList: # 初始化链表对象的函数
数组：连续存储的有序元素集合 1.1 创建和访问数组 1.2 数组的搜索与排序 2. 链表：非连续存储的动态数据结构 2.1 单链表与双链表 2.2 链表的操作与应用 3....// 创建一个整数数组 int[] intArray = new int[5]; // 初始化数组元素 intArray[0] = 10; intArray[1] = 20; intArray[2]...线性搜索遍历整个数组以查找目标元素，而二分搜索则利用已排序数组的性质在较短时间内找到目标元素。...intArray[i] == target) { System.out.println("找到了目标元素在索引：" + i); break; } } // 二分搜索（数组必须已排序...插入删除：链表插入和删除效率高，数组的插入删除可能导致数据搬移。 访问速度：数组访问速度较快，链表需要遍历节点。 空间消耗：链表需要额外的指针存储引用，空间消耗相对较大。
1．设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客 姓氏的字母序相链。例如，下面是张某个时刻的乘客表。...设av是可用数组空间的小下标，当有客户要订票时，将其姓名写入该单元的data域，然后在静态链表中 查找其插入位置。...void Insert（unode user[max],int av）∥user是静态双向链表，表示飞机票订票系统，元素包含data、Llink和Rlink三个域，结点按来客姓名排序。...也未考虑从空开始建立链表。增加乘客时也 未考虑姓名相同者（实际系统姓名不能做主关键字）。完整系统应有（1）初始化，把整个数组空间初始化成双 向静态链表，全部空间均是可利用空间。（2）申请空间。...当有乘客购票时，要申请空间，直到无空间可用为 止。（3）释放空间。当乘客退票时，将其空间收回。由于空间使用无优先级，故可将退票释放的空间作为下个 可利用空间，链入可利用空间表中。
4、数据结构和算法 数据结构考点 数组和链表的区别； 链表的操作，如反转，链表环路检测，双向链表，循环链表相关操作； 队列，栈的应用； 二叉树的遍历方式及其递归和非递归的实现； 红黑树的旋转 算法考点...外部排序：应掌握如何利用有限的内存配合海量的外部存储来处理超大的数据集，写不出来也要有相关的思路。 考点扩展： 哪些排序是不稳定的，稳定意味着什么？ 不同数据集，各种排序最好或最差的情况？...如何优化算法？(以空间换时间) 5、Java集合框架 compare和自定义的compare 6、Map集合 HashMap、HashTable、ConccurentHashMap的区别？...使锁更细化 数据结构进行优化：数组+链表+红黑树 synchronized只锁定链表和红黑树的首节点。...多线程环境下如何进行扩容？ Hash Map、 Hashtable、 ConccurentHashMap三者区别 Hash Map线程不安全，数组+链表+红黑树。
包括两部分数据 Mark Word（标记字段） Mark Word被设计成一个非固定的数据结构以便在极小的空间内存存储尽量多的数据，它会根据对象的状态复用自己的存储空间 包括：哈希码（HashCode...解决方案 volatile方案： 禁止重排序 基于类初始化的解决方案 利用classloder的机制来保证初始化instance时只有一个线程。...弱一致性表现淋漓尽致 ConcurrentSkipListMap 第三种key-value数据结构：SkipList（跳表） SkipList 平衡二叉树结构 Skip list让已排序的数据分布在多层链表中...，level是通过一定的概率随机产生的 每一层都是一个有序的链表，默认是升序，也可以根据创建映射时所提供的Comparator进行排序，具体取决于使用的构造方法 最底层(Level 1)的链表包含所有元素...: 原子更新整型 AtomicLong:原子更新长整型 数组 通过原子的方式更新数组里的某个元素 AtomicIntegerArray: 原子更新整型数组里的元素 AtomicLongArray
TreeMap 和 TreeSet 在排序时如何比较元素？Collections 工具类中的 sort()方法如何比较元素？...HashTable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的 TreeMap： 红黑树（自平衡的排序二叉树） 哪些集合类是线程安全的？...Java.util.concurrent.BlockingQueue是一个队列，在进行检索或移除一个元素的时候，它会等待队列变为非空；当在添加一个元素时，它会等待队列中的可用空间。...我们不需要担心等待生产者有可用的空间，或消费者有可用的对象，因为它都在BlockingQueue的实现类中被处理了。...理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。
如果你了解通用模式，则可以将它们用作模板来解决无数微小变化的其他许多问题。 在这里，我列出了可用于解决任何编码面试问题的前14种模式，以及如何识别每种模式以及每种模式的一些示例性问题。...在许多情况下，两个指针可以帮助你找到具有更好空间或运行时复杂性的解决方案。 确定何时使用"两指针"方法的方法： 在处理排序数组（或链接列表）并且需要找到一组满足某些约束的元素时，它将遇到一些问题。...如何确定何时使用快速和慢速模式？ 该问题将处理链表或数组中的循环 当你需要知道某个元素的位置或链表的总长度时。 什么时候应该在上面提到的"两指针"方法上使用它？...它们将是涉及编号在给定范围内的排序数组的问题 如果问题要求你在排序/旋转数组中查找缺失/重复/最小的数字 具有循环排序模式的问题： 查找丢失的号码（简单） 查找最小的遗漏正数（中） 6、就地反转链表 在很多问题中...如何识别K-way合并模式： 该问题将出现排序的数组，列表或矩阵 如果问题要求你合并排序列表，请在排序列表中找到最小的元素。
因为我认为 选择 排序 和 插入排序 相比 选择排序是从未排序数据中找到合适的 和 前面的换，打乱了顺序不稳定，链表和数组没有太大区别。...个赋值操作，选择排序每轮也需要移动一个，适用于 数组连续空间下标访问，但是不稳定 个人感觉 链表适合 插入排序 稳定 适合向后移动 数组适合 冒泡排序和 选择排序，插入排序会出现 大量数据向后移动1...四、插入排序 插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素，即数组第一个元素。...在未排序区间取出一个元素插入到已排序区间的合适位置，直到未排序区间为空。 空间复杂度：插入排序是原地排序算法。 时间复杂度： 1. 最好情况：O(n)。 2....五、选择排序 选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。
【02-数组和链表】 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。 数组、链表、队列、栈等都是线性表结构。...2.数组缺点 (1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。...【插入排序（Insertion Sort）】 我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。...插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。 重复这个过程，直到未排序区间中元素为空，算法结束。...【选择排序（Selection Sort）】 选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
01 数组 数组是用一组连续的内存空间,来存储一组具有相同类型的数据的结构，该空间具有固定的大小。所以其特点就是空间连续、数据类型相同、空间大小固定、可以进行随机访问。...更新：更新一个给定索引位置处的已存在元素的值 因为数组的大小是固定的，所以从数组中插入和删除元素是不能直接完成的。必须要先分配一个新的数组空间。...数组结构的应用： 作为其他数据结构的底层结构。例如数组列表、堆、hash表等。 用于不同的排序算法。例如插入排序、快速排序、冒泡排序以及合并排序。...07 堆（Heap） 堆是二叉树的一个特例，其特点是某个节点的值总是不大于或不小于其父节点的值。下面我看下堆是如何表示的。堆即可以用树形结构来表示，也可以使用数组来表示。...堆的应用 用于堆排序算法 用于优先级队列 用于查找数组中第K大或第K小的值的算法 以上我们简单介绍了7种常见的数据结构以及其在实际中的应用，希望对你所有帮助。
数组（Array） 2. 链表（Linked List） 3. 栈（Stack） 4. 队列（Queue） 算法 1. 排序算法 2. 搜索算法 3. 递归算法 编写高效的代码的关键考虑因素 1....if arr[i] == target: return i return -1 # 二分查找（假设数组已排序） def binary_search(arr, target...解决复杂问题 某些问题可能非常复杂，没有合适的算法和数据结构，将难以解决。例如，图算法可用于解决社交网络分析或路线规划等问题。 4....链表（Linked List） 链表是一种线性数据结构，由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以是单向的或双向的。...空间复杂度 空间复杂度表示算法执行所需的内存空间与输入规模之间的关系。与时间复杂度类似，选择具有较低空间复杂度的算法可以节省内存资源。 3.
，一般在函数中会将已存在对象的数据成员的值复制一份到新创建的对象中。...key 和 value ， key是可以重复的，所有元素的值都会自动排序，key不允许重复 vector 连续存储的容器，内存分配在堆上面，动态数组 底层实现：数组 两倍容量增长：vector一次性分配好内存...， 在增加新元素的时候，如果没有超过当前的容量，那么直接添加，然后调整迭代器，如果超过了当前的容量， 则vector会重新配置原数组的内存的2倍空间，将原空间元素内存拷贝到新空间，释放掉原空间，且此时迭代器会失效...，如vector，stack，list及ostream_iterator的扩展 迭代器时如何删除元素的？...CPLUS_INCUCLUDE_PATH/C_INCLUDE_PATH中指定的头文件路径 malloc原理 向内存申请一块连续可用的空间，并返回指向这块空间的指针 如果开辟成功，则返回一个指向开辟好空间的指针
列表的基本思想是将元素按照一定顺序组织起来，并且支持在列表中插入、删除和遍历元素。列表可以使用数组或链表实现。在数组实现中，列表的元素在内存中是连续的，而在链表实现中，元素可以在内存中任意位置。...2、内置列表的初始化当然C#中链表的初始化可以使用LinkedList类。...操作可用于查询和操作列表。...插入和删除效率低：由于需要维护元素的顺序，插入和删除操作比较耗时。空间浪费：由于列表内部存储的元素是连续的，当需要插入或删除元素时，可能需要移动大量元素，导致空间浪费。...栈和队列的实现：栈和队列都可以通过列表来实现。迭代器：列表可以被用作迭代器，使得可以对数据进行迭代处理。图的遍历：图的遍历算法中，可以使用列表来存储已访问和未访问的节点。
定义： 单链表：各个结点散落在内存中的各个角落，每个结点有指向下一个节点的指针(下一个结点在内存中的地址); 静态链表：用数组的方式来描述线性表的链式存储结构: 分配一整片连续的内存空间，各个结点集中安置...型数组； 3.静态链表基本操作的实现 初始化静态链表：把a[0]的next设为-1 查找某个位序（不是数组下标，位序是各个结点在逻辑上的顺序）的结点：从头结点出发挨个往后遍历结点，时间复杂度O=...A： 不一定，要看实际需求； 排序算法的分类： 内部排序： 数据都在内存——关注如何使时间、空间复杂度更低； 外部排序： 数据太多，无法全部放入内存——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少...（不一定是第一个）把待排序序列“划分”为两个部分，左边更小，右边更大，该元素的最终位置已确认 算法实现（重点） //用第一个元素将待排序序列划分为左右两个部分 int Partition(int A[]...可理解为顺序存储的二叉树，注意 可以将堆视为一棵 完全二叉树 (✔) 可以将堆视为一棵 二叉排序树 (✖) 大根堆：完全二叉树中，根 ≥ 左、右 小根堆：完全二叉树中，根 ≤ 左、右 如何基于“堆”进行排序
关联容器内的元素是排序的。插入元素时，容器会按一定的排序规则将元素放到适当的位置上，因此插入元素时不能指定位置。 「set」: 含有 Key 类型对象的已排序集。...[16] STL中的vector的实现，是怎么扩容的 vector 为空的时候没有预分配空间，每次添加一个元素时，会判断当前是否还有剩余可用空间，如果没有则进行试探性扩容，并且把内存拷贝到新申请的内存空间上...「list」是双向链表，内部存储可能是不连续的空间，通过指针链接这些不连续的空间，不支持随机访问。...说一下什么是内存泄漏，如何避免 是指程序在申请内存后，无法释放已申请的内存空间，称之为内存泄露。...[36] ① 冒泡排序 ② 选择排序 ③ 插入排序 ④ 希尔排序 ⑤ 快速排序 ⑥ 归并排序 ⑦ 堆排序 链表的特点和操作 特点 ① 采用动态存储分配，不会造成内存浪费和溢出。
用于识别使用二指针的时机的方法： 可用于你要处理排序数组（或链接列表）并需要查找满足某些约束的一组元素的问题 数组中的元素集是配对、三元组甚至子数组 下面是一些满足二指针模式的问题： 求一个排序数组的平方...如何判别使用快速和慢速模式的时机？ 处理链表或数组中的循环的问题 当你需要知道特定元素的位置或链表的总长度时 何时应该优先选择这种方法，而不是上面提到的二指针方法？...涉及数值在给定范围内的排序数组的问题 如果问题要求你在一个排序/旋转的数组中找到缺失值/重复值/最小值 循环排序模式的问题： 找到缺失值（简单） 找到最小的缺失的正数值（中等） 6．原地反转链表 在很多问题中...拓扑排序 拓扑排序可用于寻找互相依赖的元素的线性顺序。比如，如果事件 B 依赖于事件 A，那么 A 在拓扑排序时位于 B 之前。 这个模式定义了一种简单方法来理解执行一组元素的拓扑排序的技术。...该模式看起来是这样的： 1．初始化。
C/C++和Java有什么区别 手撕算法 连续子数组最大和 合并两个排序链表 C/C++ sizeof union和struct的区别 指针和数组的区别 多态 虚函数 static关键字 计网 网络体系结构...合并两个排序链表 可参考：链表面试题(动图详解)-明明做出来了却为什么没有Offer?...Struct 数据对齐原则：内存按结构成员的先后顺序排列，当排到该成员变量时，其前面已摆放的空间大小必须是该成员类型大小的整倍数，如果不够则补齐，以此向后类推。 各成员间互不影响。...指针数组相当于一个变量，存放的是其它变量在内存中的地址储存多个相同类型数据的集合同类型指针可相互赋值数组只能一个个拷贝元素存储很灵活，可指向任意类型的数据存在一块连续的物理空间上，逻辑上的多维数组其实存的是一维...，结束时释放空间，默认初始化为0，使用时可以改变其值。
TreeMap：TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的...链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被 Hash 后，得到数组下标，把数据放在对应下标元素的链表上。...如果哈希桶数组很大，即使较差的 Hash 算法也会比较分散，如果哈希桶数组数组很小，即使好的 Hash 算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小...那么通过什么方式来控制 map 使得 Hash 碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的 Hash 算法和扩容机制。...默认的负载因子 0.75 是对空间和时间效率的一个平衡选择，建议不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子 Load factor 的值；相反，
，空间复杂度：O(1)。 插入排序：将待排序元素逐个插入到已排序序列的合适位置，形成有序序列。时间复杂度：最好情况下O(n)，最坏情况下O(n^2)，平均情况下O(n^2)，空间复杂度：O(1)。...选择排序（Selection Sort）：通过不断选择未排序部分的最小（或最大）元素，并将其放置在已排序部分的末尾（或开头）。...，交换左右指针所指向的元素 5，重复3，4，直到左指针超过右指针，此时，比基准小的值就都会放在基准的左边，比基准大的值会出现在基准的右边 6，然后分别对基准的左右两边重复以上的操作，直到数组完全排序 注意这里的基准该如何选择...HashTable：数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的 TreeMap：红黑树（自平衡的排序二叉树） ConcurrentHashMap：Node数组...数组：数组的内存空间是连续的，随机访问的时间复杂度是O1，适用于需要按索引访问元素的场景，但是插入和删除元素较慢，时间复杂度是On 链表：链表是由节点组成，节点之间是分散存储的，内存不连续，每个节点存储数据和指向下一个节点的指针
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
云直播
实时音视频
