01 Explain Linked List in C with Examples
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 = ¤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.
Top

02 What is Dynamic and Static Memory Allocation in C and How this Occurs in Context with Linked Lists
Question: What is Dynamic and Static Memory Allocation in C and How this Occurs in Context with Linked Lists?
Answer: Static memory allocation is a compile time constant i.e. memory is allocated during compilation of the program. For example,

int main(void)
{
int fours[10]; /* fours is an array of 10 integers */
char symbols[128]; /* symbols an array of 128 characters */

return 0;
}
When above program is compiled, fours is allocated (10 * sizeof(int)) bytes, symbols is allocated 128 bytes. Here memory is allocated during compile time. We call this static allocation because memory is allocated once at the compile time and we can’t request for reallocation if need arises. Further, we can’t free up memory once we are done with this. Memory allocated statically frees up only when program exits.

There are situations where we are not sure of exact amount of memory we require until run time, during the entire execution of program. For example, to keep record of foreigners visiting to India every year. In such situations, if we allocate memory statically presuming some maximum number, there might be wastage of memory if far fewer people visited the country in a particular year as well as there’s always a possibility to overflow.

What here we require is some scheme to allocate memory as per ours’ need. For example, if we need to find average of marks of all students of all classes. Students might count differently in different classes. In such situations, we require dynamic memory allocation.

In systems, functions malloc() and free() maintain pool of available memory. When, memory, in bytes, is requested, malloc() attempts to allocate memory from this pool. If enough memory is not there, malloc() requests O.S. to allocate. O.S. tries to free up memory and returns the same to the pool, but if O.S., too, fails, malloc() returns NULL. For example,

/* create_sll.c -- program creates a singly linked list */
#include <stdio.h>
#include <stdlib.h>

#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 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 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;
}

Notice that in above program, we allocate memory to newnode when a new value is required to be inserted in the list. Since, we, in advance, are not sure of how big the List is i.e. how many values might comprise the list, we, therefore, dynamically allocate memory as and when needs. NULL is a visual representation for Null Pointer. Internally, It’s 0, zero. Though, program doesn’t include code fragment to delete a value from the list, we can, however, write a function to delete a particular value from the list, and back the freed up memory to the pool of available memory. The advantage of dynamic allocation.

Top

03 What is a Singly Linked List in C Language
This C Tutorial explains Singly Linked List in C Language.
A linked list that can only be traversed in forward direction is called a singly linked list. A singly linked list is traversed from beginning through till end using the root pointer. root contains the address of start of list. Let’s, for example, create a singly linked list and traverse it,

/* create_sll.c -- program creates a singly linked list */
#include <stdio.h>
#include <stdlib.h>

#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("naEntered 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("naValue %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");
}
}

Above program creates a Singly Linked List with user specified values. We can traverse this list in forward direction as root points to the beginning of the list and last node contains NULL in the link field which means there’s no more nodes in the list. Further, we can’t get back to a node we already traversed because we don’t have a pointer to it. The only way we can get back to any previous node is to traverse the list from the start or save pointers to desired nodes.

Top

04 What are 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 = ¤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.

Top

05 What are Different Operations Performed on a Singly Linked List in C Programming
This C Tutorial explains Different Operations Performed on a Singly Linked List in C Programming.
Let’s see an example of a C program that creates a singly linked list and performs various operations on it.

/* sll.c -- a realistic approach */
#include <stdio.h>
#include <stdlib.h>

/* Symbolic constants declared */
#define T 1
#define I 2
#define S 3
#define D 4
#define Q 5
#define TRAVERSE "enter 1 to TRAVERSE the list..."
#define INSERT "enter 2 to INSERT new value in the list..."
#define SEARCH "enter 3 to SEARCH a value in the list..."
#define DELETE "enter 4 to DELETE a value from the list..."
#define QUIT "enter 5 to QUIT the program..."

typedef struct NODE {
struct NODE *link;
int value;
} Node;

/* function declarations */
int traverse(Node **);
void insert(Node **, const int);
int search(Node **, const int);
int delete(Node **, const int);

