List

Question 1

What is an ADT List?

Answer 1

• a list can be seen as a sequence of elements of the same type,
  < l1, l2, …, ln >
• there is an order of the elements
• each element has a position inside the list
• the order of the elements is important (positions are important)
• the number of elements from a list is called the length of the list
• a list without elements is called empty
• a list is a container that is:
  - either empty
  - it has a unique first element
  - it has a unique last element
  - for every element (except for the last)
  there is a unique successor element
  - for every element (except for the first)
  there is a unique predecessor element

Question 2

What are the positions in an ADT List?

Answer 2

Every element from a list has a unique position in the list:
- positions are relative to the list (but important for the list)
- the position of an element:
- dentifies the element from the list
- determines the position of the successor and predecessor element
(if they exist)

Position of an element can be seen in different ways:
- as the rank of the element in the list (first, second, third, etc.)
similarly to an array, the position of an element is actually its index
- as a reference to the memory location where the element is stored
for example a pointer to the memory location

We consider the position of an element in an abstract manner of type TPosition

A position p will be considered valid if it denotes the position of an actual element from the list:
- if p is a pointer to a memory location, p is valid if it is the address of an
element from a list (not NIL or some other address that is not the address
of any element)
- if p is the rank of the element from the list, p is valid if it is between 1 and
the number of elements

For an invalid position we will use the following notation: ⊥

Question 3

What is the domain of an ADT List?

Answer 3

Domain of the ADT List:

L = { l | l is a list with elements of type TElem, each having a unique position in l of type TPosition}

Question 4

What are the operations for an ADT List?

Answer 4

init(l)
first(l)
last(l)
valid(l, p)
next(l, p)
previous(l, p)
getElement(l, p)
position(l, e)
setElement(l, p, e)
addToBeginning(l, e)
addToEnd(l, e)
addToPosition(l, p, e)
remove(l, p)
remove(l, e)
search(l, e)
isEmpty(l)
size(l)
destroy(l)
iterator(l, it)

Question 5

What is an ADT IndexedList?

Answer 5

If we consider that TPosition is an Integer value (similar to Python and Java*), we can have an IndexedList

In case of an IndexedList the operations that work with a position take as parameter integer numbers representing these positions.

• less operations in the interface of the IndexedList
  (operations first, last, next, previous, valid do not exist)

*In Python and Java, TPosition is represented by an index.
We can add and remove using index and we can access
elements using their index (but we have iterator as well for the List).

Question 6

What is an ADT IteratedList?

Question 7

What is an ADT SortedList?