Collections and Data Structures

Create UML class models of the following data structures.

Linked Lists

A linked list contains references to two list nodes: first and last. A list node may have a predecessor and successor list node. A list node may have a label of type T.

Trees

A tree contains a reference to a tree node called root. There are two types of tree nodes: parents and leafs. Every tree node has a reference to its parent (except a root). A tree node may have a label of type T.

Stacks and Queues

 

 

Directed Graphs

A graph node may have a label of type T and may contain links. A link may have a label of type S. A link has source and destination graph nodes. A graph node is the source of all of the links it contains. A directed graph contains graph nodes and lniks.

Templates in UML

Generic classes and interfaces can be shown with template parameters:

My convention: untyped template parameters will be assumed to be type parameters.

Unfortunately, Star UML has not yet implemented template bindings. For example, suppose we want to design lists as linked nodes:

While UML does provide a notation for the class Node<String>, StarUML has not yet implemented this notation. Instead, we will show String as the default value of T:

This may not work very well if we have a model containing both Node<String> and Node<Int> classes.