Lists Exercises

1. Terminology
   1. With all of the members of your table, define the following terms (as they relate to lists):
      1. ADT (Abstract Data Type)
      2. head
      3. tail
      4. length
      5. ordered
2. Linked Lists Basics
   1. Draw a single link of a linked list (according to the version from the textbook)
   2. Draw an empty linked list (with a header and trailer (i.e., the version from the textbook))
   3. Draw a linked list (with a header and trailer) with a single link with "C" in it
3. Linked list demo: Stores the year that Columbus State University was founded (Columbus College at the time) (with adapted code from the textbook).
4. ADT Lists
   Background:
   

   Sequences of elements a₀ through a_n−1 can be represented by:

   ⟨ a0, a1, ..., an−1 ⟩

   Additionally, for lists, use | to indicate the current position of the list.
   Individually complete the following, then turn to a neighbor to confirm your answers. Write down each call to the List interface necessary to complete the following operations. Draw the list representation after each operation.
   1. Insert every character of your first name into a basic list and write down a representation of the list using sequence notation.
      For example:

      New list: ⟨ | ⟩
      Insert H: ⟨ | H ⟩
      Append y: ⟨ | H, y ⟩
      Append r: ⟨ | H, y, r ⟩
      Append u: ⟨ | H, y, r, u ⟩
      Append m: ⟨ | H, y, r, u, m ⟩

   2. Insert a space and then every character of your last name into the existing list and write down a representation of the list using sequence notation.
      Example final state:

      ⟨ | H, y, r, u, m,  , C, a, r, r, o, l, l ⟩

   3. Insert a space, your middle initial, and a "." in between your first and last names in the existing list and write down a representation of the list using sequence notation.
      Example final state:

      ⟨ H, y, r, u, m,   | D, .,  , C, a, r, r, o, l, l ⟩

   4. Remove all but the first letter of your first name, middle name and last name and write down a representation of the list using sequence notation.
      Example final state:

      ⟨ H, D, C | ⟩

5. Doubly-linked Lists Basics
   1. What does a link in an doubly-linked list look like?
   2. What does an empty doubly-linked list (with a header and trailer (i.e., the version from the textbook)) look like?
   3. What does an empty basic doubly-linked list (no header nor trailer) look like?
   4. What does a doubly-linked list (with a header and trailer) with a single link with "C" in it look like?
   5. What does a doubly-linked list (no header nor trailer) with a single link with "C" in it look like?
   6. What are the scenarios for inserting into a doubly-linked list (with a header and trailer)?
   7. What are the scenarios for inserting into a doubly-linked list (no header nor trailer)?

Last Modified: