Transcript Ordered List - WordPress.com

Ordered List: The Abstract View
•
•
The most common linear data structure is the list. By now you are already pretty
familiar with the idea of a list and at least one way of representing a list in the
computer. Now we are going to look at a particular kind of list: an ordered list.
Ordered lists are very similar to the alphabetical list of employee names for the XYZ
company. These lists keep items in a specific order such as alphabetical or numerical
order. Whenever an item is added to the list, it is placed in the correct sorted position
so that the entire list is always sorted.
Before we consider how to implement such a list, we need to consider the abstract
view of an ordered list. Since the idea of an abstract view of a list may be a little
confusing, let's think about a more familiar example. Consider the abstract view of a
television. Regardless of who makes a television, we all expect certain basic things
like the ability to change channels and adjust the volume. As long as these operations
are available and the TV displays the shows we want to view, we really don't care
about who made the TV or how they chose to construct it. The circuitry inside the TV
set may be very different from one brand to the next, but the functionality remains the
same. Similarly, when we consider the abstract view of an ordered list, we don't worry
about the details of implementation. We are only concerned with what the list does,
not how it does it.
created on 29/10/2008
yahaya.wordpress.com
1
Ordered List: The Abstract View
• Suppose we want a list that can hold the following group of sorted
numbers: [2 4 6 7]. What are some things that we might want to do
with our list? Well, since our list is in order, we will need some way
of adding numbers to the list in the proper place, and we will need
some way of deleting numbers we don't want from the list. To
represent these operations, we will use the following notation:
• AddListItem(List, Item)
RemoveListItem(List, Item)
• Each operation has a name and a list of parameters the operation
needs. The parameter list for the AddListItem operation includes a
list (the list we want to add to) and an item (the item we want to
add). The RemoveListItem operation is very similar except this time
we specify the item we want to remove. These operations are part of
the abstract view of an ordered list. They are what we expect from
any ordered list regardless of how it is implemented in the computer.
created on 29/10/2008
yahaya.wordpress.com
2
Ordered List: The Implementation
• In this lesson, we are going to look at two different ways of creating
an ordered list data structure to hold the following list [2 4 6 7]. First,
we will create a list using an array of memory cells. Next, we will
create the the same list using pointers. Finally, we will compare
these two approaches to see the advantages and disadvantages.
• Array Implementation
• One approach to creating a list is simply to reserve a block of
adjacent memory cells large enough to hold the entire list. Such a
block of memory is called an array. Of course, since we will want to
add items to our list, we need to reserve more than just four memory
cells. For now, we will make our array large enough to hold six
numbers. The animation below shows a graphical representation of
our array in memory with the list numbers. Follow the directions in
the animation to learn how the list operations AddListItem and
RemoveListItem work.
created on 29/10/2008
yahaya.wordpress.com
3
Ordered List: The Implementation
• In the animation, you saw that there were two disadvantages to
using an array to implement an ordered list. First, you saw that the
elements in the list must be kept in sequence, that is, there must not
be gaps in the list. If gaps are allowed, the computer will not be able
to determine which items are part of the list and which items are not.
For this reason, the ordered list structures that are implemented with
arrays are known as sequential lists.
• The second disadvantage that you saw was that arrays have a fixed
size and therefore limit the number of items the list can contain. Of
course we could try to increase the size of the array, but it may not
always be the case that the adjacent memory cells in the computer
are available. They could be in use by some other program.
However, it is quite likely that the computer does have available
memory at some other non-adjacent location. To take advantage of
this memory, we need to design our list so that the list items do not
have to be adjacent.
created on 29/10/2008
yahaya.wordpress.com
4
Ordered List: The Implementation
• Pointer Implementation
• A second approach to creating a list is to link
groups of memory cells together using pointers.
Each group of memory cells is called a node.
With this implementation every node contains a
data item and a pointer to the next item in the
list. You can picture this structure as a chain of
nodes linked together by pointers. As long as we
know where the chain begins, we can follow the
links to reach any item in the list. Often this
structure is called a linked list.
created on 29/10/2008
yahaya.wordpress.com
5
Ordered List: The Implementation
• Notice that the last memory cell in our chain contains a symbol
called "Null". This symbol is a special value that tells us we have
reached the end of our list. You can think of this symbol as a pointer
that points to nothing. Since we are using pointers to implement our
list, the list operations AddListItem and RemoveListItem will work
differently than they did for sequential lists. The animation below
shows how these operations work and how they provide a solution
for the two problems we had with arrays.
•
created on 29/10/2008
yahaya.wordpress.com
6
Ordered List: The Implementation
• By implementing our list with pointers, we are able to
avoid the two disadvantages we discovered with using
sequential lists. However, this does not mean that linked
lists are the perfect solution. Whenever we use
indirection in building a data structure, it becomes much
harder to find mistakes. For example, it is very easy to
assign the wrong address to a pointer and "short circuit"
our list. In general, sequential lists are simpler than
linked lists but they are also more limited. Linked lists
give us a great amount of flexibility but this comes at the
cost of increased complexity
created on 29/10/2008
yahaya.wordpress.com
7