• Collections can be further orgamized based on additional properties:
  • Are the elements ordered?
  • Are duplicates allowed?
  • Are there constraints on additon and removal of elements in any way?
• Following the idea of **Indirection,** there are the following interface which extend Collection that captures the above properties:
  • Interface List for ordered collections.
  • Interface Set for colections without duplicates.
  • Interface Queue for ordered collections with constraints on addition and deletion.

List Interface

• An ordered collection can be accessed in two ways:

  1. Through an iterator (using hasNext() and next())
  2. By position → Random Access ( similar to a[i] in Python)

  ---

• For Random Access, additional functions are present.

  public interface List<E> extends Collection<E>{
  	void add(int index, E element);
  	void remove(int index):
  	
  	E get(int index); //retuns an element at index.
  	E set(int index, E element); //Sets an element E at index.
  	//Look at add() function. This seems similar....
  	//Difference? -> set give an object of type E as return value. What is this value?
  
  	ListIterator<E> listIterator(); //Special Type of Iterator for lists.
  

• ListIterator extends Iterator. Special functions are:

  • void add(E element): To insert an element before the current index.
  • void previous(): To go to the previous element.
  • boolean hasPrevious(): Checks that it is legal to go backwards.

  ---

List Interface and Random Access

• For some ordered collections under List , random access may not be that efficient.
  • Example: In an array, we can easily compute the element at index i
  • But in a Linked List, to get to element at index i, we have to from beginning and traverse i links.
• But the List interface has a random access function get to enable random access.
• So even though such a function exists, for a linked list, it is not random access, and also more computationall expensive.
• But the user of this method may not know about this.
• How to solve this issue?

<aside> 💡 Solution: Set a tagging interface called Random Access.

</aside>

• Used to just tell us whether a List supports random access or not.
• Can choose algorithmic strategy based on this.

if(c instanceof RandomAccess){
	//use random access algorithm
}
else{
	//use sequential access algorithm
}

• Now, only the implementations that have this RandomAccess Tagging interface implemented, will use in the above, the random access algorithm.

• If a List is not implemeting this tagging interface, then it will use the sequential access algorithm. → So can reduce the computations.

  ---

The AbstractList interface