C program to insert an element at any position in a linked list

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

/* Node Stucture */
typedef struct node_t {
int data;
struct node_t *next;
} Node;

/* Function Declarations */
Node * insert_top(int, Node *);
Node * insert_bottom(int, Node *);
Node * insert_after(int, int, Node *);
Node * insert_before(int, int, Node *);
void print(Node *);
int count(Node *);

/* Add a new node to the top of a list */
Node * insert_top(int num, Node *head) {
Node *new_node;
new_node = (Node *) malloc(sizeof(Node));
new_node->data = num;
new_node->next= head;
head = new_node;
return head;
}

/* Add a new node to the bottom of a list */
Node * insert_bottom(int num, Node *head) {
Node *current_node = head;
Node *new_node;
while ( current_node != NULL && current_node->next != NULL) {
current_node = current_node->next;
}

new_node = (Node *) malloc(sizeof(Node));
new_node->data = num;
new_node->next= NULL;
if (current_node != NULL)
current_node->next = new_node;
else
head = new_node;
return head;
}

/* Add a new node after an element in the list */
Node * insert_after(int num, int prev_num, Node *head) {
Node *current_node = head;
Node *new_node;
while ( current_node->data != prev_num) {
current_node = current_node->next;
}
new_node = (Node *) malloc(sizeof(Node));
new_node->data = num;
new_node->next= current_node->next;
current_node->next = new_node;
return head;
}

/* Add a new node before an element in the list */
Node * insert_before(int num, int next_num, Node *head) {
Node *current_node = head;
Node *new_node;
while ( current_node->next->data != next_num) {
current_node = current_node->next;
}
new_node = (Node *) malloc(sizeof(Node));
new_node->data = num;
new_node->next= current_node->next;
current_node->next = new_node;
return head;
}

/* Print all the elements in the linked list */
void print(Node *head) {
Node *current_node = head;
while ( current_node != NULL) {
printf(“%d “, current_node->data);
current_node = current_node->next;
}
}

/* Program main */
int main()
{
Node *head = NULL;
int num, prev_num, next_num;
int option;
char * temp;
char ch;
/* Display Menu */
while(1) {

printf(“\n ***********************************\n”);
printf(“\n * Linked list operations: *\n”);
printf(“\n * 1. Insert at the top of list *\n”);
printf(“\n * 2. Insert at bottom of list *\n”);
printf(“\n * 3. Insert after an element *\n”);
printf(“\n * 4. Insert before an element *\n”);
printf(“\n * 5. Show all elements *\n”);
printf(“\n * 6. Quit *\n”);
printf(“\n ***********************************\n”);
printf(“\n Choose an option [1-5] : “);
if (scanf(“%d”, &option) != 1) {
printf(” *Error: Invalid input. Try again.\n”);
scanf(“%s”, &temp); /*clear input buffer */
continue;
}

switch (option) {
case 1: /* Add to top*/
printf(” Enter a number to insert : “);
if (scanf(“%d”, &num) != 1) {
printf(” *Error: Invalid input.\n”);
scanf(“%s”, &temp); /*clear input buffer */
continue;
}
head = insert_top(num, head);
printf(“Number %d added to the top of the list”, num);
printf(“\nPress any key to continue…”);
getch();
break;

case 2: /* add to bottom */
printf(” Enter a number to insert : “);
if (scanf(“%d”, &num) != 1) {
printf(” *Error: Invalid input. \n”);
scanf(“%s”, &temp);
continue;
}
head = insert_bottom(num, head);
printf(“%d added to the bottom of the list”, num);
printf(“\nPress any key to continue…”);
getch();
break;

case 3: /* Insert After */
printf(” Enter a number to insert : “);
if (scanf(“%d”, &num) != 1) {
printf(” *Error: Invalid input.\n”);
scanf(“%s”, &temp);
continue;
}

printf(” After which number do you want to insert : “);
if (scanf(“%d”, &prev_num) != 1) {
printf(” *Error: Invalid input.\n”);
scanf(“%s”, &temp);
continue;
}
if (head != NULL) {
head = insert_after(num, prev_num, head);
printf(“%d is inserted after %d”, num, prev_num);
}else {
printf(“The list is empty”, num, prev_num);
}
printf(“\nPress any key to continue…”);
getch();
break;

case 4: /* Insert Before */
printf(” Enter a number to insert : “);
if (scanf(“%d”, &num) != 1) {
printf(” *Error: Invalid input. \n”);
scanf(“%s”, &temp);
continue;
}

printf(” Before which number do you want to insert : “);
if (scanf(“%d”, &prev_num) != 1) {
printf(” *Error: Invalid input.\n”);
scanf(“%s”, &temp);
continue;
}

if (head != NULL) {
head = insert_before(num, prev_num, head);
printf(“Number %d inserted before %d”, num, prev_num);
}else {
printf(“The list is empty”, num, prev_num);
}
printf(“\nPress any key to continue…”);
getch();
break;

case 5: /* Show all elements */
printf(“\nElements in the list: \n [ “);
print(head);
printf(“]\n\nPress any key to continue…”);
getch();
break;

case 6: /* Exit */
return(0);
break;

default:
printf(“Invalid Option. Please Try again.”);
getch();

} /* End of Switch */
} /* End of While */

return(0);
}

