数组和链表的区别各有何优缺点(数组和链表的优缺点)

导语：数组和链表

数组

使用连续的内存空间存储一组相同数据类型的元素。使用下标的方式访问元素；适用于多读少更新（有序状态下的删除或者新增）的场景。

优点使用下标访问元素时间复杂度为O(1)。缺点占用的空间必须连续。扩容时需要将原数组中的元素移动到新的空间中。元素要求有序情况下，新增或者删除元素时需要移动数据。示例（leetcode-1588）

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

输入：arr = [1,4,2,5,3]

输出：58

解释：所有奇数长度子数组和它们的和为：

[1] = 1

[4] = 4

[2] = 2

[5] = 5

[3] = 3

[1,4,2] = 7

[4,2,5] = 11

[2,5,3] = 10

[1,4,2,5,3] = 15

我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

def sum(arr):    &34;&34;&34;     数组长度+1是为了代码简洁，sumArr长度比arr大1,       保存数组arr中前N项和    sumArr = [0 for i in range(l)]     由于单个元素即是元素数量为1的子区间，所以遍历过程中可以直接求和；    for i in range(1, l):     arr中前N项和    sumArr[i] = sum     子数组的最小长度    i = 3    while i < l:    j = i;    34;&34;链表节点&34;&34;&34;    :type head1, head1: ListNode    :rtype: ListNode    &34;& 链表A的长度    l1 = 0     链表B的长度  l2 = 0   返回值  r = None   计算链表B的长度    while hB:      l2 += 1      hB = hB.next     查找相同的节点    while hA and hB:        if hA == hB:            r = hA          break      else:            hA = hA.next            hB = hB.next    return r

示意图

本文内容由小涵整理编辑！