< Back

Lecture 25 - Linked Lists

---

As usual, create a directory to hold today's activities:

$ mkdir ~/cs170/labs/lab25 
$ cd ~/cs170/labs/lab25 

---

Data Structures

We have already begun our descent down the rabbit hole of Data Structures on Friday. Today, we will start looking at a slightly more complicated data structure known as Linked Lists.

A Linked List is what we call a linear data structure. Data is stored as a series of Nodes, and access to this data is restricted by traversing through all of the previous elements inserted. One oddity of this approach is that each of these nodes must store a pointer to data of the same type. So this is a recursive data type!

---

Details

Create a C++ class called LinkedList. This means you need a .h and .cc file for this class. You are going to be implementing your own version of the LinkedList class

INSIDE of your LinkedList class, you should define a new class called Node. This class is nested inside of the Linked List class, since only the Linked List should really care about Nodes. Anyone interacting with the list should not need to know about this Node class.

Your Node class will have two public data members: data (and integer), and next (a Node pointer). Notice that we can leave these data members as public, because this class will only be modified from within our Linked List class.

In your LinkedList class, you should have two private data members: front (a Node pointer, which is a pointer to the first node in the list), and numElements (and integer, the number of elements stored in the list.

Your linked list should start off empty. Therefore, front should be NULL, and numElements should be 0. Add a method void append(int pData), which will insert the parameter pData at the end of the linked list.

Example

You won't exactly be able to verify your code until you've implemented the next part. However, you can always hand trace your code to verify it is functioning correctly.

  LinkedList myList;

  for(int i = 0; i < 10; i++) {
    myList.append(i);
  }

  //ASSERT: myList now contains the integers 0 - 9 in sequential order.

---

Once you have written the above class structure, you will probably want some mechanism for verifying the Linked List has been structured correctly. We can easily write a print method as part of the linked list, to print the list to standard output. However, there is a more elegant mechanism provided by C++ to solve this issue: operator overloading!

Details

We want to be able to do cout << aLinkedListObject << endl; in our programs. To accomplish this, in your LinkedList.h file, add a method to the Linked List class:

friend ostream & operator<<(ostream & out, LinkedList & list).

Lets break this down a little bit. First, notice that this is a friend function. The normal way we invoke methods in C++ is using the . or -> operators. So we could do myLinkedListObject.print();. However, in this case, we aren't doing that. As such, this overloaded operator is NOT a method of the class. However, we would like to use the private attributes of the class in this function. Therefore, if we declare it as a friend in our class definition, we will be allowed to access those private pieces of member data.

We also have a new datatype here: ostream. This is the generic output stream datatype. iostream is-a ostream (which means it inherits the ostream class!). So I will be allowed to not only use cout, but also cerr and any file i/o classes we want to use.

Notice this also takes a reference to a linked list as a parameter. You do not need to do anything special in order to pass a parameter by reference.

The implementation for this function should be in your LinkedList.cc file. It should look like:

ostream & operator<<(ostream & out, LinkedList & list) { ... }.

Notice that the friend keyword is dropped outside of the class definition. This function should simply iterate through the elements of the list, outputting them to the out stream piece by piece until the end.

Example

  LinkedList myList;

  for(int i = 0; i < 10; i++) {
    myList.append(i);
  }

  cout << myList << endl;
  //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9,]

 

---