int main(void)
{
Node *root = 0;
Node **p2r = &root;
Node *found = 0;
int op = 0;
int value = 0;

printf("\n**Program Shows different operations on Singly "
"Linked List.**\n");
printf("\nUser, what operation do you want to do, now?\n\n");
printf("%s\n%s\n%s\n%s\n%s\n: ",
TRAVERSE, INSERT, SEARCH, DELETE, QUIT);
while (1) {
while (scanf("%d", &op) == 1) {
if (op == T) {
op = traverse(p2r);
}

if (op == I) {
printf("User, enter integer value you want to "
"insert: ");
scanf("%d", &value);
insert(p2r, value);
}

if (op == S) {
printf("User, enter an integer value you wish to "
"search in the list...: ");
scanf("%d", &value);
op = search(p2r, value);

if (op == I) {
printf("User, enter integer value you want to "
"insert: ");
scanf("%d", &value);
insert(p2r, value);
}
}

if (op == D) {
printf("User, enter a value you wish to delete: ");
scanf("%d", &value);
op = delete(p2r, value);

if (op == I) {
printf("User, enter integer value you want to "
"insert: ");
scanf("%d", &value);
insert(p2r, value);
}
}

if (op == 5) {
printf("Thank You!\n");
return 0;
}

printf("\nUser, what operation do you want now?\n\n");
printf("%s\n%s\n%s\n%s\n%s\n: ",
TRAVERSE, INSERT, SEARCH, DELETE, QUIT);

}
}
}

void insert(Node **linkp, const int value)
{
Node *current;
Node *new;

while (((current = *linkp) != NULL) && (current->value < value))
linkp = ¤t->link;

/* firstly we verify if value is already in the list */
if (current != NULL) {
if (current->value == value) {
printf("Value %d is already in the list!\n", value);
printf("So, we don't INSERT value.\n");
return ;
}
}

/* Value isn't already in the list */
/* Let's allocate it in proper place in the list */
/* Allocate space to new */
new = (Node *)malloc(sizeof(Node));

/* Verify if allocation successful */
if (new == NULL) {
printf("Error: Memory Allocation Failed!\n");
exit(EXIT_FAILURE);
}

/* write in value in the new */
new->value = value;

/* Insert value in the list */
*linkp = new;
new->link = current;
printf("Value %d inserted successfully!\n", value);
}

int traverse(Node **linkp)
{
Node *current = *linkp;
int op = 0;

/* Let's verify if list is Empty */
if (current == NULL) {
printf("\nList is EMPTY.\n");
printf("So, you can either enter a value in the list or ");
printf("QUIT the program.\nEnter 2 to INSERT value in the list, "
"or enter 5 to QUIT.: ");
while (scanf("%d", &op) == 1 && (op != I && op != Q))
printf("Entered value is INCORRECT, enter CORRECT value: ");

return op;
}
/* List isn't EMPTY, Traversing the list */
else {
printf("\nList is as follows: ");
while (current != NULL) {
printf("%d ,", current->value);
current = current->link;
}
puts("\n");
return op;
}
}
int delete(Node **linkp, const int value)
{
Node *current = *linkp;
int op = 0;

/* let's see if list is empty */
if (current == NULL) {
printf("List is empty.\n");
printf("User, you can either enter an integer value or "
"you can quit the program.\n");
printf("Enter 2 to INSERT a value and enter 5 to QUIT the "
"program: ");
while (scanf("%d", &op) == 1 && (op != I && op != Q))
printf("You entered WRONG value! Please try again.\n");

return op;
}
else {
/*
* List isn't empty. We search through the entire list for
* desired value and once found, we'll delete the node
* containing the value
*/
while ((current = *linkp) != NULL && current->value != value)
linkp = ¤t->link;

/* now there are 2 cases, Either we've reached the end of list */
if (current == NULL) {
printf("We have reached the end of the List.\n");
printf("Value %d is NOT in the list.\n", value);
return op;
}
else if (current->value == value) {
printf("We have found value %d in the List.", value);
/*we delete the specified value from the list */
/* now we free up memory allocated to that node */
*linkp = current->link;
printf(" And deleted the value!\n");
/* set link field of previous node to point to
node current->link points to */
free(current);
/* free up current node back to free pool of memory */
return op;
}
}
}

