More Linked Lists
- Generalized Lists
(HSM Ch.4.10)
- A generalized list object is an ordered sequence of zero or
more elements of some type, including generalized lists.
- Allows sublists
- And why not? Basis of Prolog and LISP programming structures.
- Examples (HSM Ch.4.10.1)
- A list has a head and a tail
- The empty list has no elements
- The
head and tail functions
- Lists may occur more than once, possibly recursively
- Representation
(HSM Ch.4.10.1)
- Example application: Polynomials in several variables
- Factor out each variable with each exponent
- Top list is the first variable, with a head node giving the
variable name, then nodes for each exponent
- Sublists for each node, of the same nature for subsequent
variables
- Recursive algorithms
(HSM Ch.4.10.2)
- Copying a list
(HSM Ch.4.10.2.1)
- Recursive algorithm
- Time complexity = O(NumberOfNodes)
Space complexity = O(Longest branch)
- List equality
(HSM Ch.4.10.2.2)
- List depth
(HSM Ch.4.10.2.3)
- Shared and recursive lists
- Sharing saves space
- Sharing requires naming of lists, implemented as head nodes
with reference counts (useful for deleteing)
- Deleting shared lists, and recursive lists
- Heterogeneous Lists
(HSM Ch.4.12)
- Representation using a union
- Nodes take the largest space possibly needed
- Representation using inheritance
- Use an abstract base class for nodes, and a derived class
for the various types of data
- Use a union to return data, so an iterator can be defined
- Rather inelegant - maybe it can be improved?
Exercises
- Generalized lists: HSM Ch.4.10, exercises 1,2, 7.
- Heterogeneous lists: HSM Ch.4.12, exercise 6.
Lab Tasks
Exam Style Questions
- Define the generalized list ADT.
- Draw a picture showing the linked list representation of the generalized
list [some generalized list, e.g., (a,(b,(c,d),e),f,g)]
- Give an algorithm to copy a generalized list. What is it's asymptotic
complexity in big-O notation?
- Give an algorithm to determine if two generalized lists are equal.
What is it's asymptotic complexity in big-O notation?
- Give an algorithm to find the depth of a generalized list.
What is it's asymptotic complexity in big-O notation?
- Draw a picture showing the linked list representation of the following
shared generalized lists. Include the head nodes required to keep count
of the number of uses of each list.
[some shared lists]
- What C++ programming feature is needed when representing heterogeneous
linked lists?