KEMBAR78
C Linked List Guide for Developers | PDF | Computer Engineering | Data
Scribd
Upload
71 views17 pages

C Linked List Guide for Developers

The document discusses the implementation of a stack using a linked list data structure in C. It defines a node structure with a value and pointer to the next node. Functions to push, pop and display the stack are created by manipulating the head pointer of the linked list. Push adds a new node to the head, pop removes the head node, and display traverses the list to print all elements. These functions allow performing basic stack operations of insert, remove and traversal using a linked list.

Uploaded by

Nikhil Kachhawah
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
71 views17 pages

C Linked List Guide for Developers

The document discusses the implementation of a stack using a linked list data structure in C. It defines a node structure with a value and pointer to the next node. Functions to push, pop and display the stack are created by manipulating the head pointer of the linked list. Push adds a new node to the head, pop removes the head node, and display traverses the list to print all elements. These functions allow performing basic stack operations of insert, remove and traversal using a linked list.

Uploaded by

Nikhil Kachhawah
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 17

// Linked list implementation in C

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

// Creating a node
struct node {
int value;
struct node *next;
};

// print the linked list value


void printLinkedlist(struct node *p) {
while (p != NULL) {
printf("%d ", p->value);
p = p->next;
}
}

int main() {
// Initialize nodes
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

// Allocate memory
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

// Assign value values


one->value = 1;
two->value = 2;
three->value = 3;

// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;

// printing node-value
head = one;
printLinkedlist(head);
}

Output

123
// Linked list operations in C

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

// Create a node
struct Node {
int data;
struct Node* next;
};

// Insert at the beginning


void insertAtBeginning(struct Node** head_ref, int new_data) {
// Allocate memory to a node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

// insert the data


new_node->data = new_data;

new_node->next = (*head_ref);

// Move head to new node


(*head_ref) = new_node;
}

// Insert a node after a node


void insertAfter(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));


new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}

// Insert at the end


void insertAtEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref; /* used in step 5*/

new_node->data = new_data;
new_node->next = NULL;

if (*head_ref == NULL) {
*head_ref = new_node;
return;
}

while (last->next != NULL) last = last->next;


last->next = new_node;
return;
}

// Delete a node
void deleteNode(struct Node** head_ref, int key) {
struct Node *temp = *head_ref, *prev;

if (temp != NULL && temp->data == key) {


*head_ref = temp->next;
free(temp);
return;
}
// Find the key to be deleted
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}

// If the key is not present


if (temp == NULL) return;

// Remove the node


prev->next = temp->next;

free(temp);
}

// Search a node
int searchNode(struct Node** head_ref, int key) {
struct Node* current = *head_ref;

while (current != NULL) {


if (current->data == key) return 1;
current = current->next;
}
return 0;
}

// Sort the linked list


void sortLinkedList(struct Node** head_ref) {
struct Node *current = *head_ref, *index = NULL;
int temp;

if (head_ref == NULL) {
return;
} else {
while (current != NULL) {
// index points to the node next to current
index = current->next;
while (index != NULL) {
if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
}
}
}

// Print the linked list


void printList(struct Node* node) {
while (node != NULL) {
printf(" %d ", node->data);
node = node->next;
}
}

int main() {
struct Node* head = NULL;

insertAtEnd(&head, 1);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 3);
insertAtEnd(&head, 4);
insertAfter(head->next, 5);

printf("Linked list: ");


printList(head);

printf("\nAfter deleting an element: ");


deleteNode(&head, 3);
printList(head);

int item_to_find = 3;
if (searchNode(&head, item_to_find)) {
printf("\n%d is found", item_to_find);
} else {
printf("\n%d is not found", item_to_find);
}

sortLinkedList(&head);
printf("\nSorted List: ");
printList(head);
}
Output

Linked list: 3 2 5 1 4
After deleting an element: 2 5 1 4
3 is not found
Sorted List: 1 2 4 5
Doubly Linked List Implementation in C

#include <stdio.h>
#include <stdlib.h>
// node creation
struct Node {
int data;
struct Node* next;
struct Node* prev;
};

// insert node at the front


void insertFront(struct Node** head, int data) {
// allocate memory for newNode
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

// assign data to newNode


newNode->data = data;

// make newNode as a head


newNode->next = (*head);

// assign null to prev


newNode->prev = NULL;

// previous of head (now head is the second node) is newNode


if ((*head) != NULL)
(*head)->prev = newNode;

// head points to newNode


(*head) = newNode;
}

// insert a node after a specific node


