52.219 LISTS, DLISTS, STACKS, QUEUES
A look at lists, how we can implement them and the operations
that act upon them. Same for doubly linked lists, stacks and queues.
Sequence of elements, two special cases are stacks and queues
Lists are flexible, grow and shrink on demand, elements can be accessed,
inserted, deleted. Lists can be joined together (concatenated),
split into sub-lists.
Applications, almost too many to list (!): simulations, memory
management, programming language translation, ...
Mathematically: a list is a sequence of zero or more elements of a
given type, and is often shown as
a1, a2, ..., an or as
[a1,a2,...,an] or as
LLIST (Linked Lists)
Also known as (aka) "pointer" implementation, or "linked-list"
(most frequently linked list).
1. show diagram of linked list for x -> [a c e]
end of list, and empty list
2. Print list (simple traversal), find an element in the list,
and get me the nth item in a list
3. show how we insert, and how we insert! (where insert! is destructive
or mutative, and insert is constructive (building a new structure))
Notes on insert((2)!)
(a) insert(!) takes a predicate that imposes some "order" on the list
and this allows POLYMORPHISM (a big win)
(b) insert constructs a new list, but retains the contents of the
list, doing this via (make-llist (head l) (insert e (tail l) p))
(c) insert! alters existing list, but must keep "ahead" of the
element that will be changed. That is insert(2)! looks one
cell into the future when forced to traverse/recurse
Notes on delete(!)
(a) delete constructs new list, delete! modifies list
COSTS v BENEFITS of LLIST (linked list)
COSTS: space overhead per element due to pointers, computational
effort in maintaining pointers, garbage when we use a constructive
technique for insert and delete, garbage on delete!
BENEFITS: do not need contiguous storage (don't need to pack/shift
elements), can allow lists to grow/shrink dynamically
VLIST (vector list)
Vector implementation of lists. We have a contiguous block of
storage area, a one dimensional array, a vector.
Notes on insert
There is no such thing as insert (as far as I am concerned for
vlist). So to insert! something we make space for it by shifting
everything right from the position that we wish to occupy
(via function right-shift). Beware of careless right shift!!
Notes on lazy list
How about we mark a deleted element as deleted and do not do a left shift
until we are about to run out of space? Would there be any advantage?
For example, when inserting we do a right shift. Could we again
use deletions to our advantage (ie stopping right shift early?)
COSTS v BENEFITS for VLIST (vector list)
COSTS: hard work doing insertions and deletions (whole load of shifting
going on), have to set a limit on the size of the list, have that
space even if we don't use it.
BENEFITS: compact, no space overheads in additional pointers etc, can
get quickly to the nth element (don't have to traverse list).
ALIST (a cursor implementation using arrays)
Cursor base implementation of lists. We are using a two dimensional
array, so I called it an alist. Think of a row of the array,
the first column corresponds to the contents of the cell, and the
second column corresponds to a pointer to the next element in the
list (or empty).
Within the structure we have a pointer to the first element in the
list, and the first free element in the list. Initially element i
points to element i+1, the last element point to ground (0 in this
case), and free points to the first element. So, its all free
When we delete an element we remove it from the "active" list and
"push" it onto the free list (see free-element). Consequently, when
we insert! a new item/element into the list we must "pop" off a new
element from the free list, upd8 the free list, find the appropriate
insertion position, and upd8 the active list. Behaviour of insert!
is essentially the same as for llist.
COSTS v BENEFITS for ALIST (cursor based implementation)
COSTS: we have to maintain free space, essentially doing garbage
collection as we go, we put a limit on the size of the list,
BENEFITS: dont do all the shifting about that we have in vlist,
and probably have smaller space overhead than the llist
implementation. Generally, very similar to llist.
Doubly linked list, same set of functions
Each element of the dlist points to previous and next memeber in the
list. We can then traverse left or right along the list. One might
expect that insertions and deletions will be easier.
Why have a DLIST? Again, using structure with pointers, and arrays
Stack is one of the most ubiquitous data structures in computing.
Earlier generation machines (such as PDP11) used a stack based architecture.
Function/procedure calls, when allowing local variables, will use a
stack to save off state information. Stacks are used as a mechanism
for evaluating expressions, deferring actions to be performed, and so on.
aka First In Last Out (FILO)
What is a stack, why do we need such a structure? (recursive functions)
(top s), (pop s), (push s), (empty? s). Again, structures versus arrays
Would we want to implement a stack in a similar way to vlist?
Think of a stack "growing down", such that top of stack (t.o.s) is last
element in the vector that is occupied, and element 1 is the bottom of stack
(b.o.s). Again, consider costs v benefits.
We will later look at removing recursion by implementing explicit stacks.
However, recursion is supported by stacks!!
Queue is very often used in simulations. That is we have a queue
of events that must happen in a given order. There will be a model
that takes events off the queue (dequeue) and executes that event.
Similarly there will be a process that generates events and adds them
to the queue (enqueue), maybe using some stochastic process.
An easy example to consider would be simulating a super market,
where events are customers (with certain demands on the check outs)
and a number of checkout desks. We might then wish to run a simulation
to determine what would be "optimal" number of desks, and shift
pattern for check outers (what would you call a person that works ata
a check out desk?). Might also consider design of airport, placement
of machines (or any other resource) in a factory, investment of funds,
and so on.
aka First In First Out (FIFO)
Why have queues? Structure versus array.
Queues implemented as circular arrays. How do we recognise over full, and
empty situations. What is the best implementation for a queue?
(front q), (enqueue e q), (dequeue q), (empty? q)