Ordered and Unordered Singly Linked Lists in C

This C Tutorial explains Ordered and Unordered Singly Linked Lists in C.

A singly linked list in which values are inserted in either ascending or descending order is called an ordered singly linked list. An unordered singly linked list doesn’t have such limitation. Let’s, first, consider an example of ordered singly linked list,

/* create_sll.c -- program creates an ordered singly linked list */
#include <stdio.h>
#include <stdlib.h>
 
/* symbolic constants declared */
#define TRAVERSE 1
#define INSERT 2
#define QUIT   3
 
/* structure declaration */
typedef struct  NODE {
                      struct NODE *link;
                      int value;
        } Node;
 
void insert_sll(Node **, const int);
void traverse_sll(Node **);
 
int main(void)
{
    Node *root = 0;         /* root is 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 TRAVERSE, 2 FOR INSERT and 3 for QUIT : ");
    while (1) {
        while (scanf("%d", &op) == 1 &&
               (op == INSERT || op == QUIT || op == TRAVERSE)) {
 
            if (op == TRAVERSE) {
                traverse_sll(p2r);
            }
            else if (op == INSERT) {
                printf("User, enter an integer value: ");
                scanf("%d", &value);
                insert_sll(p2r, value);
            }
            else if (op == QUIT) {
                printf("\nThank You!\n");
                return 0;
            }
 
            printf("\nWant to do some more operations,\nenter 1 "
                   "for TRAVERSE, 2 for INSERT and 3 for QUIT : ");
        }
            printf("\n\aEntered is a WRONG choice,\nenter 1 "
                   "for TRAVERSE, 2 for INSERT, 3 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 newnde */
    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;
}
 
void traverse_sll(Node **linkp)
{
    Node *current = *linkp;
 
    /* traverse the list */
    if (current == NULL) {
        printf("\nList is EMPTY.\n");
    }
    else {
        printf("\nList contains values : ");
        while (current != NULL) {
            printf("%d ", current->value);
            current = current->link;
       }
        printf("\n");
    }
}

Output of above program for some arbitrary choices as,

 
**Let's create a Singly Linked List**
 
User, enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 1
 
List is EMPTY.
 
Want to do some more operations,
enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 2
User, enter an integer value: 34
 
Want to do some more operations,
enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 2
User, enter an integer value: -098
 
Want to do some more operations,
enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 2
User, enter an integer value: 12
 
Want to do some more operations,
enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 2
User, enter an integer value: -15
 
Want to do some more operations,
enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 1
 
List contains values : -98 -15 12 34
 
Want to do some more operations,
enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 3
Thank You!

Notice that above program creates an ordered singly linked list with inserted values set in ascending order. In addition, no value can be inserted in duplicate. Actually, program walks down the list to find appropriate place to insert the new value if the same isn’t already in the list.

advertisement
advertisement

Well! In order to create an unordered singly linked list we can modify insert_sll() slightly to create unordered singly linked list. In unordered list we shall insert new value at the end of the list. Let’s modify insert_sll() function and incorporate the same in place of already defined insert_sll() in the program to create an unordered list,

void insert_sll(Node **linkp, const int value)
{
    Node *newnode = 0;
 
    /* Let's create an unordered singly linked list */
    /* insert new value at the end of list */
    while (*linkp != NULL)
        linkp = &(*linkp)->link;
 
    /* Let's allocate memory to newnde */
    newnode = (Node *)malloc(sizeof(Node));
 
    /* verify 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 */
    /* at the end of the list */
    *linkp = newnode;
    newnode->link = NULL;
}

With slight modification to the following statement

    puts("\n**Let's create a Singly Linked List**\n");

which now looked like as

    puts("\n**Let's create an Unordered Singly Linked List**\n");

and insert_sll() of the previous program which produced ordered singly linked list now have been replaced with the modified insert_sll() function and run the program with arbitrary choices, output turns out as,

advertisement
 
**Let's create an Unordered Singly Linked List**
 
User, enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 1
 
List is EMPTY.
 
Want to do some more operations,
enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 2
User, enter an integer value: 23
 
Want to do some more operations,
enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 2
User, enter an integer value: -9
 
Want to do some more operations,
enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 2
User, enter an integer value: 143
 
Want to do some more operations,
enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 7
 
Entered is a WRONG choice,
enter 1 for TRAVERSE, 2 for INSERT, 3 for QUIT : 1
 
List contains values : 23 -9 143
 
Want to do some more operations,
enter 1 for TRAVERSE, 2 for INSERT and 3 for QUIT : 3
 
Thank You!

So, what you observed? New values inserted in the end of list. And values aren’t in order. So, singly list is unordered.

advertisement

Sanfoundry Global Education & Learning Series – 1000 C Tutorials.

If you wish to look at all C Tutorials, go to C Tutorials.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.