1.9.1 Lists, Stacks, and Queues

 An array is a simple data structure in which each element can be accessed directly. For example, main memory is constructed as an array. If the data item being tstored is larger than one byte, then multiple bytes can be allocated to the item, and the item is addressed as "item number x item size." But what about storing an item whose size may vary? And what about removing an item if the relative positions of the remaining items must be preserved? In such situations, arrays give way to other data structures.

After arrays. list are perhaps the most fundamental data structures in computer science. Whereas each item in an array can be accessed directly, the items in a list must be accessed in a particular order. That is, a list represents a collection of data values as a sequence. The most common method for implementing thsi structure is a linked list, in which items are linked to one another. Linked lists are of several types:

- In a singly linked list, each item points to its successor, as illustrated in Figure 1.17.

- In a doubly linked list, a given item can refer either to its predecessor or to its successor, as illustrated in Figure 1.18.

- In a circularly linked list, the last element in the list refers to the first delement, rather than to null, as illustrated in Figure 1.19.

Linked lists accommodate items of varying sizes and allow easy insertion and deletion of items. One potential disadvantage of using a list is that performance for retrieving a specified item in a list of size n is linear-O(n), as it requires potentially traversing all n elements in the worst case. Lists are some-times used directly by kernel algorithms. Frequently, though, they areused for constructing more powerful data structures, such as stacks and queues.

A stack is a sequentially ordered data structure that uses the last in, first out(LIFO) principle ofr adding and removing items, meaning that last item placed onto a stack is the first item removed. The operations for inserting and removing items from a stack are known as push and pop, respectively. An operating system often uses a stack when invoking function calls. Parameters, local variables, and the reuturn address are pushed onto the stack when a function is called; returing from the function call pops those items off the stack.

A queue, in contrast, is a sequentially ordered data structure that uses the first in, first out(FIFO) principle; items are removced from a queue in the order in which they wwere inserted. There are many everyday exasmples of queues, including shoppers waitting in a checkout line at a store and casrs waiting in line that are sent to a printer are typically printed in the order in which they were submitted, for example. As we shall see in Chapter 5. tasks that are waiting to be run on an available CPU are often organized in queues.