Big O Notation Arrays vs. Linked List insertions

Question

Big O Notation Arrays vs. Linked List insertions:

According to academic literature for arrays it is constant O(1) and for Linked Lists it is linear O(n).

An array only takes one multiplication and addition.

A linked list which is not laid out in contiguous memory requires traversal.

This question is, does O(1) and O(n) accurately describe indexing/search costs for arrays and linked lists respectively?

Answer 1

Insertion for arrays I'd imagine is slower. Sure, you have to iterate a linked list, but you have to allocate, save and deallocate memory to insert into an array.

Answer 2

Assuming you are talking about an insertion where you already know the insertion point, i.e. this does not take into account the traversal of the list to find the correct position:

Insertions in an array depend on where you are inserting, as you will need to shift the existing values. Worst case (inserting at array[0]) is O(x).

Insertion in a list is O(1) because you only need to modify next/previous pointers of adjacent items.

Answer 3

tldr An unsorted array is analogous to a set. Like a set, elements can be added and removed, iterated over, and read. But, as with a set, it makes no sense to talk about inserting an element at a specific position, because to do so would be an attempt to impose a sorting order on what is, by definition, unsorted.

---

According to academic literature for arrays it is constant O(1) and for Linked Lists it is linear O(n).

It is worth understanding why the academic literature quotes array insert as O(1) for an array. There are several concepts to understand:

• An array is defined as being unsorted (unless explicitly stated otherwise).

• The length of an array, defined as the number of elements that the array contains, can be increased or decreased arbitrarily in O(1) time and there is no limit on the maximum size of an array.

  (In a real computer this is not be the case, due to various factors such as memory size, virtual memory, swap space, etc. But for the purpose of algorithm asymptotic analysis these factors are not important - we care about how the running time of the algorithm changes as the input size increases towards infinity, not how it performs on a particular computer with a particular memory size and operating system.)

• Insert and delete are O(1) because the array is an unsorted data structure.

• Insert is not assignment

Consider what it actually means to add an element to an unsorted data structure. Since there is no defined sorting order, whatever order actually occurs is arbitrary and does not matter. If you think in terms of an object oriented API, the method signature would be something like:

Array.insert(Element e)

Note that this is the same as the insert methods for other data structures, like a linked list or sorted array:

LinkedList.insert(Element e)
SortedArray.insert(Element e)

In all of these cases, the caller of the insert method does not specify where the value being inserted ends up being stored - it is an internal detail of the data structure. Furthermore, it makes no sense for the caller to try and insert an element at a specific location in the data structure - either for a sorted or unsorted data structure. For an (unsorted) linked list, the list is by definition unsorted and therefore the sort order is irrelevant. For a sorted array, the insert operation will, by definition, insert an element at a specific point of the array.

Thus it makes no sense to define an array insert operation as:

Array.insert(Element e, Index p)

With such a definition, the caller would override an internal property of the data structure and impose an ordering constraint on an unsorted array - a constraint that does not exist in the definition of the array, because an array is unsorted.

Why does this misconception occur with arrays and not other data structures? Probably because programmers are used to dealing with arrays using the assignment operator:

array[0] = 10
array[1] = 20

The assignment operator gives the values of an array an explicit order. The important thing to note here is that assignment is not the same as insert:

• insert : store the given value in the data structure without modifying existing elements.
• insert in unsorted : store the given value in the data structure without modifying existing elements and the retrieval order is not important.
• insert in sorted : store the given value in the data structure without modifying existing elements and the retrieval order is important.
• assign a[x] = v : overwrite the existing data in location x with the given value v.

An unsorted array has no sort order, and hence insert does not need to allow overriding of the position. insert is not the same thing as assignment. Array insert is simply defined as:

Array.insert(v):    
    array.length = array.length + 1
    // in standard algorithmic notation, arrays are defined from 1..n not 0..n-1
    array[array.length] = v

Which is O(1).

Answer 4

Long ago on a system that had more RAM that disk space I implemented an indexed linked list that that was indexed as it was entered by hand or as it was loaded from disk. Each and every record was append to the next index in memory and the disk file opened the record appended to the end closed.

The program cashiered auction sales on a Model I Radio Shack computer and the the writes to disk were only insurance against power failure and for and archived record as in order to meet time constraints the data had to be fetched form RAM and printed in reverse order so the buyer could be ask if the first item that came up was the last one he purchased. Each buyer and Seller were linked to the last item of theirs that sold and that item was linked to the item before it. It was only a single link link list that was traversed from the bottom up.

Corrections were made with reversing entries. I used the same method for several things and I never found a faster system if the method would work for the job at hand and the index was saved to disk and didn't have to be rebuilt as the file reloaded to memory as it might in a power failure.

Later I wrote a program to edit more conventionally. It could also reorganize the data so it was grouped together.

Answer 5

What literature are you referencing? The size of an array is determined when the array is created, and never changes afterwards. Inserting really only can take place on free slots at the end of the array. Any other type of insertion may require resizing and this is certainly not O(1). The size of a linked list is implementation dependent, but must always be at least big enough to store all of its elements. Elements can be inserted anywhere in the list, and finding the appropriate index requires traversing.

Answer 6

O(1) accurately describes inserting at the end of the array. However, if you're inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n) for arrays. End appending also discounts the case where you'd have to resize an array if it's full.

For linked list, you have to traverse the list to do middle insertions, so that's O(n). You don't have to shift elements down though.

There's a nice chart on wikipedia with this: http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays

                          Linked list   Array   Dynamic array   Balanced tree

Indexing                          Θ(n)   Θ(1)       Θ(1)             Θ(log n)
Insert/delete at beginning        Θ(1)   N/A        Θ(n)             Θ(log n)
Insert/delete at end              Θ(1)   N/A        Θ(1) amortized   Θ(log n)
Insert/delete in middle     search time 
                                + Θ(1)   N/A        Θ(n)             Θ(log n)
Wasted space (average)            Θ(n)    0         Θ(n)[2]          Θ(n)