In a singly (one-way) linear linked list, each node is divided into two parts.

  • The first part contains the information of the element.
  • The second part called the linked field or next pointer field contains the address of the next node in the list.

A head pointer is used to hold the address of the first element in the list. Also, the last element of the linked list has a NULL value in the next pointer field to mark the end of the list.

Singly Linked List

Declaration of a Linear Linked List

Suppose we want to store a list of ints, then the linear linked list can be declared as:

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; }
.cl { margin: 0px; }
.cb1 { color: green; }
.cb2 { color: blue; }
.cb3 { color: maroon; }

typedef struct nodetype
{
 int info;
 struct nodetype *next;
} node;
node *head;

The above declaration defines a new data type, “struct nodetype”, with a typedef of “node”.

Creating an empty list

  • In the previous declaration, the variable head is declared as a pointer to a “node”.
  • The variable head has not yet been initialized.
  • This variable is used to point to the first element of the list
  • Since the list will be empty in the beginning, the variable head is assigned a sentinel value to indicate that the list is empty.

void createemptylist(node **head)
{
 *head=NULL;
}

Operations on Linked Lists

The main operations that are performed on a linked list are the following:

Sample Program

Here is a sample linked list program:

/*
 * Linear Linked List of strings
 * http://www.byteguide.com
 */
 
#include <stdio.h>
#include <stdlib.h>
 
 
struct llnode
{
 char *data;
 struct llnode *next;
};
 
void addAtPos(struct llnode **, char *, int );
void search(struct llnode *, char *);
void deleteByElement(struct llnode **, char *);
void deleteByPosition(struct llnode **, int );
void elete_list(struct llnode **);
void display(struct llnode *);
void displaynth(struct llnode *, int );
void displayrev(struct llnode *, int );
 
 
/*
 * Driver functions -- main() and menu()
 */
int menu(struct llnode *);
int main()
{
 struct llnode *start = NULL;
 int pos;
 char temp[80];
 
 while (1)
 {
 switch(menu(start))
 {
 case 1:
 puts("Enter strings to add at end, blank line to stop: ");
 while (gets(temp)[0])
 addAtPos(&start, temp, INT_MAX);
 break;
 case 2:
 puts("Enter strings to add at beginning, blank line to stop: ");
 while (gets(temp)[0])
 addAtPos(&start, temp, 1);
 break;
 case 3:
 printf("Enter position: ");
 scanf("%d", &pos);
 gets(temp); /*Clear buffer*/
 printf("Enter the string to add: ");
 addAtPos(&start, gets(temp), pos);
 break;
 case 4:
 printf("Enter string to search: ");
 search(start, gets(temp));
 break;
 case 5:

pre class=”cl”> printf(“Enter string to delete: “);

 deleteByElement(&start, gets(temp));
 break;
 case 6:
 printf("Enter position: ");
 scanf("%d", &pos);
 gets(temp);
 deleteByPosition(&start, pos);
 break;
 case 7:
 delete_list(&start);
 puts("List deleted successfully");
 break;
 case 8:
 display(start);
 getchar();
 break;
 case 9:
 printf("Enter position: ");
 scanf("%d", &pos);
 gets(temp);
 displaynth(start, pos);
 break;
 case 10:
 displayrev(start, 1);
 getchar();
 break;
 case 11:
 exit(0);
 }
 }
}
 
int menu(struct llnode *start)
{
 int choice;
 char temp[80];
 puts("1-Add at end");
 puts("2-Add at beginning");
 puts("3-Add at position");
 if (start)
 {
 puts("4-Search");
 &nbs; puts("5-Delete by element");
 puts("6-Delete by position");
 puts("7-Delete list");
 puts("8-Display");
 puts("9-Display nth node");
 puts("10-Display in reverse");
 }
 puts("11-Exit");
 scanf("%d", &choice);
 gets(temp); /*clear buffer*/
 return choice;
}
void addAtPos(struct llnode **start, char *toadd, int pos)
{
 struct llnode *prev, *curr;
 struct llnode *newnode;
 int cnt;
 if (pos<1)
 {
 puts("Invalid position");
 return;
 }
 prev = NULL;
 curr = *start;
 for (cnt=1; curr && cnt<pos; cnt++)
 {
 prev = curr;
 curr = curr->next;
 }
 newnode = malloc(sizeof (struct llnode));
 newnode->data = malloc(strlen(toadd)+1);
 strcpy(newnode->data, toadd);
 newnode->next = curr;
 if (prev!=NULL)
 prev->next = newnode;
 else
 *start = newnode;
 if (curr==NULL && prev!=NULL && pos!=INT_MAX)
 puts("Data inserted at end");
}
 
void search(struct llnode *p, char *tosearch)
{
 int pos;
 
 for (pos=1; p && strcmp(p->data, tosearch)!=0; pos++)
 p = p->next;
 
 
 if (p!=NULL)
 printf("%s found at position %dn", tosearch, pos);
 else
 printf("%s not found in listn", tosearch);
}
void deleteByElement(struct llnode **start, char *todelete)
{
 struct llnode *prev, *curr, *temp;
 prev = NULL;
 curr = *start;
 
 while (curr && strcmp(curr->data, todelete)!=0)
 {
 prev = curr;
 curr = curr->next;
 }
 if (curr == NULL)
 puts("ELEMENT NOT FOUND");
 else
 {
 temp = curr;
 if (prev != NULL)
 prev->next = curr->next;
 else
 *start = (*start)->next; /*this deletes the first element*/
 free(temp->data);
 free(temp);
 printf("%s deleted successfully", todelete);
 }
 getchar();
}
void deleteByPosition(struct llnode **start, int pos)
{
 struct llnode *prev, *curr, *temp;
 int cnt;
 char deleted[80];
 prev = NULL;
 curr = *start;
 for (cnt=1; curr && cnt<pos; cnt++)
 {
 prev = curr;
 curr = curr->next;
 }
 if (curr == NULL && cnt!=1)
 puts("POSITION NOT FOUND");
 else
 {
 temp = curr;
 if (prev != NULL)
 prev->next = curr->next;
 else
 *start = (*start)->next; /*this deletes the first element*/
 strcpy(deleted, temp->data);
 free(temp->data);
 free(temp);
 printf("%s deleted successfully", deleted);
 }
 getchar();
}
void delete_list(struct llnode **start)
{
 struct llnode *temp;
 while(*start)
 {
 temp = *start;
 *start = (*start)->next;
 free(temp);
 }
}
void display(struct llnode *p)
{
 int cnt;
 for (cnt=1; p; cnt++)
 {
 printf("%d: %sn",cnt,p->data);
 p = p->next;
 }
}
 
void displaynth(struct llnode *p, int pos)
{
 int cnt;
 for (cnt=1; p && cnt<pos; cnt++)
 p=p->next;
 
 if (p && cnt==pos)
 printf("The %dth node is %sn", pos, p->data);
 else
 printf("Invalid positionn");
 getchar();
}
 
void displayrev(struct llnode *p, int cnt)
{
 if (p)
 {
 displayrev(p->next, cnt+1);
 printf("%d: %sn", cnt, p->data);
 }
}