Before starting to implement linked list in C, let’s see what self-referential structures are. Also, you need to know about dynamic memory allocation, which you can find here in this link. For example, let’s define a structure like below:
struct node {
int data;
struct node *nextPtr;
}; // end struct node
In the above struct node, we have two members, viz. integer member data and pointer member nextPtr. Also, the pointer points to same type struct node, hence the name self-referential structure. Moreover, it is also called a link.
Linked List in C
A linked list is a linear collection of self-referential structures, called nodes, connected by pointer links. That is why, the term ’linked’ list. We can access a linked list via a pointer to the first node of the list. On the other hand, we access the subsequent nodes via the link pointer member which we store in each node. Finally, by convention, we set the link pointer in the last node to NULL to mark the end of the list. Also, we store the data dynamically in a linked list. Furthermore, a node can contain data of any type including other structs.
Implementation Example
Now, we are going to implement linked list in C, which stores a character in an alphabetical order.
#include <stdio.h>
#include <stdlib.h>
// Self-referential Structure
struct listNode {
char data; // A character data in the list
struct listNode *nextPtr; // Pointer to next node
}; // end struct listNode
typedef struct listNode ListNode; // alias for the struct
typedef ListNode *ListNodePtr; // alias for ListNode*
// Declarations
void insert(ListNodePtr *sPtr, char value);
char delete(ListNodePtr *sPtr, char value);
int isEmpty(ListNodePtr sptr); // Memory!
void showList(ListNodePtr currentPtr);
void showMenu(void);
int main() {
// Initially, there are no nodes
ListNodePtr startPtr = NULL;
// User's choice
unsigned int ch;
// User's entered character
char item;
// Display the menu
showMenu();
printf("? ");
scanf("%u", &ch);
// Loop unless user chooses 3
while(ch != 3) {
switch(ch) {
case 1:
printf("Enter a character: ");
scanf("\n%c", &item);
// insert the item in list
insert(&startPtr, item);
showList(startPtr);
break;
case 2:
// if list is not empty
if(!isEmpty(startPtr)) {
printf("Enter character to be deleted: ");
scanf("\n%c", &item);
// Remove the character if found
if (delete(&startPtr, item)) {
printf("%c deleted.\n", item);
showList(startPtr);
}
else {
printf("%c not found. \n\n", item);
}
}
else {
printf("The list is empty. \n");
}
break;
default:
printf("Invalid choice.\n");
showMenu();
break;
}
showMenu();
printf("? ");
scanf("%u", &ch);
}
printf("Thank You!\n");
return 0;
}
// Display Menu Function
void showMenu(void) {
printf("Enter your choice:\n"
" 1 to insert element into the list.\n"
" 2 to delete element from the list.\n"
" 3 to end" );
}
// insert a new value into the list in sorted order
void insert(ListNodePtr *sPtr, char value) {
ListNodePtr newPtr; // pointer to new node
ListNodePtr previousPtr; // pointer to previous node
ListNodePtr currentPtr; // pointer to current node
newPtr = malloc(sizeof(ListNode)); // Create a node
// if allocated
if (newPtr != NULL) {
newPtr->data = value; // put value in the node
newPtr->nextPtr = NULL; // doesn't have to link to another node
previousPtr = NULL;
currentPtr = *sPtr;
// find the correct location in the list
while(currentPtr != NULL && value > currentPtr->data) {
previousPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
}
// insert new node at beginning of list
if (previousPtr == NULL) {
newPtr->nextPtr = *sPtr;
*sPtr = newPtr;
}
else {
previousPtr->nextPtr = newPtr;
newPtr->nextPtr = currentPtr;
}
}
else {
printf("%c is not inserted. \n", value);
}
}
// delete a list element
char delete(ListNodePtr *sPtr, char value) {
ListNodePtr previousPtr;
ListNodePtr currentPtr;
ListNodePtr tmpPtr;
// delete first node
if (value == (*sPtr)->data) {
tmpPtr = *sPtr; // hold onto node being removed
*sPtr = (*sPtr)->nextPtr; // de-thread the node
free(tmpPtr); // free the de-threaded node
return value;
}
else {
previousPtr = *sPtr;
currentPtr = (*sPtr)->nextPtr;
// find the correct location in the list
while (currentPtr != NULL && currentPtr->data != value) {
previousPtr = currentPtr;
currentPtr = currentPtr->nextPtr;
}
// delete node at currentPtr
if (currentPtr != NULL) {
tmpPtr = currentPtr;
previousPtr->nextPtr = currentPtr->nextPtr;
free(tmpPtr);
return value;
}
}
return '\0'; // NULL
}
// return 1 if the list is empty, otherwise 0
int isEmpty(ListNodePtr sPtr) {
return sPtr == NULL;
}
// show the list
void showList(ListNodePtr currentPtr) {
// if list is empty
if (isEmpty(currentPtr)) {
printf("The list is empty!\n");
}
else {
printf("The list is: \n");
// while not the end of list
while(currentPtr != NULL) {
printf("%c ==> ", currentPtr->data);
currentPtr = currentPtr->nextPtr;
}
printf("NULL\n");
}
}
In the above example, we saw how we can perform insert and delete operations in linked list. It is all explained in the comments in the program. In a nutshell, you have to create a new node and point to its address from previous node. On the other hand, while deleting, you have to delete the node and set the nextPtr of previous node to NULL.
You can view the the code in the gist here.