Introduction
In this previous tutorial, we learned about linked lists. Linked list are a way to store data when you don’t know how many items you are going to have until you are done. A simple example would be finding all of the letters in a text file that start with the letter a. We also discussed some of the performance implications of a linked list versus an array.
In this tutorial, we are going to implement some common operations that would be performed on a linked list like adding an element to the end, inserting an element in the middle of the list, and removing an element from the list.
Code
So, the first thing that I’m going to do is declare a class to store and manage my linked list:
class LinkedList
{
public:
LinkedListItem* Head;
LinkedList();
};
LinkedList::LinkedList()
{
Head = NULL;
}
This way, I can group all of my methods that deal with the linked list together in a logical place. So, the first method that we are going to put on the class is a way to print out the contents of the list:
void LinkedList::Print()
{
LinkedListItem* curr = Head;
while(curr != NULL)
{
cout << curr->Number << endl;
curr = curr->Next;
}
}
This is a great first method to write, since it will give us a way to debug the rest of the methods. Next, we’ll add a way to add elements to the list. As a slight optimization, I’m going to also add a variable on the class that stores the end of the list, as well as the beginning:
class LinkedList
{
public:
LinkedListItem* Head;
LinkedListItem* End;
LinkedList();
void Print();
void Add(int number);
};
void LinkedList::Add(int number)
{
LinkedListItem* item = new LinkedListItem(number);
if(Head == NULL)
{
Head = item;
End = item;
}
else
{
End->Next = item;
End = End->Next;
}
}
This should be pretty straight forward. The only thing to watch out for is that when we first create the list, the Head variable will be NULL, so if it is the first item in the list, we need to update the Head variable.
Now, let’s write a function to grab an item at a random index in the linked list:
LinkedListItem* LinkedList::ElementAt(int index)
{
int idx = 0;
LinkedListItem* curr = Head;
while(curr != NULL && idx < index)
{
curr = curr->Next;
idx++;
}
if(idx != index)
{
curr = NULL;
}
return curr;
}
If you remember the performance discussion from the previous tutorial, this is why accessing random elements in a linked list is slower than an array.
This method also brings up an interesting question of what should we do if the index that is requested doesn’t exist? There are many ways to solve this problem, but in this case we return a NULL pointer. This is a good indication to the user that something went wrong.
Now, using that function, we can write a function to insert an element in a random location:
bool LinkedList::Insert(int index, int number)
{
LinkedListItem* item = new LinkedListItem(number);
if(index == 0)
{
LinkedListItem* tmp = Head;
Head = item;
item->Next = tmp;
if(End == NULL)
{
End = item;
}
return true;
}
else
{
LinkedListItem* prev = ElementAt(index - 1);
if(prev != NULL)
{
LinkedListItem* tmp = prev->Next;
prev->Next = item;
item->Next = tmp;
if(prev == End)
{
End = item;
}
return true;
}
return false;
}
}
The easiest way to understand this function is to start with thinking about the case where we need to insert an element in the middle of the list. In this case, we need to update the element before it’s Next variable to point to the element that we are inserting, and we need to update the element that we are inserting’s Next variable to point to the element that the previous element’s Next variable used to point to. That’s the tricky part, the rest is just minor bookkeeping.
The other thing to note about the method is that it returns whether or not the operation succeeded. This is important because the insert can fail if the caller requests an index that is less than zero or greater than the length of the list, and it is critical to let the caller know if the operation was successful.
Now we need to consider removing elements from the list, making sure to clean up any memory that was allocated to store them. The first thing that we will implement is removing all of the items from the list:
void LinkedList::Clear()
{
LinkedListItem* curr = Head;
while(curr != NULL)
{
LinkedListItem* tmp = curr;
curr = curr->Next;
delete tmp;
}
Head = NULL;
End = NULL;
}
Clearing the list is pretty straight-forward. The only thing to remember is to call delete on the item that we remove! Next is removing an item from the list. This is the reverse of the insert case above, so we need to make sure that the Next pointers are all correct after we are done:
bool LinkedList::Remove(int number)
{
LinkedListItem* prev = NULL;
LinkedListItem* curr = Head;
while(curr != NULL)
{
if(curr->Number == number)
{
if(prev == NULL)
{
Head = curr->Next;
if(End == curr)
{
End = NULL;
}
delete curr;
}
else
{
prev->Next = curr->Next;
if(End == curr)
{
End = prev;
}
delete curr;
}
return true;
}
prev = curr;
curr = curr->Next;
}
return false;
}
This removes the first occurrence of the number that was passed in, and does nothing if the number that is passed in does not exist in the list. Another way to remove an item from the list would be to remove the item at a given index.
The last thing that we are going to do is put a call to Clear in the destructor:
LinkedList::~LinkedList()
{
Clear();
}
This will ensure that the memory will be cleaned up properly when the list the deleted.
Summary
In this tutorial, we implemented some of the common operations that can be done on linked lists. Hopefully doing this illustrated some of the benefits and weaknesses of linked lists that we mentioned in the previous tutorial.
In the next tutorial, we will be going over the STL linked list. Since linked lists are so common, there is a standard implementation that you can use for your projects. This saves you the time (and tracking down the bugs) associated with writing your own. However, even if you do use a standard implementation, it is still very important to understand what is going on under the covers. This will help you know whether or not it is the correct fit for what you are trying to accomplish.
If you have any questions or comments about what was covered here, post them to the comments. I watch them closely and will respond and try to help you out.