Question

I know Java and also recently started learning Python. At one point I understood that I need to take a pause and clarify all questions related to Data Structures, especially Lists, Arrays and Tuples. Could you please correct me if I am wrong in any of the following:

  • Originally, according to Data Structures standards, Lists do not support any kind of indexation. The only way to get access to the element is through iterations (next method).
  • In Java there is actually a way to get access to elements by index (i.e. get(index) method), but even if you use these index-related methods it is still iterating from the first element (or more specifically its reference)
  • There is a way in Python to access to Lists elements as we work with arrays in Java, using list[index] syntax, but in reality, even though this data type is called "lists", we do have an array of references in the background and when we refer to the third element, for example, we are referring directly to the 3 element in array to get reference without iteration from the first one (I am pretty sure that I am wrong over here)
  • Tuples are implemented in the same way as Lists in Python. The only difference is that they are immutable. But it is still something closer to lists than arrays, because elements are not located contiguously in memory.
  • There are no arrays as in Python
  • In Data Structure theory, when we are creating an array, it uses only a reference to the first cell of memory, and then iterates to the # of element that we specified as index. The main difference between Lists and Arrays is that all elements are located contiguously in memory, that's why we are winning in performance aspect.

I am pretty sure that I am wrong somewhere. Could you correct me please? Thanks

Was it helpful?

Solution

Most of that is wrong.

  • The list abstract data type is an ordered sequence of elements, allowing duplicates. There are many ways to implement this data type, particularly as a linked list, but most programming languages use dynamically resized arrays.
  • Even linked lists may support indexing. There is no way for the implementation to skip directly to the n'th element, but it can just follow links to get there.
  • Java's List type does not specify an implementation, only an interface. The ArrayList type is a List implemented with a dynamic array; the Linkedlist is exactly what the name says.
  • Python's lists are implemented with dynamically resized arrays. Python's tuples are implemented with fixed-size arrays.
  • There are actually two Python types commonly referred to as arrays, not counting the common newbie usage of "array" to refer to Python lists. There are the arrays provided by the array module, and there are NumPy's ndarrays.
  • When you index an array, the implementation does not iterate from the location of the first element to the n'th. It adds an offset to the address of the array to skip to the element directly, without iterating.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top