A sequential access collection is a list that stores its elements in sequential order. We call this type of collection a linear list. Linear lists are not limited by size when they are created, meaning they are able to expand and contract dynamically. Items in a linear list are not accessed directly; they are referenced by their position, as shown in Figure 1.2. The first element of a linear list is at the front of the list and the last element is at the rear of the list.
Because there is no direct access to the elements of a linear list, to access an element you have to traverse through the list until you arrive at the position of the element you are looking for. Linear list implementations usually allow two methods for traversing a list—in one direction from front to rear, and from both front to rear and rear to front.
A simple example of a linear list is a grocery list. The list is created by writing down one item after another until the list is complete. The items are removed from the list while shopping as each item is found. Linear lists can be either ordered or unordered. An ordered list has values
in order in respect to each other, as in:
Beata Bernica David Frank Jennifer Mike Raymond Terrill
An unordered list consists of elements in any order.
The order of a list makes a big difference when performing searches on the data on the list, as you’ll see in a next post when we explore the binary search algorithm versus a simple linear search.
Some types of linear lists restrict access to their data elements. Examples of these types of lists are stacks and queues.
A stack is a list where access is restricted to the beginning (or top) of the list. Items are placed on the list at the top and can only be removed from the top. For this reason, stacks are known as Last-in, First-out structures. When we add an item to a stack, we call the operation a push.
When we remove an item from a stack, we call that operation a pop. These two stack operations are shown in Figure 1.3. The stack is a very common data structure, especially in computer systems programming.
Stacks are used for arithmetic expression evaluation and for balancing symbols, among its many applications.
A queue is a list where items are added at the rear of the list and removed from the front of the list.
This type of list is known as a First-in, First-out structure. Adding an item to a queue is called an EnQueue, and removing an item from a queue is called a Dequeue. Queue operations are shown in Figure 1.4.
Queues are used in both systems programming, for scheduling operating system tasks, and for simulation studies.
Queues make excellent structures for simulating waiting lines in every conceivable retail situation.
A special type of queue, called a priority queue, allows the item in a queue with the highest priority to be removed from the queue first. Priority queues can be used to study the operations of a hospital emergency room, where patients with heart trouble need to be attended to before a patient with a broken arm, for example.
The last category of linear collections we’ll examine are called generalized indexed collections. The first of these, called a hash table, stores a set of data
values associated with a key. In a hash table, a special function, called a hash function, takes one data value and transforms the value (called the key) into an integer index that is used to retrieve the data.
The index is then used to access the data record associated with the key. For example, an employee record may consist of a person’s name, his or her salary, the number of years the employee has been with the company, and the department he or she works in.
This structure is shown in Figure 1.5. The key to this data record is the employee’s name. C# has a class, called HashTable, for storing data in a hash table.
Another generalized indexed collection is the dictionary. A dictionary is made up of a series of key–value pairs, called associations. This structure is analogous to a word dictionary, where a word is the key and the word’s definition is the value associated with the key. The key is an index into the value associated with the key.
Dictionaries are often called associative arrays because of this indexing scheme, though the index does not have to be an integer.
Tweet
No comments:
Post a Comment