void insertAfter(struct Node* prev_node, int data) {
// check if previous node is null
if (prev_node == NULL) {
printf("previous node cannot be null");
return;
}

// allocate memory for newNode


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// assign data to newNode
newNode->data = data;
// set next of newNode to next of prev node
newNode->next = prev_node->next;
// set next of prev node to newNode
prev_node->next = newNode;
// set prev of newNode to the previous node
newNode->prev = prev_node;
// set prev of newNode's next to newNode
if (newNode->next != NULL)
newNode->next->prev = newNode;
}

// insert a newNode at the end of the list


void insertEnd(struct Node** head, int data) {
// allocate memory for node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

// assign data to newNode


newNode->data = data;

// assign null to next of newNode


newNode->next = NULL;

// store the head node temporarily (for later use)


struct Node* temp = *head;

// if the linked list is empty, make the newNode as head node


if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}

// if the linked list is not empty, traverse to the end of the linked list
while (temp->next != NULL)
temp = temp->next;

// now, the last node of the linked list is temp

// assign next of the last node (temp) to newNode


temp->next = newNode;

// assign prev of newNode to temp


newNode->prev = temp;
}

// delete a node from the doubly linked list


void deleteNode(struct Node** head, struct Node* del_node) {
// if head or del is null, deletion is not possible
if (*head == NULL || del_node == NULL)
return;

// if del_node is the head node, point the head pointer to the next of del_node
if (*head == del_node)
*head = del_node->next;

// if del_node is not at the last node, point the prev of node next to del_node to the previous of
del_node
if (del_node->next != NULL)
del_node->next->prev = del_node->prev;

// if del_node is not the first node, point the next of the previous node to the next node of
del_node
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;

// free the memory of del_node


free(del_node);
}

// print the doubly linked list


void displayList(struct Node* node) {
struct Node* last;

while (node != NULL) {


printf("%d->", node->data);
last = node;
node = node->next;
}
if (node == NULL)
printf("NULL\n");
}

int main() {
// initialize an empty node
struct Node* head = NULL;

insertEnd(&head, 5);
insertFront(&head, 1);
insertFront(&head, 6);
insertEnd(&head, 9);

// insert 11 after head


insertAfter(head, 11);

// insert 15 after the seond node


insertAfter(head->next, 15);

displayList(head);

// delete the last node


deleteNode(&head, head->next->next->next->next->next);

displayList(head);
}

Output

6->11->15->1->5->9->NULL6->11->15->1->5->NULL
Linked List Implementation in C – Stack

#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
struct node *head;

void main ()
{
int choice=0;
printf("\n*********Stack operations using linked list*********\n");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("\n\nChose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}
void push ()
{
int val;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;

}
printf("Item pushed");

}
}

void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");

}
}
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}

Output

*********Stack operations using linked list*********

----------------------------------------------

Chose one from the below options...

1.Push
2.Pop
3.Show
4.Exit
Enter your choice
2
Underflow

Chose one from the below options...

1.Push
2.Pop
3.Show
4.Exit
Enter your choice
1
Enter the value10
Item pushed

Chose one from the below options...

1.Push
2.Pop
3.Show
4.Exit
Enter your choice
1
Enter the value10
Item pushed

Chose one from the below options...

1.Push
2.Pop
3.Show
4.Exit
Enter your choice
3
Printing Stack elements
10
10

Chose one from the below options...

1.Push
2.Pop
3.Show
4.Exit
Enter your choice
2
Item popped

Chose one from the below options...

1.Push
2.Pop
3.Show
4.Exit
Enter your choice
3
Printing Stack elements
10

Chose one from the below options...

1.Push
2.Pop
3.Show
4.Exit
Enter your choice
2
Item popped

Chose one from the below options...


1.Push
2.Pop
3.Show
4.Exit
Enter your choice
2
Underflow

Chose one from the below options...

1.Push
2.Pop
3.Show
4.Exit
Enter your choice 4
Linked List Implementation in C – Queue

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front;
struct node *rear;
void insert();
void delete();
void display();
void main ()
{
int choice;
while(choice != 4)
{
printf("\n*************************Main Menu*****************************\
n");
printf("\
n=================================================================\n");
printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
printf("\nEnter your choice ?");
scanf("%d",& choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
void insert()
{
struct node *ptr;
int item;

ptr = (struct node *) malloc (sizeof(struct node));


if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
void delete ()
{
struct node *ptr;
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
void display()
{
struct node *ptr;
ptr = front;
if(front == NULL)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
while(ptr != NULL)
{
printf("\n%d\n",ptr -> data);
ptr = ptr -> next;
}
}
}

Output

***********Main Menu**********

==============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter value?
123

***********Main Menu**********

==============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter value?
90

***********Main Menu**********

==============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

printing values .....

123

90

***********Main Menu**********
==============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?2

***********Main Menu**********

==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

printing values .....

90

***********Main Menu**********

==============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?4

You might also like