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.

LIST

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
               (a1, a2,...,an)

LLIST (Linked Lists)

Also known as (aka) "pointer" implementation, or "linked-list" (most frequently linked list). source: /home/s7/pat/scheme/pub/llist.scm 

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. source: /home/s7/pat/scheme/pub/vlist.scm

    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 initially.

    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. source: /home/s7/pat/scheme/pub/alist.scm

    DLIST

    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

    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.

    source: /home/s7/pat/scheme/pub/stack.scm

    We will later look at removing recursion by implementing explicit stacks. However, recursion is supported by stacks!!

    QUEUE

    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)

    source: /home/s7/pat/scheme/pub/lqueue.scm