Single Linked List in C [part 1]

This tutorial assumes a basic knowledge of the C language and pointers. If you are not comfortable with this please refer to the basics of the C programming language and Memory Management.

Introduction

Linked lists are very useful when storing a group of data and accessing them linearly when needed. The naming is mainly because of the way the data is linked together, each “node” knows about the “next” node, it also can carry
it’s own properties. Imagine having a students in a classroom and wanting to have their name and age or a simple list of songs that needs to be played in order.
The whole program is available for a download here.

Simple linked list implementation

We will start by including the following standard libraries which allows us to use printf(), malloc() and strncpy().
[code language=”c”]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
[/code]
Next, let’s define our data structure, in our case we chose to have a single linked list of students
[code language=”c”]
/* Basic student definition */
typedef struct Student {
unsigned int age;
char name[20];
struct Student *next;
} Student;
[/code]
We also need to store the “head” and the “tail”, those are respectively the First and Last elements in our set of data.
[code language=”c”]
/* points to the first Student */
static Student *head = NULL;
/* points to the last Student */
static Student *tail = NULL;
[/code]
The main function which is responsible of dynamically creating a new Student data and linking to the previous known data.
[code language=”c”]
/* Create a new Student and attach to the last one. */
Student *insert(int age, char *name){
if(!head){
/*
* We do not have any Student created yet
*/
head = (Student *)malloc(sizeof(Student));
head->age = age;
strncpy(head->name, name, 20);
head->next = NULL;
/* at this stage the First and Last element are the same */
tail = head;
}else{
/*
* We already have a Student, link it
*/
tail->next = (Student *)malloc(sizeof(Student));
tail->next->age = age;
strncpy(tail->next->name, name, 20);
tail->next->next = NULL;
/* Last element is the newly created element */
tail = tail->next;
}
return tail;
}
[/code]
Now the main part of the program, simply creating three new Students and showing them. As you can see the “head” and “tail” are respectively the first and last elements of our linked data set.
[code language=”c”]
int main(int argc, char **argv){
/* Insert three elements */
insert(24, "John Doe");
insert(22, "Jean Luc");
insert(31, "Alex Rim");
/* Start with the first element and loop till we reach a dead end. */
Student *s = head;
while(s != NULL){
printf("Student: %s, Age:%drn", s->name, s->age);
s = s->next;
}
printf("rn");
printf("First Student: %s, Age:%drn", head->name, head->age);
printf("Last Student: %s, Age:%drn", tail->name, tail->age);
return 0;
}
[/code]
Executing the following program will output the following:
[code language=”bash”]
Student: John Doe, Age:24
Student: Jean Luc, Age:22
Student: Alex Rim, Age:31
First Student: John Doe, Age:24
Last Student: Alex Rim, Age:31
[/code]
In part 2 we will be discussing how to improve the linked lists in order to make them double linked, that is having previous/next element implementation and also possibility to delete an item from the list.
Stay tuned!