A complete working Java program to demonstrate all insertion methods on linked list

package linked.list;

/**
*
* @author SHASHI
*/
// A complete working Java program to demonstrate all insertion methods
// on linked list
class LinkedList
{
Node head; // head of list

/* Linked list Node*/
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}

/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */
new_node.next = head;

/* 4. Move the head to point to new Node */
head = new_node;
}

/* Inserts a new node after the given prev_node. */
public void insertAfter(Node prev_node, int new_data)
{
/* 1. Check if the given Node is null */
if (prev_node == null)
{
System.out.println(“The given previous node cannot be null”);
return;
}

/* 2 & 3: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);

/* 4. Make next of new Node as next of prev_node */
new_node.next = prev_node.next;

/* 5. make next of prev_node as new_node */
prev_node.next = new_node;
}

/* Appends a new node at the end. This method is 
defined inside LinkedList class shown above */
public void append(int new_data)
{
/* 1. Allocate the Node &
2. Put in the data
3. Set next as null */
Node new_node = new Node(new_data);

/* 4. If the Linked List is empty, then make the
new node as head */
if (head == null)
{
head = new Node(new_data);
return;
}

/* 4. This new node is going to be the last node, so
make next of it as null */
new_node.next = null;

/* 5. Else traverse till the last node */
Node last = head;
while (last.next != null)
last = last.next;

/* 6. Change the next of last node */
last.next = new_node;
return;
}

/* This function prints contents of linked list starting from
the given node */
public void printList()
{
Node tnode = head;
while (tnode != null)
{
System.out.print(tnode.data+” “);
tnode = tnode.next;
}
}

/* Driver program to test above functions. Ideally this function
should be in a separate user class. It is kept here to keep
code compact */
public static void main(String[] args)
{
/* Start with the empty list */
LinkedList llist = new LinkedList();

// Insert 6. So linked list becomes 6->NUllist
llist.append(6);

// Insert 7 at the beginning. So linked list becomes
// 7->6->NUllist
llist.push(7);

// Insert 1 at the beginning. So linked list becomes
// 1->7->6->NUllist
llist.push(1);

// Insert 4 at the end. So linked list becomes
// 1->7->6->4->NUllist
llist.append(4);

// Insert 8, after 7. So linked list becomes
// 1->7->8->6->4->NUllist
llist.insertAfter(llist.head.next, 8);

System.out.println(“\nCreated Linked list is: “);
llist.printList();
}
}

OUTPUT

Created Linked list is:
1 7 8 6 4