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 = ¤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 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,
**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.
Sanfoundry Global Education & Learning Series – 1000 C Tutorials.
