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 = ¤t->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.
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,
**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.
Sanfoundry Global Education & Learning Series – 1000 C Tutorials.
- Get Free Certificate of Merit in C Programming
- Participate in C Programming Certification Contest
- Become a Top Ranker in C Programming
- Take C Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Practice BCA MCQs
- Practice Computer Science MCQs
- Buy C Books
- Buy Computer Science Books
- Apply for C Internship