- C Programming Basics
- C Tutorial
- C Program Structure
- C Basic Syntax
- C Data Types
- C Constants
- C Variables
- C Operators
- C Ternary Operator
- C Storage Classes
- C Flow of Control
- C Decision Making
- C if if-else Statement
- C switch Statement
- C Loops
- C for Loop
- C while Loop
- C do-while Loop
- C goto Statement
- C break Statement
- C continue Statement
- C Popular Topics
- C Arrays
- C Strings
- C Pointers
- C Functions
- C Recursion
- C Scope Rules
- C Programming Advance
- C Structures
- C Unions
- C Bit Fields
- C Enumerations
- C Input & Output
- C Typedef
- C Preprocessors
- C Type Casting
- C Recursion
- C Error Handling
- C Linked Lists
- C Stacks
- C Queues
- C Binary Trees
- C Header Files
- C File I/O
- C Variable Arguments
- C Memory Management
- C Command Line Arguments
- C Programming Examples
- C Programming Examples
- C Programming Library
- C Standard Library
- C Programming Test
- C Programming Test
- Give Online Test
- All Test List
C Linked Lists
Unlike stack or queue, a linked list can be accessed in a flexible manner, because each piece of information carries with it a link to the next data item in the chain. In addition, a linked list retrieval operation doesn't remove and destroyed an item from the list. In fact, you need to add a specific deletion operation to do this.
Linked list can be either singly or doubly linked. A singly linked list contains a link to the next data item. On the other hand, a doubly linked list contains the links to both next and previous element in the list. You will use one or the other of these linked list types, depending upon your application. Now let's discuss about singly linked lists.
Singly Linked Lists
A singly linked list requires that each item of information contain a link to the next element in list. Each data item generally consists of a structure which includes the information fields and a link pointer. Let's take a look at the following figure which represents a singly linked lists.

