Linked Lists

The Ordered List ADT (HSM Ch.2.3)
- An ordered list object is an ordered sequence of zero or more elements of some type. If the all the elements are of the same type, it is a homogeneous ordered list, otherwise it is a heterogeneous ordered list.
- Operations include
  - Checking if the list is empty
  - Finding the length of the list
  - Storing a new element at one end or a specified position in the list
  - Retrieving an element from one end or a specified position in the list
  - Retrieving elements of the list from one end to the other (iteration)
  - Removing an element at one end or a specified position in the list
  - Comparing elements
  - Output the elements in order
- Examples (HSM Ch.2.3)
- The array ADT can be used to implement a homogeneous ordered list ADT.
  - Complications in the implementation due to the static nature of arrays.
  - Useful in some special cases, e.g., polynomials.
Singly Linked Lists
- Motivation (vs Arrays) (HSM Ch.4.1)
  - Adding new data
  - Deleting data
  - Storage efficiency
- Simple representation (HSM Ch.4.2.1-2)
  - Private data and link - cannot access data from pointer to node
  - Public data, or public access functions - violates encapsulation principle
    - Any function can access, not only linked list manipulation functions
    - Only linked list manipulation functions must manipulate the data
  - Data class inside linked list class - cannot add more data to linked list class without adding more to every node.
  - Nested classes - does not provide reusability of data class
  - Separate list class and data class, with linked list manipulation functions as friends
- Reusable representation (HSM Ch.4.3.1)
Circular Linked Lists (HSM Ch.4.4)
- Representation
- A dummy head node
Doubly Linked Lists (HSM Ch.4.9)
- Motivation
  - Can only move one way
  - Hard to delete a known node
  - Hard to insert before a known node
- Representation
- Ease of previously difficult operations
- A dummy head node (HSM Fig.4.29-30)
Iterators
- Motivation (HSM Ch.4.3.2)
- Using member functions of the list class
  - Some functions do not make sense for some instantiations of the template
  - List class could become bulky
  - Class implementor has to predict all possible needs
  - Class user has to understand implementation to add new ones, which violates data abstraction
- Iterators provide sequential access to data in nodes
- Internal iterators
  - Add another node pointer (the iterator) in the list class
  - Add member functions to
    - Set the iterator to the start or end
    - Check if the iterator is at a node
    - Check if there is a node after or before the iterator position
    - Move the iterator forwards or backwards
    - Get or set the data of the current node
    - Add a node before or after the current node
    - Delete the node before or after the current node
  - Only one (or a fixed number) of iterators available per list
- External iterators (HSM Ch.4.3.2)
  - An iterator class is made a friend of the node and list classes
  - An iterator object contains a pointer to a list object and a pointer to a node in that list.
  - Member functions manipulate the node pointer.
YALLI
- A doubly linked list template class with external iterator
- linkedlistclass.h
- linkedlistclass.cpp
- TestLinkedListClass.cpp - Test program

Exercises

Singly linked lists: HSM Ch.4.2, exercises 2, 4, 5.
Circular linked lists: HSM Ch.4.4, exercise 1.

Lab Tasks

Counting Words

Exam Style Questions

Define the ordered list ADT.
Give a C++ header file showing the classes for a decent linked list implementation. You need not give the function declarations, but you must declare the data members.
Draw a picture of a {linked list,circular linked list,doubly linked list} with nodes containing the integer values 1, 16, 27, 92. Do not use any dummy nodes.
What is the difference between an internal and an external iterator?
What is the space complexity of a {linked list,circular linked list, doubly linked list} for storing N fixed size items of data?
What is the big-O time complexity of {traversing,inserting a node at the front,inserting a node at the end} a {linked list, circular linked list,doubly linked list}? Explain your answer.