Tutorials on Advanced Math and Computer Science Concepts

Implementating the List Data Structure

A list is a data structure that is like an array in functionality. The main difference is that an array will typically have a static size, declared at the time of declaring the array. With a list, the size can grow with each insert by the user.  This is helpful for situations where the amount of data we are working with is variable in size. For instance, if we are processing a CSV file with a set of records in it, the number of records a user provides might be different on every run. Rather than declaring an array to the size of the CSV, we can just insert the records without worrying about size, giving us a more efficient solution.

The implementation of a list mimics the implementation of a stack and queue. It is important to note however that a list does not have a specific storage structure, such as first in first out or last in first out. Typically, we allow the user to be able to remove at any index they like. For insertion, usually the user can insert at either the front or rear of the queue, using different methods for each. In addition to these differences, we also keep track of the length of the list, to be able to easily report it to the user, in cases where they may want to iterate the list.

To implement this functionality, we start with a Node object that is the same as a stack or queue.

In the actual List object, we need to keep track of two properties. The first is the head of the list, which indicates the first element in the list. The second is the length of the list, which we need to increment on inserts and decrement on removes. To start, let's have a look at the properties, construction, and insert portions of the list.

You can see that as discussed, we have two properties, the front of the list, and the length of the list. When we insert, you'll notice the logic is very similar to a stack insert. We check if there is a front, and if so, we set the new front and point to the old one. If there is no front, we simply set the front. The only real difference is that we increment the length when the process is completed.

The remove operation is more interesting, as it allows the user to remove at any index they choose. In order to handle this, we need to iterate the list starting at the head, until we reach the index chosen by the user. Once we reach this, we set the node before that index to point to the value that comes after the index chosen. This essentially cuts the index chosen out of the list, as shown below.

With this code, we can successfully add and remove values from our list, which is the basic functionality required for a list implementation. There are a few other operations that can be useful to have, such as inserts to the rear of the list, and functions to get the length and check if the list is empty. Let's look at how we could implement these methods.

Inserting to the rear uses a similar logic to removal from an index.  We create a holder for the front of the list, and iterate until we reach the end of the list. Once we reach the end, we update the node to point to our insert value, and we are done.

As for our length related methods, we can return the length property to determine the length of the list. If we want to check if the list is empty, we simply return the result of checking if the length of the list is 0.

As a final note, let's take a look at how we can use a list, and a diagram of how the operations work.

There are a lot of different extensions you can make to the list class. Methods to check if a value is in a list, and to remove a specific value are typically good methods to try implementing. Implementing these methods will help you further your understanding of lists, and also enable you to have more functionality when using your list class.