Lecture 6 - Ordered Lists

4. Ordered Lists

An ordered list is a list in which the elements must always be ordered in a particular way. You are familiar with the most common example of ordered lists, namely sorted lists, in which the elements are ordered according to their values. We will look at sorted lists in detail next, but let us now mention some other types of ordered list.

Frequency Ordered Lists

It commonly happens that the elements in a list are accessed over and over again. Typically, to access an element you have to pass through all the elements that precede it in the list. The idea of a frequency ordered list is that the most frequently accessed elements should occur earliest in the list.

Chronologically Ordered Lists

In a chronologically ordered list elements are ordered according to time. For example, you could base the order on the time of last access of each element (note: this is different than frequency-ordering):

Round Robin: Most recently accessed is the last in the list. This is what the textbook discusses under ``circular lists'' (p.137)
Cache (sort of): Least recently accessed is the LAST.

The most common chronologically ordered lists are based upon the time at which each element was added to the list:

Stack: Elements are in reverse chronological order, called LIFO (Last In First Out) or FILO (First In Last Out): the first element added is the last element in the stack, the last element added is the first element in the stack.
Queue: Elements are in normal chronological order called FIFO (First In First Out): the first element added is the first element in the queue the last element added is the last element in the queue.

We will now look at stacks and queues in more detail.