List (abstract Data Type) - Characteristics

Characteristics

Lists have the following properties:

• The size of lists. It indicates how many elements there are in the list.
• Equality of lists:
  • In mathematics, sometimes equality of lists is defined simply in terms of object identity: two lists are equal if and only if they are the same object.
  • In modern programming languages, equality of lists is normally defined in terms of structural equality of the corresponding entries, except that if the lists are typed, then the list types may also be relevant.
• Lists may be typed. This implies that the entries in a list must have types that are compatible with the list's type. It is common that lists are typed when they are implemented using arrays.
• Each element in the list has an index. The first element commonly has index 0 or 1 (or some other predefined integer). Subsequent elements have indices that are 1 higher than the previous element. The last element has index + − 1.
  • It is possible to retrieve the element at a particular index.
  • It is possible to traverse the list in the order of increasing index.
  • It is possible to change the element at a particular index to a different value, without affecting any other elements.
  • It is possible to insert an element at a particular index. The indices of higher elements at that are increased by 1.
  • It is possible to remove an element at a particular index. The indices of higher elements at that are decreased by 1.