int search(Node **linkp, const int value)
{
Node *current = *linkp;
int op = 0;

/* Let's verify if list is Empty */
if (current == NULL) {
printf("\nList is EMPTY.\n");
printf("So, you can either enter a value in the list or ");
printf("QUIT the program.\nEnter 2 to INSERT value in the list, "
"or enter 5 to QUIT.: ");
while (scanf("%d", &op) == 1 && (op != I && op != Q))
printf("Entered value is INCORRECT, enter CORRECT value: ");

return op;
}
/* List isn't EMPTY, Searching value in the list */
else {
while ((current != NULL) && current->value != value)
current = current->link;

if (current == NULL) { /* reached end of list */
printf(" %d is NOT in the list.\n", value);
return op;
}
else {
printf("%d is FOUND in the list.\n", value);
return op;
}
}
}

Output of the above program for arbitrary choices is as follows,


**Program Shows different operations on Singly Linked List.**

User, what operation do you want to do, now?

enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 1

List is EMPTY.
So, you can either enter a value in the list or QUIT the program.
Enter 2 to INSERT value in the list, or enter 5 to QUIT.: 2
User, enter integer value you want to insert: 65
Value 65 inserted successfully!

User, what operation do you want now?

enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 2
User, enter integer value you want to insert: -87
Value -87 inserted successfully!

User, what operation do you want now?

enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 1

List is as follows: -87 ,65 ,


User, what operation do you want now?

enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 3
User, enter an integer value you wish to search in the list...: 55
55 is NOT in the list.

User, what operation do you want now?

enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 3
User, enter an integer value you wish to search in the list...: 65
65 is FOUND in the list.

User, what operation do you want now?

enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 4
User, enter a value you wish to delete: 55
We have reached the end of the List.
Value 55 is NOT in the list.

User, what operation do you want now?

enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 4
User, enter a value you wish to delete: 65
We have found value 65 in the List. And deleted the value!

User, what operation do you want now?

enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 1

List is as follows: -87 ,


User, what operation do you want now?

enter 1 to TRAVERSE the list...
enter 2 to INSERT new value in the list...
enter 3 to SEARCH a value in the list...
enter 4 to DELETE a value from the list...
enter 5 to QUIT the program...
: 5
Thank You!
Notice various operations performed on Ordered Singly Linked List. Further, you can try writing all declarations in yours own header with .h extension and functions’ definitions in a separate file with .c extension to allow other programs to share those functions.


Top

06 What is a Doubly Linked List in C
This C Tutorial explains a Doubly Linked List in C language.
A singly liked list can be traversed in one and in Forward Direction only while doubly linked list in either Forward or Backward direction. For this either way traversal, each node contains two pointer fields. We consider, for example, declaration of a node,

typedef struct NODE {
struct NODE *fwd;
struct NODE *bwd;
int value;
} Node;
/* Node is user defined type for above structure template */

fwd pointer of each node, except last node in which it’s NULL, points to next node in the list while bwd pointer of each node, except first node in which it’s NULL, points to previous node in the list. But how list begins? There’s a root node of which fwd pointer field begins the list in Forward diection while bwd pointer field begins the list in backward direction.

Let’s see declaration for root node,

int main(void)
{
Node root; /* root node declared */

/* fwd and bwd fields of root node are set to NULL */
root.fwd = 0;
root.bwd = 0;

}
Instead of declaraing a root node, here for ex. it also contains an integer “value” which wastes memory, we could have used two separate pointers each of type Node *. Since we write dedicated functions to perform different operations on the list and then we would have required to pass two pointers to functions. To simplify the task we better declare single root node with two pointer fields and use it’s value field for stroing other list related information, for ex. no. of nodes in the list, etc.
This way you are required to pass pointer to root to different functions for different operations on the list.


