Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Chapter 3
Lists, Recursion, Stacks, Queues
We have seen how arrays are a convenient way to store collections of items, and
how loops and iteration allow us to sequentially process those items
...
In this
section, we shall see that lists may be a better way to store collections of items, and
how recursion may be used to process them
...

3
...
When considering lists, we can speak aboutthem on different levels - on a very abstract level (on which we can define what we
mean by a list), on a level on which we can depict lists and communicate as humans
about them, on a level on which computers can communicate, or on a machine level
in which they can be implemented
...
We can depict a pointer to the empty list by a
diagonal bar or cross through the cell
...


Using those, our last example list can be constructed as
MakeList(3, MakeList(1, MakeList(4, MakeList(2, MakeList(5, EmptyList)))))
...

This inductive approach to data structure creation is very powerful, and we shall use
it many times throughout these notes
...

It is obviously also important to be able to get back the elements of a list, and we no
longer have an item index to use like we have with an array
...
So, conversely, from a non-empty list it must always be possible to get the first
element and the rest
...

The selectors will only work for non-empty lists (and give an error or exception on
the empty list), so we need a condition which tells us whether a given list is empty:
• isEmpty(list)
This will need to be used to check every list before passing it to a selector
...
e
...
This would be done by so-called mutators which
change either the first element or the rest of a non-empty list:
• replaceFirst(x, l)
• replaceRest(r, l)

For instance, with l = [3, 1, 4, 2, 5], applying replaceFirst(9, l) changes l to [9, 1, 4, 2,
5]
...

We shall see that the concepts of constructors, selectors and conditions are
common to virtually all abstract data types
...

XML Representation
In order to communicate data structures between different computers and possibly
different programming languages, XML (eXtensible Markup Language) has
become a quasi-standard
...
For
instance, a cell-oriented representation of the above list would be:

While this looks complicated for a simple list, it is not, it is just a bit lengthy
...

Implementation of Lists
There are many different implementations possible for lists, and which one is best
will depend on the primitives offered by the programming language being used
...
In some other languages, it is more natural
to implement 14 lists as arrays
...
For many applications,
this is not a problem because a maximal number of list members can be
determined a priori (e
...
, the maximum number of students taking one particular
module is limited by the total number of students in the University)
...
We will not go into the details of all the
possible implementations of lists here, but such information is readily available in
the standard textbooks
...
2 Recursion
We previously saw how iteration based on for-loops was a natural way to process
collections of items stored in arrays
...

The idea is to formulate procedures which involve at least one step that invokes (or
calls) the procedure itself
...

To find the last element of a list l we can simply keep removing the first remaining
item till there are no more left
...
We say that
the procedure has linear time complexity, that is, if the length of the list is increased
by some factor, the execution time is increased by the same factor
...
It does not mean, however, that lists are inferior to arrays in general, it
just means that lists are not the ideal data structure when a program has to access
the last element of a long list very often
...
Again,
this needs to be done one item at a time, and that can be accomplished by
repeatedly taking the first remaining item of l1 and adding it to the front of the
remainder appended to l2:

The time complexity of this procedure is proportional to the length of the first list,
l1, since we have to call append as often as there are elements in l1
...
3 Stacks
Stacks are, on an abstract level, equivalent to linked lists
...

Graphical Representation
Their relation to linked lists means that their graphical representation can be the
same, but one has to be careful about the order of the items
...
The two constructors are:
• EmptyStack, the empty stack, and
• push(element, stack),

which takes an element and pushes it on top of an existing stack, and the two
selectors are:
• top(stack), which gives back the top most element of a stack, and
• pop(stack), which gives back the stack without the top most element
...

Implementation of Stacks
There are two different ways we can think about implementing stacks
...
That is, push does not change the original stack,
but creates a new stack out of the original stack and a new element
...
This
functional view is quite convenient
...
However, from a practical point of view, we may not
want to create lots of new stacks in a program, because of the obvious memory
management implications
...
This is
conceptually more difficult, since now applying top to a given stack may give
different answers, depending on how the state of the system has changed
...


3
...

Conceptually, we add to the end of a queue and take away elements from its front
...

For instance, if we insert the elements [3, 1, 4, 2] into an initially empty queue, we
get:

This arrangement means that taking the first element of the queue, or adding an
element to the back of the queue, can both be done efficiently
...
e
...

Abstract Data Type “Queue”
On an abstract level, a queue can be constructed by the two constructors:
• EmptyQueue, the empty queue, and
• push(element, queue), which takes an element and a queue and returns a
queue in which the element is added to the original queue at the end
...

And, as with stacks, the selectors only work for non-empty queues, so we again
need a condition which returns whether a queue is empty:
• isEmpty(queue)
In later chapters we shall see practical examples of how queues and stacks operate
with different effect
...
5 Doubly Linked Lists
A doubly linked list might be useful when working with something like a list of web
pages, which has each page containing a picture, a link to the previous page, and a
link to the next page
...
g
...
However, the doubly linked list also has an
easy way to get the previous element, as well as to the next element
...
Again, we depict the empty list by a diagonal bar or cross
through the appropriate cell
...

• MakeListRight(element, list), which takes an element and a doubly linked
list and returns a new doubly linked list with the element added to the right of the
original doubly linked list
...
For example, the doubly linked list represented above can be constructed
by either of:
MakeListLeft(3, MakeListLeft(1, MakeListLeft(4, MakeListLeft(2, MakeListLeft(5,
EmptyList)))))
MakeListLeft(3, MakeListLeft(1, MakeListRight(5, MakeListRight(2, MakeListLeft(4,
EmptyList)))))

In the case of doubly linked lists, we have four selectors:
• firstLeft(list),
• restLeft(list),
• firstRight(list), and
• restRight(list)
...
This is useful when we might need to move efficiently through a
whole list of items, but might not be starting from one of two particular end points
...
6 Advantage of Abstract Data Types
It is clear that the implementation of the abstract linked-list data type has the
disadvantage that certain useful procedures may not be directly accessible
...
One could modify
the linked-list data type by maintaining a pointer to the last item, as we did for the
queue data type, but we still wouldn’t have an easy way to access intermediate
items
...
That
disadvantage leads to an obvious question: Why should we want to use abstract
data types when they often lead to less efficient algorithms? Aho, Hopcroft and
Ullman (1983) provide a clear answer in their book:

“At first, it may seem tedious writing procedures to govern all accesses to the
underlying structures
...
This
flexibility can be particularly important in large software efforts, and the reader
should not judge the concept by the necessarily tiny examples found in this book
...




---