CPSC170
Fundamentals of Computer Science II

We have seen how to get memory allocated dynamically, i.e., at run-time. Using this mechanism, we have seen how to create arrays of arbitrary length. Often, though, arrays are not the best data structure to use. For example, consider a stack. It grows as users push data objects. A dynamic array will work for this. But, in typical programs, a stack grows and shrinks often. Dynamic arrays are ideal when the data structure grows, but does not shrink. As another example, consider a program that needs a list of objects and the program needs to add elements to the list, possibly somewhere in the middle of the list, or needs to remove elements, possibly from the middle of the list. Again, in this case, dynamic arrays are not ideal, since inserting an element as the i-th element, or deleting the i-th element, where i is the index of an element in the middle of the list will require moving all the elements in the list beyond index i.

Linked data structures are very useful in the above two situations, and in many other situations. A linked data structure is essentially one where an element of the structure contains some data, and also contains one or more pointers (references) to other elements in the structure. A good way to visualize such structures is as nodes that have pointers to other nodes. Each node contains data objects and pointers to the other nodes.

Linked Lists

The simplest linked data structure is that of a singly linked list. Such a structure is also called a linear data structure, i.e., where one can traverse from one element to a unique next element. (Arrays are examples of linear data structures too.) A singly linked list can be implemented using two classes. One class for the nodes of the list. A node holds a data element and a pointer to its successor (the element that follows it). The second class stores a pointer to the first element of the list (the head).

Node

In this lab we will only consider the node class. This class is extremely basic. In fact, when we implement the list class, this class will be a private inner class. An inner class is a class declared within another class. This is similar to the iterator class in the container classes.

The node class will contain data members and a constructor. When a class only stores data that has public access, it is typical to use a struct rather than a class. For a singly linked list, a node needs to hold two items, the data stored in the node and a pointer to the node that comes after this node i.e., the next node. The following struct template will be used for our nodes.

template <typename T>
struct Node{
  T _data;                // _data stores the data in the node.
  Node<T>* _next;         // _next is a pointer to the next node. If there is no next node,
                          // _next is set to nullptr.


  Node(const T& data = T{}, Node* next = nullptr)    // Constructs a node with _data set
    :_data{data}, _next{next}{ }                     // to data and _next set to next.
	                                             // Default values T{} and nullptr
                                                     // are used for _data and _next.
};

As you can see the struct Node is very simple. It stores a data value and a pointer to another node. If no node come after a node, then we set the pointer to nullptr. Rember a pointer is simply a memory address, the size of a pointer is independent of what it points to. The efficiency of passing a pointer by value or by references is essentially the same. So most times we will pass pointers by value, we will pass them by reference only when we need to. The following code creates a linked list of three nodes.

int main(){
  Node nnn(3);      // Created a list with node  (3).
  Node nn(2,&nnn ); // Created a list with nodes (2)->(3).
  Node n(1, &nn);   // Created a list with node  (1)->(2)->(3).
}

The first line of main creates a linked list with data 3 and _next pointer set to nullptr. The second line creates a node with data 2 and _next pointer set to the address of the previously created node nnn. Finally the third line creates a node with data 1 and _next pointer set to the address of the previously create node nn. We can view the content of a list with a simple print function. The function takes a pointer to a Node object, if it is a null pointer then the list is empty and there's nothing to print, otherwise, the data of the node pointed to is printed, then the we move on to the next item and repeat the process. This can be done with the following while-loop.

template <typename T>
void print_list(Node<T>* node){    
  while(node != nullptr){  
    cout << node->_data << " ";
    node = node->_next;    // move to the next node.
  }
}

Use this print function to print the lists created in main to see that the correct lists are created. Play around with the Node struct. In main create a list of 4 strings so that the printed list is "Paved with good intentions". Make a Node that cause print_list to loop infinitely. Let me know if you can't.

As a standalone struct, node is poorly designed. It can easily be misused to create lists with no end. In the next lab we will wrap Node in a class that will ensure that Node is used properly. For now, just get comfortable with the concept of a linked list i.e., a object with a pointer to another object. Don't bother about memory leaks, we will handle all that later.

Exercise

Create a function template with the following header/signature.

Node* create_list(unsigned list_size).

The function should create a list of length/size list_size. The data elements should be the default value of a variable of type T. The list should be created on the heap (why not on the stack?), the value returned should be a pointer to the head (first element of the list) of the list. If list_size is 0 it should return nullptr. Test this function with the print function to see that it works. You need to specify the function's template when you call it.

Create a function with header unsigned lst_size(const Node<T>* node). This function should return the size of the list pointed to by node. What should this function return when node == nullptr?

Create get/set functions to set/get the values stored in a list. For example get(my_list, 4) should return the value stored in the 4th node of my_list. It could throw an exception if the list doesn't have up to 4 nodes. set(my_list, 10, val) should set the value in the 10th node of my_list to val. Use the print function to test these functions.