Hello everyone,
Following up on our first round of the Lebgeeks Programming Competition, I had the idea of writing a quick tutorial on linked lists.
Targeted audience:
I will be writing the code in C. I will assume that you know how to write and read basic C code. If you come from a different programming language, you should not have any trouble understanding the basic principles explained here. In all cases, a good understanding of pointers is necessary to understand the code.
Objectives:
The goal of this tutorial is to set up an introduction to data structures by studying and implementing linked lists. Upon finishing the tutorial, you should be able to implement your own linked lists, as well as a library of useful functions. We will also talk about the pros and cons of linked lists, and will end the tutorial by giving a small exercise.
Note: This tutorial was inspired by a tutorial on linked lists written by Alexandre Haffner
Let's begin: the linked list, an introduction
Organizing your data can sometimes be a real challenge. You probably know how to organize them in arrays, which can solve a lot of trouble, by giving your data a common naming pattern. However arrays, though very useful in certain cases, have some serious limitations. Here's an example:
my_array[4] = {3, 10, 24, 5};
Take this array. Now let's imagine that I want to remove the second entry of the array (10). In order to fill the void left in the second position, I would have to translate all the remaining elements by one position.
// my_array after removing the second entry.
{3, NULL, 24, 5}
//In order to remove the NULL value, I can only translate "24" and "5" by one.
The translation operation can be very costly, especially for really big arrays. The same problem occurs when adding a new element in the middle of the list. In order to insert an element between "24" and "5", I would first need to translate "5" (and all the elements after it) by one, beforehand. Linked lists are actually a great alternative that make it easier to add or remove new elements to the list.
Another major problem with arrays is that their size is fixed. Say you are programming a phonebook program, how would you store all the entries? It's a common practice to declare a variable with very large size (like one million), but what if this size is ever reached? Maybe your phonebook will get to a million entries. And do we really need to waste so much memory? Linked lists have no limit when it comes to size.
How do linked lists work
The main idea is to create a custom structure representing each node of your linked list. Each node would contain a data as well as a pointer to the next node of the list. It may sound confusing. To be honest, I remember the first time I was told how linked lists work I thought that computer scientists are crazy creatures coming from another planet. But do not worry, you'll find that linked lists are very convenient thing to use. Remeber how messed up pointers sounded in the first time you heard about them. Anyway, I suggest instead of talking useless theories, we jump straight to the code.
A Node
To make things easier, we will consider that we want to populate the linked list with simple integers. It will be stored in a variable called data. Keep in mind that you could replace it with anything else.
We will start by defining the structure for a single node.
#include <stdlib.h>
typedef struct Node Node;
struct Node
{
int data;
struct Node* next;
};
tyepdef Node* llist;
We created the Node type, a structure that contains an int (data) and a pointer to the next Node. Then we created
llist (stands for linked list), a pointer to the node. Manipulating a linked list consists of pointing to the first Node of the list. Using the
next pointer, we can then cyle through the list to reach any element. Note that we simply created the
llist type for clarity reasons.
(PS Do not forget to include the stdlib library!)
Now let's take a look how to declare a linked list.
#include <stdlib.h>
typedef struct Node Node;
struct Node
{
int data;
struct Node* next;
};
typedef Node* llist;
int main (int argc, char** argv)
{
/* 3 different ways of declaring linked lists. */
llist my_list1 = NULL;
Node* my_list2 = NULL;
struct Node* my_list3 = NULL;
return 0;
}
NB: You should have been taught to initialize your pointers to NULL. This is true for linked lists more than ever. If you don't, your program will consider that the first node is not empty. This error is frequent, pay attention!
Manipulating linked lists
We now know to declare a linked list, it is time for us to start using them. Now pay attention to the following code. If you understand it, you will really understand how linked lists work. We will start easy with a function
insertHead(), a function that inserts a new element to the top of the list.
llist insertHead (llist my_list, int value)
{
/* We create the new node we want to insert */
llist* new_node = malloc (sizeof(Node));
/* We put the correct value in the new element */
new_node->data = value;
/* We assign the next pointer to the previous head of the list */
new_node->next = my_list;
/* Returning the new list */
return new_node;
}
We will now implement a
insertTail() function, that appends a new element to the end of the linked list. This function is a little bit more complicated because we do not have a pointer to the last element of the list. So our first concern is to find that element. In order to do so, we will have to iterate the list, starting from head, going from next pointer to next pointer, until it points to NULL. This is when we will know we reached our final element. The rest is predictable.
llist insertTail (llist my_list, int value)
{
/* Creating new element and assigning its value.
Since it will be the last item of the list, it points to NULL */
Node* new_element = malloc (sizeof(Node));
new_element->data = value;
new_element->next = NULL;
/* If my_list is empty, we simply return the newly created element. */
if (my_list == NULL)
{
return new_element;
}
else
{
/* To find the last element, we declare a temp pointer */
Node* temp = my_list;
while (temp->next != NULL)
{
temp = temp->next;
}
/* We make the final element point to the new element */
temp->next = new_element;
return my_list;
}
}
Be sure to understand these two codes entirely before moving on. As you can see, llist is nothing more than a pointer to the first element (top or head) of the linked list.
I usually find it easier to understand some functions, by understanding how they are used. So here's an example that might help:
int main (int argc, char** argv)
{
llist my_list = NULL;
/* Adding first element to the list */
my_list = insertHead (my_list, 5);
/* Adding the second element (7). Note that element is added
at the head, so the list is now: [7, 5].
my_list = insertHead (my_list, 7);
/* Adding the third element at the tail: [7, 5, 9]. */
my_list = insertTail (my_list, 9);
return 0;
}
I know I am repeating myself, but it is very important that you understand the implementation of these two functions. Do not continue reading otherwise, the rest of the tutorial will not help you more. And to test if you really did understand it, here are some exercises for you. I'm going to give you the answers, but make sure to try and code them for yourself first.
1- Implement function
void printList (llist my_list);
As it name suggests, it should print every element of the list to the screen.
Answer:
void printList (llist my_list)
{
Node* temp = my_list;
while (temp->next != NULL)
{
printf ("%d ", temp->data);
temp = temp->next;
}
}
2- Using the three functions we have so far:
- insertHead()
- insertTail()
- printList()
write the main of a small program that would print this linked list to the screen:
10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10
Answer:
int main (int argc, char** argv)
{
llist my_list = NULL;
int i = 0;
for (i=1; i<11; i++)
{
my_list = insertHead (my_list, i);
my_list = insertTail (my_list, i);
}
printList (my_list);
}
3- Write a function
int isEmpty (llist my_list);
Answer:
int isEmpty (llist my_list)
{
if (my_list == NULL)
{
return 1;
}
else
{
return 0;
}
}
This is it for the first part of this tutorial. I will be updating the tutorial with new, more complex functions to use on linked lists soon. For now make sure you understood those basic principles, so that next time we can go a lot faster.
I hope you are enjoying it,
rahmu