Linked List in C - Sanfoundry

This C Tutorial explains Linked List in C with examples.

Though we are already familiar with structure pattern and about different ways we can access their members, we consider it once more for better understanding of Linked lists. For example:

typedef struct NODE {
                     /* link is a ptr to type struct NODE */
                     struct NODE *link; 
                     int data;
    } Node;     /* Node new type for above structure pattern */

Note that we have also given above structure design a tag name called NODE and included, as its member, link, a pointer to struct NODE i.e. link is a pointer to structure of type struct NODE of which link is one of its members. Such a structure is called self-referential structure.

Type of link field is struct NODE therefore we can create a list of such self-referential structures connected through links. Each independent structure in the list is called a node. The node that begins the list is called root node and which ends the list has set its link field to point to nowhere. Let’s consider a simple C program that creates a Singly Linked List,

/* create_sll.c -- program creates a singly linked list */
#include <stdio.h>
#include <stdlib.h>
 
/* symbolic constants declared */
#define INSERT 1
#define QUIT   2
 
/* structure declaration */
typedef struct  NODE {
                      struct NODE *link;
                      int value;
        } Node;
 
void insert_sll(Node **, const int);
 
int main(void)
{
    Node *root = 0;         /* root is set to NULL */
    Node **p2r = &root;     /* pointer-to-root */
    int value;
    int op;
 
    puts("\n**Let's create a Singly Linked List**\n");
    printf("User, enter 1 for INSERT and 2 for QUIT : ");
    while (1) {
        while (scanf("%d", &op) == 1 && (op == INSERT || op == QUIT )) {
 
            if (op == INSERT) {
                printf("User, enter an integer value: ");
                scanf("%d", &value);
                insert_sll(p2r, value);
            }
            else if (op == QUIT) {
                printf("Thank You!\n");
                return 0;
            }
 
            printf("\nWant to insert more integer values,\nenter 1 "
                   "for INSERT, else 2 for QUIT : ");
        }
            puts("Entered is a WRONG choice, enter 1 "
                 "for INSERT, 2 for QUIT");
    }
}
 
void insert_sll(Node **linkp, const int value)
{
    Node *current = 0;
    Node *newnode = 0;
 
    /* Let's create an ordered singly linked list */
    /* firstly, ensure if value isn't already in the list */
    /* if value is already in the list, we won't add duplicate */
    while ((current = *linkp) != NULL && current->value < value)
        linkp = &current->link;
 
    /* if value is already in the list */
    if (current != NULL && current->value == value) {
        printf("\n\aValue %d is already in the list.\n", value);
        return ;
    }
 
    /* value isn't already in the list */
    /* Let's allocate memory to newnode */
    newnode = (Node *)malloc(sizeof(Node));
 
    /* If memory allocated to newnode successfully */
    if (newnode == NULL) {
        printf("Not sufficient Memory!\n");
      exit(EXIT_FAILURE);
    }
    /* write in value in value field of newnode */
    newnode->value = value;
 
    /* insert newnode in the list */
    /* between current and previous */
    newnode->link = current;
    *linkp = newnode;
}

Output of above program for some arbitrary choices,

Note: Join free Sanfoundry classes at Telegram or Youtube

 
**Let's create a Singly Linked List**
 
User, enter 1 for INSERT and 2 for QUIT : 1
User, enter an integer value: 23
 
Want to insert more integer values,
enter 1 for INSERT, else 2 for QUIT : 1
User, enter an integer value: 34
 
Want to insert more integer values,
enter 1 for INSERT, else 2 for QUIT : 4
 
Entered is a WRONG choice,
enter 1 for INSERT, 2 for QUIT : 1
User, enter an integer value: 12
 
Want to insert more integer values,
enter 1 for INSERT, else 2 for QUIT : 1
User, enter an integer value: 12
 
Value 12 is already in the list.
 
Want to insert more integer values,
enter 1 for INSERT, else 2 for QUIT : 2
 
Thank You!

Notice that program creates an ordered singly linked list with values inserted by the user. No duplicate values can be inserted in the list.