What is a Linked List Anyway?
Linked Lists are a sequential access data structure comprised of a series of ‘nodes’. Nodes are a developer defined type, usually created from structs in languages like C, or classes in object oriented languages like C++, Java, and Swift.
/* a typical linked list node in C */
typedef struct node {
void* data;
struct node *next;
} listNode_t;
Linked Lists are a fundamental Abstract Data Type, but with things like the C++ Standard Template Library, the Java Standard Library, and most modern programming languages equivalents, it would be a very rare thing indeed to be expected to implement the list ADT in any kind of production or professional code.
So why should a programmer today bother to study linked lists?
The answers might surprise you! I was going to make a bunch of puns involving dogs, fingers, lasers, and memory but it made me contemplate my own sense of humor so i’ll just come out and say it. The number one reason someone should study linked lists?
POINTERS.
Ah yes, those pesky buggers that have brought many a programmer to the verge of throwing their computer out the window, and the cause of more late night debug marathons than a misplaced ‘;’.
Linked Lists are a great way to bone up your Pointer skills. Did asterisks and ampersands have you running like hell from C straight into the arms of python and Java? maybe you should have slowed down and taken a trip down Linked List lane.
Ok, great, Pointers. What Else?
What else? How about the more advanced ADT’s that build on the idea of ‘Linking Nodes Together’, such as Trees, Graphs, Stacks, and Hash Tables!
Linked Lists provide us with another advantage when creating these more complex data structures. We could implement these ADT’s with arrays. The drawback to this is that with the linked approach, we don’t need to know how many nodes we’re going to have ahead of time!
Sure, we could use the likes of std::vector in C++, Heck, std::list is implemented with a doubly linked list! But that doesn’t negate the value of learning the intricacies of Linked Lists and how to implement them ourselves. Some people still use C!
Ok, Data Structures. And?
Job readiness. Take a quick look at top coder, geeks for geeks, and a myriad of other job prep sites for programmers and you’ll be inundated with a myriad of Linked List related content. If professional code isn’t likely to include hand implemented linked lists, what gives?
An understanding of the fundamentals of a language, data structures, and algorithms is what. A programmer who struggles with linked lists, is probably going to have trouble with the far more intricate areas of software development. Linked List questions give a reviewer a relative idea of where the person in question stands in regards to their understanding of the aforementioned areas.
So without further ado, lets get to it.
Linked List Basics
As mentioned above, a linked list is created by dynamically allocating a series of nodes and linking them together like a chain.
The simplest type of linked list is the Singly Linked List. Singly linked lists can only be traversed in one direction. You start at the beginning, and keep going till you find the node you want, or hit the end of the list.
Creating a Singly Linked List
In this article we’re going to create a singly linked list of integers in C++. The first thing we’re going to do is create a class for our ‘node’ type:
class node {
public:
int data;
node* next;
node(int data) : data(data) { next = nullptr; }
node(const node&) { next = nullptr; }
node() { next = nullptr; }
};
With that done we can move on to creating the list itself. Theres actually two schools of thought when it comes to linked lists, and they differ in whether they use ‘dummy’ nodes or not. Personally, i like using dummy nodes. They make things like creating lists in sorted order easier. It’s also the way that i first learned how to implement Linked Lists, so thats the method I’m going to show here.
Defining the List Class
class List {
public:
node* head;
node* last;
node* tail;
inline bool empty() { return head->next == tail; }
void add(int num);
void remove(int num);
bool find(int num);
List()
{
head = new node;
tail = new node;
head->next = tail;
tail->next = tail;
last = head;
}
List(const List&) { }
};
We declare pointers to our two dummy nodes: ‘head’ and ‘tail’, thus named because they will be the nodes that respectively precede and follow our list nodes. In our class constructor we dynamically allocate them from heap memory using the ‘new’ keyword and assign our pointers to them. we then use the ‘next’ pointer of our nodes to link the two together. Notice that tail’s next pointer points back to itself: this prevents us from running past the end of the list when iterating over it, avoiding one of the more common pointer errors: illegal access.
Basic Linked List Functions
With our List defined its time to move on to the member functions. The first function we’re going to cover is the simplest to implement: determining if our node is empty or not. This is a simple fair. If our ‘head’ node points to our ‘tail’ node, that means there are no nodes in between them, and our list is empty. The code for that function was covered in our List class definition as ‘inline’ bool, returning true if the list is empty, and false if not. Lets take a quick look back at that code:
/* code to determine if a list is empty */
inline bool empty() { return head->next == tail; }
Because our code is checking if one condition is true or not, it makes sense to inline this code, leading to a more efficient program. Next task up: adding to a list. To add a node to our linked list involves three crucial steps:
- allocate and create a new node from heap memory.
- point a node in our list to that node,
- and point the new node to the node that our referring node was previously pointing to.
Now, if we wanted, we could add every node right after head and grow the list off the front, but that would result in our list being created with items in the opposite order of which they were added. We want to grow our list in the order in which items are added, but we want to keep our add function running O(1). If we were to iterate over our list to the end and insert our node there, our add function would be linear time (O(n)) instead. This is where the last pointer shines.
/* code to add an item at the end of a list */
void List::add(int num)
{
node* x = new node(num);
x->next = last->next;
last->next = x;
last = x;
}
Not to difficult right? With that we have everything we need to create a list and add items to it. Before we cover deleting and finding items in a linked list, there’s one other topic that bears discussion.
Iterating over linked lists
The nature of linked lists makes iterating over (looping through) them a trivial affair but one that none the less deserves discussion. The steps for iterating over a list are:
- Declare a pointer and point it to the first node in the list. Lets call this pointer the list iterator.
- Process the node currently being pointed to.
- Point the iterator to iterator->next.
- Repeat until the end of the list.
The syntax of the for(;;) loop allows us a natural way to do this:
/* iterating over a linked list */ for (node* listItr = list.head->next; listItr != list.tail; listItr = listItr->next)
Pretty nifty. Of course, a while loop could be used as well, but the for() loops syntax allows for cleaner looking code. Lets take a look at a function that inputs a linked list and prints out all of its elements:
/* print the contents of a linked list */
void printList(List& list)
{
if (!list.empty())
{
for (node* listItr = list.head->next; listItr != list.tail; listItr = listItr->next)
{
std::cout<<listItr->data<<" ";
}
std::cout<<"\n";
} else {
std::cout<<"List is empty!\n";
}
}
Finding an item in a linked list
Finding in an item in a linked list is one of the areas where linked lists show their weakness: access to elements can only be done sequentially. Because of this, find() is at best a O(n) function, because techniques like Binary Search aren’t possible on a linked list, we’re left with Sequential Search:
bool List::find(int num)
{
if (!empty())
{
for (node* listItr = head->next; listItr != tail; listItr = listItr->next)
{
if (num == listItr->data)
{
return true;
}
}
}
return false;
}
Deleting and item from a linked list
With the exception of deleting the first or last item from a linked list, deletion is also O(n), for the same reason as find(), we have to iterate over the list to find the item we want to delete, and since access is sequential, deleting an arbitrary node is thus O(n).
/* deleting an arbitrary node from a linked list */
void List::remove(int num)
{
if (!empty())
{
for (node* listItr = head; listItr != tail; listItr = listItr->next)
{
if (num == listItr->next->data)
{
node *t = listItr->next;
listItr->next = listItr->next->next;
delete t;
}
}
}
}
There are a couple of subtle differences in this code from our find() method. Because of the way removing a node from a linked list works, were not checking if the current node is the one were looking for. We’re actually checking to see if the NEXT node is the one we want. Take a closer look at how the node is removed to under stand why:
/* unlinking our node from the list */ node *t = listItr->next; listItr->next = listItr->next->next; delete t;
By checking if the next node is the one we want, we can remove it from the list by pointing next to the node AFTER the next node. This essentially makes our linked list jump around the node. We assign a temporary pointer to the node we are removing and then call delete on that node to avoid creating a memory leak when we remove the node from the list.
And with that our basic implementation of a singly linked list is complete. The following code shows that everything is working as expected:
int main()
{
List myList;
printList(myList);
myList.add(1);
myList.add(24);
myList.add(3);
printList(myList);
if (myList.find(24))
{
myList.remove(24);
}
myList.add(16);
printList(myList);
return 0;
}
output:
List empty!
1 24 3
1 3 16
There you have it: Creating, Adding to, Searching in, and Deleting from Singly Linked Lists. That wasn’t too bad right? Nope! So what are some important things to remember?
- Avoid memory leaks! For every node created using new, destroy it using delete when you’re done with it. Better yet – use smart pointers!
- By using a pointer to keep track of the last node building the list in the same order we insert the items can be done in O(1) instead of O(n).
- Searching and Deletion from a linked list takes linear time: if you’re going to be doing a lot of searching, use a more efficient data structure – Binary Search Trees are a good choice.
The full code for the examples shown here can be found on my github at:
https://github.com/maxgoren/examples/blob/main/linkedlist.cpp
