For creating the LinkedList program I have used Linux(ubuntu 12.04) machine. When I was in my college days, I would use the Tourbo C compiler which was easy to use in Windows
Type the following command to install the build-essential which create our environment and C compiler to build and run C programs. This will be enough for our purpose to create C programs.
$ sudo apt−get install build−essential
SinglyLinkedList.c
-----------------------
#include <stdio.h>
#include <stdlib.h>
/*
Linded List is having an element and a pointer which points to the same type of structure.
I have type defined a NODE type and given alias as "node".
*/
typedef struct NODE {
int info;
struct NODE *next;
}node;
/*
I have created a boolean type which returns 0, 1 and 2 which returns false, true and done respectively. This is basically for return type to be used in the program to return boolean values.
*/
typedef enum {false, true, done}boolean;
/*
Now create an empty list. When the list is empty it's pointer will point to NULL.
*/
void createEmptyList(node **head) {
*head = NULL;
}
/*
For inserting element in the beginning we need to consider some conditions, such as, when list is empty, we create single node and it's next element will point to NULL. Else, when list is not empty and having some element already, then we simply create a node and the newly created element's next pointer will point to the head pointer.
*/
boolean insertAtBeginning(node **head, int ele) {
node *ptr;
ptr = (node *)malloc(sizeof(node));
ptr->info = ele;
if(*head == NULL) {
ptr->next = NULL;
}
else {
ptr->next = *head;
}
*head = ptr;
return true;
}
/*
When insert element at the end in the linked list also applies two condition basically.
1. when list is empty, create an list type pointer and point the head pointer to the newly created element.
2. When list is already having elements then create a new list type and traverse to the last element's location and last locations next pointer will point to the newly created element. Hence, the element will be inserted to the last position.
*/
boolean insertAtEnd(node **head, int e) {
node *ptr, *location;
ptr = (node *)malloc(sizeof(node));
ptr->info = e;
ptr->next = NULL;
if(*head == NULL) {
*head = ptr;
}
else {
location = *head;
while(location->next != NULL) {
location = location->next;
}
location->next = ptr;
}
return true;
}
node *searchList(node *list, int elem) {
while( (list != NULL) && (list->info != elem) && (list->next != NULL) ) {
list = list->next;
}
return list;
}
/*
To insert element after any given element, we need to find the element in the list. For this I have created a searchList() method which returns the location of the element. So, newly created node's next will point to the location's next pointer and searched locations next pointer will point to the newly created element.
*/
boolean insertAfterElement(node *list, int after, int element) {
node *location, *newptr;
location = searchList(list, after);
if(location->info != after) {
return false;
}
else {
newptr = (node *)malloc(sizeof(node));
newptr->info = element;
newptr->next = location->next;
location->next = newptr;
return true;
}
}
node *searchList1(node *list, int elem) {
while(list != NULL) {
if(list->next->info == elem) {
printf("\nlist-> %d\n", list->next->info);
return list;
}
list = list->next;
}
return list;
}
/*
To insert before an element applied the same logic as insertAfterElement with only difference is newly created element will be inserted before the searched element's location, this requires little adjustment in the element's position.
*/
boolean insertBeforeElement(node *list, int before, int element) {
node *location, *newptr;
location = searchList1(list, before);
if(location->next->info != before) {
return false;
}
else {
newptr = (node *)malloc(sizeof(node));
newptr->info = element;
newptr->next = location->next;
location->next = newptr;
return true;
}
}
/*
To traverse elements of the list, iterate until it finds null and show the element of the node. For my clearly showing locations, I have shown the elements pointer location and next pointer memory location also.
*/
void traverseInOrder(node *head) {
if(head == NULL) printf("No element\n");
else {
printf("Element\tElement Address\tAddress of next Element\t\n");
while(head != NULL) {
printf("%d \t %u \t %u\n",head->info, (unsigned int)head, (unsigned int)head->next);
head = head->next;
}
}
}
/*
For deleting element from beginning, we need to point the beginner's head pointer to the next element's pointer and free the memory occupied by first element.
*/
boolean deleteFromBeginning(node **head, int *element) {
node *delNode;
if(*head == NULL)
return false;
else {
delNode = *head;
*element = (*head)->info;
*head = (*head)->next;
free(delNode);
return true;
}
}
/*
Move the head pointer to the penultimate elements location and free the memory for the last element's location.
*/
boolean deleteFromEnd(node **head, int *num) {
node *deleteNode, *loc;
if(*head == NULL)
return false;
else if((*head)->next == NULL) {
*head = NULL;
return done;
}
else {
loc = *head;
while(loc->next->next != NULL)
loc = loc->next;
deleteNode = loc->next;
*num = deleteNode->info;
loc->next = NULL;
free(deleteNode);
return true;
}
}
/*
Traverse to the each element and free the memory occupied by each element until reaches NULL.
*/
boolean deleteList(node **list) {
node *ptr;
while(*list != NULL) {
ptr = *list;
*list = (*list)->next;
free(ptr);
}
return done;
}
/*
Search element after which element to be deleted and adjust the pointer accordingly.
*/
boolean deleteAfterElement(node *head, int after) {
node *ptr, *loc;
loc = searchList(head, after);
if(loc == (node *)NULL)
return false;
ptr = loc->next;
loc->next = ptr->next;
free(ptr);
return true;
}
/*
I have separated the main menu in main_menu() method, just to reduce our main function.
*/
int main_menu(int choice) {
printf("Pick the following options \n");
printf("==============================\n");
printf("1. \tInsert at beginning\n");
printf("2. \tInsert at end\n");
printf("3. \tInsert at after a given element\n");
printf("4. \tInsert before a given element\n");
printf("5. \tTraverse in order\n");
printf("6. \tDelete from beginning \n");
printf("7. \tDelete from end\n");
printf("8. \tDelete after a given element\n");
printf("9. \tDelete entire list \n");
printf("10.\tExit \n\n");
printf(" \tEnter your choice (1-10) :\n");
scanf("%d",&choice);
return choice;
}
int main() {
node *head;
int choice, count=0;
int element, after, before;
boolean b;
createEmptyList(&head);
while(1) {
switch(main_menu(choice)) {
case 1:
printf("Enter element to be inserted at beginning.\n");
scanf("%d", &element);
if(insertAtBeginning(&head, element)== 0)
printf("Error..Element is not inserted.\n");
else
printf("Element is inserted at beginning.\n");
break;
case 2:
printf("Enter element to be inserted at end.\n");
scanf("%d", &element);
if(insertAtEnd(&head, element)== 0)
printf("Error..Element is not inserted.\n");
else
printf("Element is inserted at end.\n");
break;
case 3:
printf("Enter element after which you want to insert : ");
scanf("%d",&after);
printf("Enter element to be inserted : ");
scanf("%d", &element);
if(insertAfterElement(head, after, element) == 0)
printf("Error...Element not found, can't insert\n");
else
printf("The given element %d is inserted after %d\n",element, after);
break;
case 4:
printf("Enter element before which you want to insert : ");
scanf("%d",&before);
printf("Enter element to be inserted : ");
scanf("%d", &element);
if(insertBeforeElement(head, before, element) == 0)
printf("Error...Element not found, can't insert\n");
else
printf("The given element %d is inserted before %d\n",element, before);
break;
case 5:
traverseInOrder(head);
break;
case 6:
b = deleteFromBeginning(&head, &element);
if(b == 0)
printf("Error...List is null.\n");
else
printf("Element deleted is %d\n", element);
break;
case 7:
b = deleteFromEnd(&head, &element);
if(b == 0)
printf("Error...List is null\n");
else if(b == done)
printf("Element is deleted, list is empty now\n");
else
printf("Deleted element is %d\n", element);
break;
case 8:
printf("Enter element after which you want to delete : ");
scanf("%d",&after);
if(deleteAfterElement(head, after) == 0)
printf("Error...Element not found, can't delete\n");
else
printf("The element after %d is deleted\n", after);
break;
case 9:
break;
case 10:
if(deleteList(&head)== 2)
printf("List elements are deleted\n");
else
printf("Error..Elements are not deleted\n");
break;
default:
printf("Exit..\n");
return 0;
}
}
return 0;
}
Type the following command to install the build-essential which create our environment and C compiler to build and run C programs. This will be enough for our purpose to create C programs.
$ sudo apt−get install build−essential
SinglyLinkedList.c
-----------------------
#include <stdio.h>
#include <stdlib.h>
/*
Linded List is having an element and a pointer which points to the same type of structure.
I have type defined a NODE type and given alias as "node".
*/
typedef struct NODE {
int info;
struct NODE *next;
}node;
/*
I have created a boolean type which returns 0, 1 and 2 which returns false, true and done respectively. This is basically for return type to be used in the program to return boolean values.
*/
typedef enum {false, true, done}boolean;
/*
Now create an empty list. When the list is empty it's pointer will point to NULL.
*/
void createEmptyList(node **head) {
*head = NULL;
}
/*
For inserting element in the beginning we need to consider some conditions, such as, when list is empty, we create single node and it's next element will point to NULL. Else, when list is not empty and having some element already, then we simply create a node and the newly created element's next pointer will point to the head pointer.
*/
boolean insertAtBeginning(node **head, int ele) {
node *ptr;
ptr = (node *)malloc(sizeof(node));
ptr->info = ele;
if(*head == NULL) {
ptr->next = NULL;
}
else {
ptr->next = *head;
}
*head = ptr;
return true;
}
/*
When insert element at the end in the linked list also applies two condition basically.
1. when list is empty, create an list type pointer and point the head pointer to the newly created element.
2. When list is already having elements then create a new list type and traverse to the last element's location and last locations next pointer will point to the newly created element. Hence, the element will be inserted to the last position.
*/
boolean insertAtEnd(node **head, int e) {
node *ptr, *location;
ptr = (node *)malloc(sizeof(node));
ptr->info = e;
ptr->next = NULL;
if(*head == NULL) {
*head = ptr;
}
else {
location = *head;
while(location->next != NULL) {
location = location->next;
}
location->next = ptr;
}
return true;
}
node *searchList(node *list, int elem) {
while( (list != NULL) && (list->info != elem) && (list->next != NULL) ) {
list = list->next;
}
return list;
}
/*
To insert element after any given element, we need to find the element in the list. For this I have created a searchList() method which returns the location of the element. So, newly created node's next will point to the location's next pointer and searched locations next pointer will point to the newly created element.
*/
boolean insertAfterElement(node *list, int after, int element) {
node *location, *newptr;
location = searchList(list, after);
if(location->info != after) {
return false;
}
else {
newptr = (node *)malloc(sizeof(node));
newptr->info = element;
newptr->next = location->next;
location->next = newptr;
return true;
}
}
node *searchList1(node *list, int elem) {
while(list != NULL) {
if(list->next->info == elem) {
printf("\nlist-> %d\n", list->next->info);
return list;
}
list = list->next;
}
return list;
}
/*
To insert before an element applied the same logic as insertAfterElement with only difference is newly created element will be inserted before the searched element's location, this requires little adjustment in the element's position.
*/
boolean insertBeforeElement(node *list, int before, int element) {
node *location, *newptr;
location = searchList1(list, before);
if(location->next->info != before) {
return false;
}
else {
newptr = (node *)malloc(sizeof(node));
newptr->info = element;
newptr->next = location->next;
location->next = newptr;
return true;
}
}
/*
To traverse elements of the list, iterate until it finds null and show the element of the node. For my clearly showing locations, I have shown the elements pointer location and next pointer memory location also.
*/
void traverseInOrder(node *head) {
if(head == NULL) printf("No element\n");
else {
printf("Element\tElement Address\tAddress of next Element\t\n");
while(head != NULL) {
printf("%d \t %u \t %u\n",head->info, (unsigned int)head, (unsigned int)head->next);
head = head->next;
}
}
}
/*
For deleting element from beginning, we need to point the beginner's head pointer to the next element's pointer and free the memory occupied by first element.
*/
boolean deleteFromBeginning(node **head, int *element) {
node *delNode;
if(*head == NULL)
return false;
else {
delNode = *head;
*element = (*head)->info;
*head = (*head)->next;
free(delNode);
return true;
}
}
/*
Move the head pointer to the penultimate elements location and free the memory for the last element's location.
*/
boolean deleteFromEnd(node **head, int *num) {
node *deleteNode, *loc;
if(*head == NULL)
return false;
else if((*head)->next == NULL) {
*head = NULL;
return done;
}
else {
loc = *head;
while(loc->next->next != NULL)
loc = loc->next;
deleteNode = loc->next;
*num = deleteNode->info;
loc->next = NULL;
free(deleteNode);
return true;
}
}
/*
Traverse to the each element and free the memory occupied by each element until reaches NULL.
*/
boolean deleteList(node **list) {
node *ptr;
while(*list != NULL) {
ptr = *list;
*list = (*list)->next;
free(ptr);
}
return done;
}
/*
Search element after which element to be deleted and adjust the pointer accordingly.
*/
boolean deleteAfterElement(node *head, int after) {
node *ptr, *loc;
loc = searchList(head, after);
if(loc == (node *)NULL)
return false;
ptr = loc->next;
loc->next = ptr->next;
free(ptr);
return true;
}
/*
I have separated the main menu in main_menu() method, just to reduce our main function.
*/
int main_menu(int choice) {
printf("Pick the following options \n");
printf("==============================\n");
printf("1. \tInsert at beginning\n");
printf("2. \tInsert at end\n");
printf("3. \tInsert at after a given element\n");
printf("4. \tInsert before a given element\n");
printf("5. \tTraverse in order\n");
printf("6. \tDelete from beginning \n");
printf("7. \tDelete from end\n");
printf("8. \tDelete after a given element\n");
printf("9. \tDelete entire list \n");
printf("10.\tExit \n\n");
printf(" \tEnter your choice (1-10) :\n");
scanf("%d",&choice);
return choice;
}
int main() {
node *head;
int choice, count=0;
int element, after, before;
boolean b;
createEmptyList(&head);
while(1) {
switch(main_menu(choice)) {
case 1:
printf("Enter element to be inserted at beginning.\n");
scanf("%d", &element);
if(insertAtBeginning(&head, element)== 0)
printf("Error..Element is not inserted.\n");
else
printf("Element is inserted at beginning.\n");
break;
case 2:
printf("Enter element to be inserted at end.\n");
scanf("%d", &element);
if(insertAtEnd(&head, element)== 0)
printf("Error..Element is not inserted.\n");
else
printf("Element is inserted at end.\n");
break;
case 3:
printf("Enter element after which you want to insert : ");
scanf("%d",&after);
printf("Enter element to be inserted : ");
scanf("%d", &element);
if(insertAfterElement(head, after, element) == 0)
printf("Error...Element not found, can't insert\n");
else
printf("The given element %d is inserted after %d\n",element, after);
break;
case 4:
printf("Enter element before which you want to insert : ");
scanf("%d",&before);
printf("Enter element to be inserted : ");
scanf("%d", &element);
if(insertBeforeElement(head, before, element) == 0)
printf("Error...Element not found, can't insert\n");
else
printf("The given element %d is inserted before %d\n",element, before);
break;
case 5:
traverseInOrder(head);
break;
case 6:
b = deleteFromBeginning(&head, &element);
if(b == 0)
printf("Error...List is null.\n");
else
printf("Element deleted is %d\n", element);
break;
case 7:
b = deleteFromEnd(&head, &element);
if(b == 0)
printf("Error...List is null\n");
else if(b == done)
printf("Element is deleted, list is empty now\n");
else
printf("Deleted element is %d\n", element);
break;
case 8:
printf("Enter element after which you want to delete : ");
scanf("%d",&after);
if(deleteAfterElement(head, after) == 0)
printf("Error...Element not found, can't delete\n");
else
printf("The element after %d is deleted\n", after);
break;
case 9:
break;
case 10:
if(deleteList(&head)== 2)
printf("List elements are deleted\n");
else
printf("Error..Elements are not deleted\n");
break;
default:
printf("Exit..\n");
return 0;
}
}
return 0;
}
To compile the file and create the executable file type the following command.
$ cc -Wall -g SinglyLinkedList.c -o SinglyLinkedList
To run the program type the following command :
$ ./SinglyLinkedList
Some of the screenshots are as follows:
Inserted some of the elements.
following shows the inserted elements.
That's it folks, the given program is showing all the general operations which can be performed on the Singly Linked List, which will get you started for the data structure programs related to Single list. This program is very basic and can be used used to extend the functionality and do some more stuff related to linked list. Some operations requires use of stack and optimal sorting algorithms which I will try to post other day sometimes.
Above all, try using it as a basis for creating more complex operation on single linked list. :)
$ cc -Wall -g SinglyLinkedList.c -o SinglyLinkedList
To run the program type the following command :
$ ./SinglyLinkedList
Some of the screenshots are as follows:
following shows the inserted elements.
That's it folks, the given program is showing all the general operations which can be performed on the Singly Linked List, which will get you started for the data structure programs related to Single list. This program is very basic and can be used used to extend the functionality and do some more stuff related to linked list. Some operations requires use of stack and optimal sorting algorithms which I will try to post other day sometimes.
Above all, try using it as a basis for creating more complex operation on single linked list. :)
Comments
Post a Comment