A linked list is a data structure that
consists of a group of nodes which are linked together. These are
one of the simplest and most common data structures for C programs.
One of the biggest advantages that linked lists have is they are
efficient at inserting and deleting elements within the sequence. The
biggest drawback of linked list is you generally have to traverse the
list to find particular nodes or to get the number of nodes in the
list.
There are several varieties of linked
lists like singly linked, doubly linked and multiply linked. We will
be using singly linked lists in this blog as we create various
networking tools therefore, in this first tutorial, we will build a
singly linked list library that we can integrate with our networking
code. While the code for this library could be optimized and
compacted, I feel that it is more important to make code readable
when learning therefore the code for this library and most of the
code in this blog will be written with functionality and readability
as the primary objectives.
In a singly linked list each node has one or more data fields and
a “next” field that points to the next node in the list. The
preceding image shows how this works where the “next” element
contains a pointer to the next node in the list.
You will be able to see how the linked
list works as we go though the code but first lets take a quick look
at the header file for our linked list library:
#ifndef
LinkedListTest_linkedlistlib_h
#define
LinkedListTest_linkedlistlib_h
struct
node
{
int
num;
char
name[16];
struct
node *next;
};
struct
node *buildnode(int num, char *name);
int
addnode(struct node *head, struct node *add);
int
length(struct node* head);
void
deletelist(struct node **head);
struct
node *searchnode(struct node *head, char *name);
int
removenode(struct node **head, struct node *remove);
#endif
We begin by defining the structure that will hold our data. This
structure can contain whatever data elements you need but you will
need to keep the
struct
node *next
element
because
it points to the next node in the list.
Next
we define six functions that we will be implementing for our library.
These functions are:
- struct
node *buildnode(int num, char *name)
– This is a convenience method that will build the node given the
values pass
in.
This function and
the searchnode()
function are the two functions
that
we will need to change
when we add this library to our projects.
- int
addnode(struct node *head, struct node *add) –
This function will add a node to the end of our list. The
head node
is the first node in our structure while the add
node
is the node to add. This
function will return the number of elements that are in the list
after the new node is added.
- int
length(struct node *head)
– This function will return the number
of nodes in
the list. The head
node is the first node in the list. If we passed another node,
besides the first node of the list, then
this function
would return the number of nodes from that node to
the end of the list.
- void
deletelist(struct node **head)
– Deletes the list and frees the memory being used.
- struct
node *searchnode(struct node *head, char *name) –
This function will search the list and return the first structure
that
has a name
element equal to the
name
argument.
- int
removenode(struct node **head, struct node *remove)
– This function will search the list for the remove
node and remove it from the list. This function will return a 0 if
it was successful in finding
and removing
the node or a -1 if the remove
node could not be found.
Now
lets look at each of the functions and see how they work. We will
start with the struct
node *buildnode(int num, char *name)
function. This function takes
two arguments and build a new node
structure with those arguments.
Here is the code:
struct
node *buildnode(int num, char *name) {
struct
node *new = (struct node *)malloc(sizeof(struct node));
new->num
= num;
strncpy(new->name,
name, sizeof(new->name));
new->next
= NULL;
return
new;
}
This
function starts off by allocating memory needed
for
the
new node
structure with the malloc()
function. We will
need to manually release this
memory
when we are finished
with this node
otherwise we will have memory leaks in our application.
Next
we assign the values to our structure. Notice that we use the
strncpy()
function
to copy the name
value into our structure. This is done because the char pointer that
was passed to our function may get released or reused, so in order to
make sure that we do not lose the
value we copy it
into the structure. We also set the next
pointer to NULL because it is not currently part of the
linked
list. Remember this function just creates a node but does not put it
in a
linked
list. To
put a node into a linked list we
we
use the
addnode()
function.
Now
we will look at our int
addnode(struct node *head, struct node *add)
function. This function will add a node to the end of the
list and
return the total number of nodes after the node is added.
int
addnode(struct node *head, struct node *add) {
struct
node* current = head;
int
count = 0;
while
(current->next != NULL) {
count++;
current
= current->next;
}
current->next
= add;
count++;
return
count;
}
The
addnode()
function
accepts two arguments; the first argument is the first node of
the list and the second argument is the node to add. In order to add
a node to the end of the list, we need to loop though the list to
find the end. This
is a weakness of singly linked list; since
we do not store the end of the list or the number of nodes in the
list we need to loop though the whole list to determine the number of
nodes or to find the end of the list.
Since
we do not want to move the pointer that was passed into the function
which
points to the first node of the list, we create a new pointer that we
name current
that also points to the first node of the list. We then set up a
while loop that loops through the list until we reach the end of the
list. We know that we have found the last node when the next
pointer of that
node points to NULL
rather than another node. If the next
pointer does not point to NULL,
we increment our counter and move the current
point to point to the next node in our list.
Once
we find the last node we set the next
pointer of that node to point to
the node that we are adding to the list.
This will put the new node at the end of the list. This does assume
that the next
pointer within the node that we are adding points
to NULL
and
not another node in the list. If the next
pointer
in the new node points to another node in the list then we would set
up a linked list that loops around in a circle. This would create an
endless loop when we attempt to find the end of the list or
when we search for a specific node in the list.
To be on the safe side we could put a line in the function that sets
the next
pointer of the new node to NULL but I left that out because this
function could also be used to combine two
linked lists where
the next
pointer may point to another node in a separate list.
Next
we will look at the int
length(struct node *head)
function. This function will return the number of nodes in our list.
This function accepts one argument which is
the first node in the list. Here
is the code for the length()
function:
int
length(struct node *head) {
struct
node* current = head;
int
count = 0;
while
(current != NULL) {
count++;
current
= current->next;
}
return
count;
}
The
length function is a duplicate of our addnode()
function
described earlier except that we are not adding a new node to the
list once
we find the end of the list.
Now
lets
look at the void
deletelist(struct node **head)
function.
This
function will delete the whole list and free the memory that the list
uses. This function takes one argument which is a pointer to a
pointer that points the the first
node of the list
to remove. Here is the code for our deletelist()
function.
void
deletelist(struct node **head) {
struct
node *next;
struct
node *current = *head;
while
(current) {
next
= current->next;
free(current);
current=next;
}
*head
= NULL;
}
In
the deletelist()
function we loop through the list. For each node in
the list we
assign the next
pointer to point to the next node in the list. We
then use the free()
function to free the memory that is assigned to the current node.
This
allows your application to reuse this memory location and prevents
memory leaks. We then set the current
pointer to point to the next node in the list. Finally, once all of
the nodes are removed, we set the pointer which pointed to the first
node in the list to NULL
to prevent our application from using it by mistake.
Now
lets see how the struct
node *searchnode(struct node *head, char *name)
function works. This functions searches the linked list for the
first node that has a name
value that is equal to the name
argument passed to the function. This function takes two arguments;
the first argument is a pointer to the first node in the linked list
and the second argument is a pointer to the char string that we are
searching for. Lets look at the code for
the searchnode()
function.
struct
node *searchnode(struct node *head, char *name) {
struct
node* current = head;
while
(current != NULL) {
if
(strcmp(current->name,name) == 0)
return
current;
current
= current->next;
}
return
NULL;
}
We
start off by creating a while loop that loops though our list.
We
then compare the name
element of each node with the name
argument passed into the function using the strcmp()
function. If they are equal, then
we found the node we are looking for and
return the
current node. If they are not equal, we our
loop moves
to the next node. If we are unable to find a node that contains the
name
argument we return NULL.
Finally
lets look at the int
removenode(struct node **head, struct node *remove) function.
This function will remove a specified node from our linked list.
This function takes two arguments; the first argument being a pointer
to a pointer that points to the linked list to search and the second
argument being a pointer to the node to remove. The
removenode()
function
will return 0 if the node was found and removed or -1 if the node was
not removed. Lets
look at the code:
int
removenode(struct node **head, struct node *remove) {
struct
node* current = *head;
struct
node* prev = NULL;
while
(current != NULL) {
if
(current == remove) {
if
(prev == NULL)
*head
= current->next;
else
prev->next
= current->next;
free(current);
return
0;
}
prev=current;
current
= current->next;
}
return
-1;
}
We begin the
removenode()
function
by defining two pointers. We set the first pointer, current,
to point to the first node of our list and set the second pointer,
prev,
to point to NULL.
When we set up our while loop that will loop though our list, the
current
pointer will always point to the current node that we are checking
and the prev
pointer will always point to the previous node. We will need to know
the previous node in our list because when we find the node to
remove, well will need to change the next
pointer of the previous node so it no longer points to the node we
wish to remove. Lets look at a diagram that shows how we are going
to remove a node from our list.
In
the diagram we can see that in order to remove node2 from our list we
need to change the next
pointer of node1 to point to node3 rather than node2. We would then
free the memory allocated to node2 so we do not have memory leaks in
our application.
Once
we have our two pointers defined we create a while loop that will
loop though our list.
If
the current
node is equal to the remove
node then this
is the node to remove. If this is the node to remove we check to see
if it
is the first node in the list by seeing if the prev
pointer is pointing to NULL.
If this is the first node then we change the head
pointer, that was passed into our function, to point to the next node
in the list otherwise we set the next
pointer from the previous structure to point to the node that the
current node's next
pointer is pointing too. Finally we free the memory that is used by
the current node and return 0 signifying
that we found and removed the node.
If
the current
node is not equal to the remove
node then we set the prev
pointer to point to the current
node and the current
pointer to point to the next node in the list. If we loop though the
whole list and we do not find the remove node, then we return a -1
signifying that we could not find the node to remove.
Now
lets look at some code to test our linked list library:
#include
<stdio.h>
#include
"linkedlistlib.h"
#include
<time.h>
void
waitFor(unsigned int secs) {
long
retTime = time(0) + secs;
while
(time(0) < retTime);
}
int
main()
{
printf("Hello
world\n");
int
i;
for
(i=0; i< 500; i++) {
struct
node *first = buildnode(1,"Jon");
struct
node *second = buildnode(2, "Kim");
struct
node *three = buildnode(3, "Kailey");
struct
node *four = buildnode(4, "Kara");
addnode(first,
second);
addnode(first,
three);
addnode(first,
four);
printf("%d)----------\n",i);
printf("Count
%d\n", length(first));
struct
node *found = searchnode(first, "Kailey");
if
(found != NULL)
printf("found:
%d %s\n",found->num, found->name);
removenode(&first,
first);
printf("Count
after remove %d\n", length(first));
removenode(&first,
found);
printf("Count
after second remove %d\n", length(first));
deletelist(&first);
printf("found:
%d\n",length(first));
printf("-------------------\n");
waitFor(2);
}
return
(0);
}
Inside the
main()
function, we begin by creating a for loop that will loop 500 times.
This loop will allow us to see how our library performs by repeating
the various tasks 500 times. If we analyze the memory usage while
this runs it will also help us to detect any memory leaks.
Within the for loop we create four nodes using the
buildnode()
function. We then create our linked list by adding the last three
nodes to our list using the
addnode()
function. Notice that we do not add the first node to the list with
the
addnode() function,
that is because we use that first node as the first node for the
list.
Now that we have our list built we verify that the list contains
four nodes by using the
length()
function which returns the number of nodes in our list and print that
count to the screen.
Next we use the
searchnode()
function to search for a node that contains the
name “Kailey”. If we find a node that contains “Kailey” then
we print the
num
and
name
elements of that structure to the screen.
We then try to remove the first node in our list by calling the
removenode()
function. We verify that the node was removed by printing out the
total number of nodes in the list after we called the
removenode()
function. To verify that we can correctly remove multiple nodes, we
then remove the “Kailey” node that we found earlier in this loop
and once again print out the number of nodes in the list to the
screen.
Finally we delete the list using the
deletelist()
function and once again print out the number of nodes in the list to
verify that they were all removed.
I hope this post helps you understand linked lists a little
better.