Basically, there are two ways to build a singly linked list. The first is simply to put each new item on the end of list. The other is to insert items into specific places in the list in ascending sorted order.
The items stored in a linked list generally consist of structures because each item must carry with it a link to the next item in the list as well as the data itself. Hence, we will need to define a structure that will be used in examples that follow. Since mailing lists are commonly stored in a linked list, an address structure makes a good choice. The data structure for each element in the mailing list is defined here:
struct address { char name[30]; char street[40]; char city[25]; char state[4]; char zip[11]; struct address *next; // link to the next address }info;
The function slstore() shows here builds a singly linked list by placing each new element on the end. And it must be passed a pointer to a structure of type address which contains the new entry, and a pointer to the last element in the list. In case, if the list is emply, then the pointer to the last element in the list must be null. Here is the code fragment of slstore() function:
void slstore(struct address *i, struct address **last) { if(!*last) *last = i; // first item in the list else (*last)->next = i; i->next = NULL; *last = i; }
Doubly Linked Lists
The doubly linked lists consist of data plus links to the next item as well as the preceding item. Let's take a look at the following figure which represents a doubly linked lists.

Having the two links rather of one has several advantages. Perhaps the most important is that the list can be read in either direction. This simplifies the list management, making insertions and deletions much easier. It also allows us to scan the list in either the direction. Another advantage is meaningful only in the case of some type of failures. Since the entire list can be read using either forward links or backward links, should on of the links become invalid, the list could be reconstructed by using the other.
A new element can be inserted into a doubly linked list in the following three ways:
- insert a new first element
- insert in the middle
- insert a new last element
Building a doubly linked list is similar to building a singly linked list except that two links are maintained. Hence, the structure must have room for both the links. Using mailing list example again, you can modify the structure address as shown here to accommodate both links. Here is the code fragment:
struct address { char name[30]; char street[40]; char city[25]; char state[4]; char zip[11]; struct address *next; struct address *prior; }info;
Using address as basic data item, following function, dlstore(), builds a doubly linked list:
void dlstore(struct address *i, struct address **last) { if(!*last) *last = i; /* is first item in list */ else (*last)->next = i; i->next = NULL; i->prior = *last; *last = i; }
Complete Mailing List Example
Here is the complete mailing list example program. The complete list is kept in memory while in use. However, it can be stored in a disk file and loaded for later use.
/* C Linked Lists - A Complete Mailing List Example Program */ #include<stdio.h> #include<conio.h> #include<stdlib.h> #include<string.h> struct address { char name[40]; char street[50]; char city[30]; char state[3]; char zip[11]; struct address *next; // pointer to the next entry struct address *prior; // pointer to the previous record }; struct address *start; // pointer to the first entry in the list struct address *last; // pointer to the last entry struct address *find(char *); void enter(void); void search(void); void save(void); void load(void); void list(void); void mldelete(struct address **, struct address **); void dls_store(struct address *i, struct address **start, struct address **last); void inputs(char *, char *, int); void display(struct address *); int menu_select(void); void main(void) { clrscr(); start = last = NULL; // initialized start and end pointers for(;;) { switch(menu_select()) { case 1 : enter(); // to enter an address break; case 2 : mldelete(&start, &last); // to remove an address break; case 3 : list(); // to display the list break; case 4 : search(); // to find an address break; case 5 : save(); // to save the list to disk break; case 6 : load(); // to read from the disk break; case 7 : exit(0); } } getch(); } // select an operation int menu_select(void) { char str[80]; int c; printf("1. Enter a name\n"); printf("2. Delete a name\n"); printf("3. List the file\n"); printf("4. Search\n"); printf("5. Save the file\n"); printf("6. Load the file\n"); printf("7. Quit\n"); do { printf("\nEnter your choice : "); gets(str); c = atoi(str); }while(c<0 || c>7); return c; } // enter the names and addresses void enter(void) { struct address *info; for(;;) { info = (struct address *)malloc(sizeof(struct address)); if(!info) { printf("\nout of memory..!!"); return; } inputs("Enter name: ", info->name, 40); if(!info->name[0]) break; // stop entering inputs("Enter street: ", info->street, 40); inputs("Enter city: ", info->city, 30); inputs("Enter state: ", info->state, 3); inputs("Enter zip: ", info->zip, 10); dls_store(info, &start, &last); } // entry loop } /* this function will input a string up to the * length in count and will prevent the string * from being overrun. It will also display a * prompting message */ void inputs(char *prompt, char *s, int count) { char p[255]; do { printf(prompt); fgets(p, 254, stdin); if(strlen(p) > count) { printf("\nToo Long..!!\n"); } }while(strlen(p) > count); p[strlen(p)-1] = 0; // remove newline character strcpy(s, p); } // now create a doubly linked list in the sorted order void dls_store(struct address *i, struct address **start, struct address **last) { struct address *old; struct address *p; if(*last == NULL) { i->next = NULL; i->prior = NULL; *last = i; *start = i; return; } p = *start; // start at top of the list old = NULL; while(p) { if(strcmp(p->name, i->name)<0) { old = p; p = p->next; } else { if(p->prior) { p->prior->next = i; i->next = p; i->prior = p->prior; p->prior = i; return; } i->next = p; // new first element i->prior = NULL; p->prior = i; *start = i; return; } } old->next = i; // put on end i->next = NULL; i->prior = old; *last = i; } // remove an element from the list void mldelete(struct address **start, struct address **last) { struct address *info; char str[80]; inputs("Enter name: ", str, 40); info = find(str); if(info) { if(*start==info) { *start=info->next; if(*start) { (*start)->prior = NULL; } else { *last = NULL; } } else { info->prior->next = info->next; if(info!=*last) { info->next->prior = info->prior; } else { *last = info->prior; } } free(info); // returned memory to system } } // find an address struct address *find(char *name) { struct address *info; info = start; while(info) { if(!strcmp(name, info->name)) return info; info = info->next; // get next address } printf("Name not found..!!\n"); return NULL; // not found } // display the complete list void list(void) { struct address *info; info = start; while(info) { display(info); info = info->next; // get next address } printf("\n\n"); } // now this function prints the fields in each address void display(struct address *info) { printf("%s\n", info->name); printf("%s\n", info->street); printf("%s\n", info->city); printf("%s\n", info->state); printf("%s\n", info->zip); printf("\n\n"); } // look or search for a name in the list void search(void) { char name[40]; struct address *info; printf("Enter name to find: "); gets(name); info = find(name); if(!info) { printf("Not found..!!\n"); } else { display(info); } } // now save the file to the disk void save(void) { struct address *info; FILE *fp; fp = fopen("mlist", "wb"); if(!fp) { printf("Cannot open file..!!\n"); exit(1); } printf("\nSaving File..\n"); info = start; while(info) { fwrite(info, sizeof(struct address), 1, fp); info = info->next; // get next address } fclose(fp); } // load the address file void load() { struct address *info; FILE *fp; fp = fopen("mlist", "rb"); if(!fp) { printf("Cannot open file..!!\n"); exit(1); } // now free any previously allocated memory while(start) { info = start->next; free(info); start = info; } // reset top and bottom pointers start = last = NULL; printf("\nLoading file..\n"); while(!feof(fp)) { info = (struct address *) malloc(sizeof(struct address)); if(!info) { printf("Out of Memory..!!"); return; } if(1 != fread(info, sizeof(struct address), 1, fp)) break; dls_store(info, &start, &last); } fclose(fp); }
This program saves your input data in the file. Here are some sample outputs, just concentrate on it:

After entering the two record, just press enter. After pressing the ENTER key, you will get this output:

Now press 3 and then press enter key to display the file. Here is the sample output after pressing the key 3 then ENTER:

As you can see, after pressing the 3 then ENTER key, you will see the entered record on the output screen. Now press 2 to delete a record from the list. Enter the name which you want to delete from the list, here we will enter Alok Kumar Singh. After entering the name which is going to delete, just press enter to perform the deletion of this name from the list. After doing this, here is the sample output :

To check, whether the required record is deleted or not from the list, just press 3 to display the entire list and check whether the name is present in the list or not, which was performed for deletion previously. Here is the sample output:

As you can see, the deletion was performed successfully i.e., Alok Kumar Singh is not in the list now. Now to search any record, just enter 4, and then enter the name to be search. Here is the sample output of the search operation.

To save the file (record), just press 5 to save. Here is the sample output:

You can do any action accordingly as you saw. To quit the program just enter 7, but before quitting the program, press 5 to save your entered record, for the further use.
« Previous Tutorial Next Tutorial »