I am trying to understand my definitions a little better before my exam, where some questions will contain the term "dynamic array." I am therefore afraid of using a singly linked list in these cases, as they offer simply explained and time efficient implementations of stacks, but might not be considered dynamic arrays.

What are the arguments for- and against a singly linked list being a dynamic array?

As far as I understand it, a dynamic array is simply an array that allocates some dynamic number of space dependent on the elements in it. In this case, the linked list's size corresponds 1:1 with the elements in it; therefore dynamic.

On the other hand, the examples my teacher has used and that are in our textbook, dynamic arrays are contiguous arrays - or rather; Arrays are defined as being contiguous sequences. I.e array[i] is the i'th element and array[i 1] is the i 1'th element (if f.ex we ordered the array). But comparable implementations of singly linked lists (two arrays for keys and next) do not follow this ordering scheme; Therefore not an array.

I have therefore derived the following conclusion in my notes; Singly linked lists are dynamic, but not arrays. Therefore not dynamic arrays.

Am I correct in this assumption? What are your arguments for/against?

CodePudding user response：

Array typically implies contiguous memory that can be directly addressed. Getting the value of the i-th element should constant whether i is large or small and whether the size of the array is large or small.

Under this definition, a linked list is dynamic but not an array.

CodePudding user response：

Is A Singly Linked List a Dynamic Array

No, an array (dynamic or not) allows for random access in constant time. With a linked list you have to traverse the list to find the value for a given index.

Arrays are defined as being contiguous sequences

This is often how it is interpreted, but when the memory management is a black box, you could consider that an array is not necessarily contiguous. This could be considered an implementation detail. For example, in JavaScript arrays are not guaranteed to be contiguous. All that matters is that the array offers direct access to an element at a given index, and does so in constant time.

Singly linked lists are dynamic, but not arrays

That is the correct conclusion.