Top

07 What are Different Operations that Can be Performed on a Doubly Linked List in C
This C Tutorial explains Different Operations that Can be Performed on a Doubly Linked List in C.
We have following C program which implements a doubly linked list and performs various operations on it.

/* dll.c -- a realistic approach */
#include <stdio.h>
#include <stdlib.h>

#define T 1 /* TRAVERSE */
#define I 2 /* INSERT */
#define S 3 /* SEARCH */
#define D 4 /* DELETE */
#define Q 5 /* QUIT */
#define TRAVERSE "enter 1 to TRAVERSE the list..."
#define INSERT "enter 2 to INSERT new value in the list..."
#define SEARCH "enter 3 to SEARCH a value in the list..."
#define DELETE "enter 4 to DELETE a value from the list..."
#define QUIT "enter 5 to QUIT the program..."
#define FORWARD 6
#define BACKWARD 7

typedef struct NODE {
struct NODE *fwd;
struct NODE *bwd;
int value;
} Node;

/* function declarations */
int ftraverse(Node *);
int btraverse(Node *);
void insert(Node *, const int);
int search(Node *, const int);
int delete(Node *, const int);

int main(void)
{
Node root; /* root is a Node, not a pointer to Node */
int op = 0;
int value = 0;
int fbchoice = 0; /* FORWARD BACKWARD Choice */

/* fwd and bwd fields of root set to NULL */
root.fwd = 0;
root.bwd = 0;

printf("n**Program Shows different operations on Doubly Linked "
"List.**n");
printf("nUser, what operation do you want to do, now?nn");
printf("%sn%sn%sn%sn%sn: ",
TRAVERSE, INSERT, SEARCH, DELETE, QUIT);
while (1) {
while (scanf("%d", &op) == 1) {
if (op == T) {
printf("Whether in Forward or Backward Direction,n");
printf("For FORWARD, enter 6, for BACKWARD, "
"enter 7,: ");
scanf("%d", &fbchoice);

if (fbchoice == FORWARD)
op = ftraverse(&root);
else if (fbchoice == BACKWARD)
op = btraverse(&root);
}

if (op == I) {
printf("User, enter integer value you want to "
"insert: ");
scanf("%d", &value);
insert(&root, value);
}

if (op == S) {
printf("User, enter an integer value you wish to "
"search in the list...: ");
scanf("%d", &value);
op = search(&root, value);

if (op == I) {
printf("User, enter integer value you want to "
"insert: ");
scanf("%d", &value);
insert(&root, value);
}
}

if (op == D) {
printf("User, enter a value you wish to delete: ");
scanf("%d", &value);
op = delete(&root, value);

if (op == I) {
printf("User, enter integer value you want to "
"insert: ");
scanf("%d", &value);
insert(&root, value);
}
}
if (op == 5) {
printf("Thank You!n");
return 0;
}

printf("nUser, what operation do you want now?nn");
printf("%sn%sn%sn%sn%sn: ",
TRAVERSE, INSERT, SEARCH, DELETE, QUIT);

}
}
}

void insert(register Node *p2r, const int value)
{
register Node *this = p2r;
register Node *next;
register Node *newnode;

/* Let's confirn if value is already in the list */
while ((next = this->fwd) != NULL) {
if (next->value == value) {
printf("Value %d is already in the list!n");
return ;
}
/* I ensure each value is inserted once */
if (next->value > value)
break;

this = next;
}

/* Value isn't already in the list */
/* Let's allocate it in proper place in the list */
/* Allocate space to newnode */
newnode = (Node *)malloc(sizeof(Node));

/* Verify if allocation successful */
if (newnode == NULL) {
printf("Error: Memory Allocation Failed!n");
exit(EXIT_FAILURE);
}

/* write in value in the newnode */
newnode->value = value;

/* Insert value in the list */
/*
* four pointer fields in this, newnode and next required
* to be adjusted
*/
newnode->fwd = next;
this->fwd = newnode;

if (this != p2r)
newnode->bwd = this;
else
newnode->bwd = NULL;

if (next != NULL)
next->bwd = newnode;
else
p2r->bwd = newnode;

printf("Value %d inserted successfully!n", value);
}

