Array List - Theory & ANSI C Implementation.

List can be implemented as a resizable array.

it's data structure L with operations:
- insert(L, index, value) - inserts 'value' element on list L, after element at position 'index',
- get(L, index) - returns 'value' element on list L, at position 'index',
- delete(L, index) - deletes element on list L, after element at position 'index',
- size(L) - returns number of elements on list L.

after 'insert' or 'delete' operation, list is reorganized & perhaps resized (to twice of it's previous size, by default).

we can see that 'insert' & 'delete' operations are expensive, but 'get' cheap - opposite to Pointer Lists (LinkedLists in Java), which have fairly cheap insertion, but it's expensive to get element from selected position.

(to be continued as soon as possible).

Source: my partial education, my programming experience.

1 comment:

  1. array list has use for example in hash map implementation.