Time complexity for an array based List

[DrJones]

So i was reading up on ADT, and Array based Lists..
The book introduces the list ADT, and it's different functions as such.

We will deal with a general list of the form A0, A1, A2, ..., AN−1. We say that the size of this list is N. We will call the special list of size 0 an empty list.
For any list except the empty list, we say that Ai follows (or succeeds) Ai−1 (i < N) and that Ai−1 precedes Ai (i > 0). The first element of the list is A0, and the last element is AN−1. We will not define the predecessor of A0 or the successor of AN−1. The position of element Ai in a list is i. Throughout this discussion, we will assume, to simplify matters, that the elements in the list are integers, but in general, arbitrarily complex elements are allowed (and easily handled by a class template).
Associated with these “definitions” is a set of operations that we would like to perform on the List ADT. Some popular operations are printList and makeEmpty, which do the obvious things; find, which returns the position of the first occurrence of an item; insert and remove, which generally insert and remove some element from some position in the list; and findKth, which returns the element in some position (specified as an argument). If the list is 34, 12, 52, 16, 12, then find(52) might return 2; insert(x,2) might make the list into 34, 12, x, 52, 16, 12 (if we insert into the position given); and remove(52) might turn that list into 34, 12, x, 16, 12.
Of course, the interpretation of what is appropriate for a function is entirely up to the programmer, as is the handling of special cases (for example, what does find(1) return above?). We could also add operations such as next and previous, which would take a position as argument and return the position of the successor and predecessor, respectively.

In another section they come up some kind of "guide" on how it could be implemented using a array/vector based structure in which they write that the worst case situation for insertion and deletion would be that

In the worst case, inserting into position 0 (in other words, at the front of the list) requires pushing the entire array down one spot to make room, and deleting the first element requires shifting all the elements in the list up one spot, so the worst case for these operations is O(N).

This doesn't make sense for since they already have a pointer to the position, should the insertion and deletion be constant time.. I don't see any reason why i should move all my data in the array down..

[TheIdeasMan]

Hi,

This doesn't make sense for since they already have a pointer to the position, should the insertion and deletion be constant time.. I don't see any reason why i should move all my data in the array down..

The implementation is an array or vector, not a linked list, so inserting/deleting requires moving all the remaining array values along 1 spot.

In a linked list, it is easier (as you alluded) because the items have pointers to the next item. Insertion involves altering the pointers. For example to insert after the 10th element, make the 10th point to the new element and the new element points to what was the 11th element before.

Hope all is well at your end, and you all are enjoying the festive season :+D

Edit: I guess using an array as a List Data Structure is a bit of a misnomer - it invites confusion at the outset IMO. Also, the whole point of Data Structures is to solve the problems that exist with built ins like arrays. So I would have expected a progression from arrays to Linked List to Binary Sort Tree, Stacks & Queues etc.