Dynamic data structures can grow and shrink at execution time.

All simple-type names are aliases for corresponding structs in namespace System.

Each simple type struct declares methods for manipulating the corresponding simple-type values.

Each struct that represents a simple type inherits from class ValueType in namespace System.

A boxing conversion creates an object that contains a copy of a simple-type value.

An unboxing conversion retrieves a simple-type value from an object.

A self-referential class contains a data member that refers to an object of the same class type. Self-referential objects can be linked to form data structures, such as lists, queues, stacks and trees.

Creating and maintaining dynamic data structures requires dynamic memory allocation—a program’s ability to obtain more memory at execution time (to hold new nodes) and to release memory no longer needed.

Operator new takes as an operand the type of the object being dynamically allocated, calls the appropriate constructor to initialize the object and returns a reference to the new object. If no memory is available, new throws an OutOfMemoryException.

A linked list is a linear collection (i.e., a sequence) of self-referential class objects called nodes, connected by reference links.

A node can contain properties of any type, including references to objects of other classes.

A linked list is accessed via a reference to the first node of the list. Each subsequent node is accessed via the link-reference member stored in the previous node.

By convention, the link reference in the last node of a list is set to null to mark the end of the list.

A circular, singly linked list begins with a reference to the first node, and each node contains a reference to the next node. The “last node” does not contain a null reference; rather, the reference in the last node points back to the first node, thus closing the “circle.”

A doubly linked list allows traversals both forward and backward. Such a list is often implemented with two “start references”—one that refers to the first element of the list to allow front-to-back traversal of the list and one that refers to the last element to allow back-to-front traversal. Each node has both a forward reference to the next node in the list and a backward reference to the previous node.

In a circular, doubly linked list, the forward reference of the last node refers to the first node, and the backward reference of the first node refers to the last node, thus closing the “circle.”

Stacks are important in compilers and operating systems.

A stack is a constrained version of a linked list—new nodes can be added to and removed from a stack only at the top. A stack is referred to as a last-in, first-out (LIFO) data structure.

The primary stack operations are push and pop. Operation push adds a new node to the top of the stack. Operation pop removes a node from the top of the stack and returns the data object from the popped node.

Queues represent waiting lines. Insertions occur at the back (also referred to as the tail) of a queue, and deletions occur from the front (also referred to as the head) of a queue.

A queue is similar to a checkout line in a supermarket: The first person in line is served first; other customers enter the line at the end and wait to be served.

Queue nodes are removed only from the head of the queue and are inserted only at the tail of the queue. For this reason, a queue is referred to as a first-in, first-out (FIFO) data structure.

The insert and remove operations for a queue are known as enqueue and dequeue.

Binary trees facilitate high-speed searching and sorting of data.

Tree nodes contain two or more links.

A binary tree is a tree whose nodes all contain two links (each of which can be null). The root node is the first node in a tree.

Each link in the root node refers to a child. The left child is the root node of the left subtree, and the right child is the root node of the right subtree.

The children of a node are called siblings. A node with no children is called a leaf node.

A binary search tree (with no duplicate node values) has the characteristic that the values in any left subtree are less than the value in that subtree’s parent node, and the values in any right subtree are greater than the value in that subtree’s parent node.

A node can be inserted only as a leaf node in a binary search tree.

In a preorder traversal, the value in each node is processed as the node is visited. After the value in a given node is processed, the values in the left subtree are processed, then the values in the right subtree are processed.

In a postorder traversal, the value in each node is processed after the node’s left and right subtrees are processed.

In an inorder traversal, the value in each node is processed after the node’s left subtree is processed and before the node’s right subtree is processed.

The inorder traversal of a binary search tree processes the node values in ascending order. The process of creating a binary search tree actually sorts the data (when coupled with an inorder traversal)—thus, this process is called the binary-tree sort.

The binary search tree facilitates duplicate elimination. As the tree is created, attempts to insert a duplicate value are recognized because a duplicate follows the same “go left” or “go right” decisions on each comparison that the original value did. Thus, the duplicate eventually is compared with a node containing the same value. The duplicate value may simply be discarded at this point.