int ftraverse(register Node *p2r)
{
register Node *this = p2r->fwd;
int op = 0;

/* Let's verify if list is Empty */
if (this == NULL) {
printf("nList is EMPTY.n");
printf("So, you can either enter a value in the list or ");
printf("QUIT the program.nEnter 2 to INSERT value in the list, "
"or enter 5 to QUIT.: ");
while (scanf("%d", &op) == 1 && (op != I && op != Q))
printf("Entered value is INCORRECT, enter CORRECT "
"value...: ");

return op;
}
/* List isn't EMPTY, Traversing the list in FORWARD direction */
else {
printf("nList is as follows: ");
while (this != NULL) {
printf("%d ,", this->value);
this = this->fwd;
}
puts("n");
return op;
}
}

int btraverse(register Node *p2r)
{
register Node *this = p2r->bwd;
int op = 0;

/* Let's verify if list is Empty */
if (this == NULL) {
printf("nList is EMPTY.n");
printf("So, you can either enter a value in the list or ");
printf("QUIT the program.nEnter 2 to INSERT value in the list, "
"or enter 5 to QUIT.: ");
while (scanf("%d", &op) == 1 && (op != I && op != Q))
printf("Entered value is INCORRECT, enter CORRECT value: ");


return op;
}
/* List isn't EMPTY, Traversing the list in Backward direction */
else {
printf("nList is as follows: ");
while (this != NULL) {
printf("%d ,", this->value);
this = this->bwd;
}
puts("n");
return op;
}
}

int delete(register Node *p2r, const int value)
{
register Node *current = p2r;
register Node *next;
register Node *dnode;
int op = 0;

/* let's see if list is empty */
if (current->fwd == NULL) {
printf("List is empty.n");
printf("User, you can either enter an integer value or you can "
"quit the program.n");
printf("Enter 2 to INSERT a value and enter 5 to QUIT the "
"program: ");
while (scanf("%d", &op) == 1 && (op != I && op != Q))
printf("You entered WRONG value! Please try again.n");

return op;
}
else {
/*
* List isn't empty. We search through the entire list for
* desired value and once found, we'll delete the node containing
* the value
*/
while ((dnode = current->fwd) != NULL && dnode->value != value)
current = dnode; /* update the current node */

/* now there are 2 cases, Either we've reached the end of list */
if (dnode == NULL) {
printf("We have reached the end of the List.n");
printf("Value %d is NOT in the list.n", value);
return op;
}
else if (dnode->value == value) {
printf("We have found value %d in the List.", value);
/*
* set current->fwd to node following node to be
* deleted
*/
current->fwd = dnode->fwd;

/*
* now set bwd pointer field of node following the
* deleting value
*/
next = dnode->fwd;
if (next == NULL) {
/* reached end of list */
/*
* set bwd field of root node to preceding node
* of deleting node
*/
p2r->bwd = dnode->bwd;
}
else {
/* else where in the list */
next->bwd = dnode->bwd;
}

printf(" And deleted the value!n");
/* now free up the dnode */
free(dnode);
return op;
}
}
}

int search(register Node *p2r, const int value)
{
register Node *this = p2r->fwd;
int op = 0;

/* Let's verify if list is Empty */
if (this == NULL) {
printf("nList is EMPTY.n");
printf("So, you can either enter a value in the list or ");
printf("QUIT the program.nEnter 2 to INSERT value in the list, "
"or enter 5 to QUIT.: ");
while (scanf("%d", &op) == 1 && (op != I && op != Q))
printf("Entered value is INCORRECT, enter CORRECT value: ");

return op;
}
/* List isn't EMPTY, Searching value in the list */
else {
while ((this != NULL) && this->value != value)
this = this->fwd;

if (this == NULL) { /* reached end of list */
printf(" %d is NOT in the list.n", value);
return op;
}
else {
printf("%d is FOUND in the list.n", value);
return op;
}
}
}


Top