This article summarizes some of the main important points you need to know about lists
- An abstract datatype represents and ordered sequences of value.
- Same value can occur more than once
- Each value is considered a distinct list value even if it is a duplicate value
Operation Performed on :
- isEmpty() : testing whether or not a list is empty
- isFull(): tests if the list is full, if it is limited (bounded) list
- add(x) : appends an entity to a list in the provided, by i , index position
- remove(i) : removes an entity from list positioned on i position
Implementations in Java:
It is a bit of overhead to list and describe all practical implementations of lists, for this a whole book or course will be need.
However I try to describe as much as I can in data structures section.
The two main approaches that lists are implemented in Java are:
- The length of an array is established when the array is created
- After creation, its length is fixed. (not entirely true)
- Getting an element positioned on index i is O(1) constant time
- Harder to resize, take O(n) liner time.
- Unknown size at creation time (can be fixed if need)
- Length is dynamically resided
- Getting element positioned on index i is liner O(n)
- Resize takes constant time O(1)
- Inserting element in front, end, or middle takes constant time O(1)