它是一个链表,一个数组？我四处搜寻,只发现有人在猜测.我的C知识不足以查看源代码.
今天在课堂上,我们了解到从列表中检索元素是O(1)在Python中.为什么会这样？假设我有一个包含四个项目的列表,例如:
li = ["perry", 1, 23.5, "s"]
这些项目的内存大小不同.因此,不可能获取内存位置li[0]并添加每个元素大小的三倍来获取内存位置li[3].那么解释器如何知道在何处li[3]不必遍历列表以便检索元素？
许多编程语言提供内置数据结构,但已知某些数据结构(例如链表)非常易于实现,因此,语言通常不包括内置数据结构.某些语言(如C++)具有(如std::list双链接),以及Java(如LinkedList<T>双链接).
例如,Python已经在其库中内置了几个数据结构,包括列表,元组,集合,字典(甚至不需要导入),以及collections库中的数据结构.它没有内置的LinkedList数据结构,因为在Python中已经很容易实现自己的LinkedList.
请注意,Python列表的基础数据结构实际上是一个数组,如"Python列表的基础数据结构是什么？"中所述..此外,双端队列中collections是一个双端队列,其应具有缺少的功能,因为它通常不会支持索引或插入在中间(然而,索引特征已经自3.5具有添加index和insert,但不存在在Python 2).
似乎提供内置数据LinkedList结构是多余的,不必要的.为什么其他一些编程语言库(如C++和Java库)包含数据LinkedList结构,即使它们易于实现？如果是这样,在这些语言中实施您自己的链表有什么风险？
例如,如果我们在python中有一个数组arr = [1,3,4].我们可以通过使用arr.remove(element)ot 来删除数组中的元素,arr.pop()并且list将变异,并且它的长度将会改变,并且该元素将不会存在.有没有办法做到这一点是C ot C++？如果是,该怎么做？