Scribd
Upload
4 views20 pages

Week 5

The document provides a comprehensive implementation of linked list operations in C, covering both single and doubly linked lists. It includes functions for creating, inserting, deleting, displaying, counting, and searching elements within the lists, as well as merging and reversing lists. Additionally, it demonstrates how to concatenate two linked lists and manage memory effectively.

Uploaded by

md sameer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views20 pages

Week 5

The document provides a comprehensive implementation of linked list operations in C, covering both single and doubly linked lists. It includes functions for creating, inserting, deleting, displaying, counting, and searching elements within the lists, as well as merging and reversing lists. Additionally, it demonstrates how to concatenate two linked lists and manage memory effectively.

Uploaded by

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

Week 5

Single Linked List Implementation

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

struct Node {
int data;
struct Node* next;
};

struct Node* head = NULL;

void create(int value) {


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
head = newNode;
printf("List created with element: %d\n", value);
}

void insertfront(int value) {


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = head;
head = newNode;
printf("Inserted element: %d\n", value);
}

void insertend(int value) {


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

if (head == NULL) {
head = newNode;
} else {
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
printf("Inserted element: %d\n", value);
}

void insertpos(int value, int position) {


if (position < 1 || position > Count() + 1) {
printf("Invalid position\n");
return;
}

if (position == 1) {
insertfront(value);
return;
}

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


newNode->data = value;

struct Node* temp = head;


for (int i = 1; i < position - 1; i++) {
temp = temp->next;
}

newNode->next = temp->next;
temp->next = newNode;
printf("Inserted element %d at position %d\n", value, position);
}

void deletefront() {
if (head == NULL) {
printf("List is empty\n");
return;
}

struct Node* temp = head;


printf("Deleted element: %d\n", temp->data);
head = head->next;
free(temp);
}

void deleteend() {
if (head == NULL) {
printf("List is empty\n");
return;
}

if (head->next == NULL) {
printf("Deleted element: %d\n", head->data);
free(head);
head = NULL;
return;
}

struct Node* temp = head;


while (temp->next->next != NULL) {
temp = temp->next;
}

printf("Deleted element: %d\n", temp->next->data);


free(temp->next);
temp->next = NULL;
}

void deletepos(int position) {


if (head == NULL) {
printf("List is empty\n");
return;
}

if (position < 1 || position > Count()) {


printf("Invalid position\n");
return;
}

if (position == 1) {
deletefront();
return;
}

struct Node* temp = head;


struct Node* prev = NULL;

for (int i = 1; i < position; i++) {


prev = temp;
temp = temp->next;
}

prev->next = temp->next;
printf("Deleted element from position %d\n", position);
free(temp);
}

void display() {
if (head == NULL) {
printf("List is empty\n");
return;
}

struct Node* temp = head;


while (temp != NULL) {
printf("%d", temp->data);
if (temp->next != NULL) printf(" ");
temp = temp->next;
}
printf("\n");
}

int Count() {
int count = 0;
struct Node* temp = head;
while (temp != NULL) {
count++;
temp = temp->next;
}
return count;
}

void search(int value) {


struct Node* temp = head;
int position = 1;

while (temp != NULL) {


if (temp->data == value) {
printf("Element %d found at position %d\n", value, position);
return;
}
position++;
temp = temp->next;
}

printf("Element not found\n");


}

int main() {
int n, value, position;
char operation[20];

scanf("%d", &n);
while (n--) {
scanf("%s", operation);

if (strcmp(operation, "create") == 0) {
scanf("%d", &value);
create(value);
} else if (strcmp(operation, "insertfront") == 0) {
scanf("%d", &value);
insertfront(value);
} else if (strcmp(operation, "insertend") == 0) {
scanf("%d", &value);
insertend(value);
} else if (strcmp(operation, "insertpos") == 0) {
scanf("%d %d", &value, &position);
insertpos(value, position);
} else if (strcmp(operation, "deletefront") == 0) {
deletefront();
} else if (strcmp(operation, "deleteend") == 0) {
deleteend();
} else if (strcmp(operation, "deletepos") == 0) {
scanf("%d", &position);
deletepos(position);
} else if (strcmp(operation, "display") == 0) {
display();
} else if (strcmp(operation, "Count") == 0) {
printf("%d\n", Count());
} else if (strcmp(operation, "search") == 0) {
scanf("%d", &value);
search(value);
}
}
// Free memory
while (head != NULL) {
struct Node* temp = head;
head = head->next;
free(temp);
}

return 0;
}

Doubly Linked List Operations

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

struct Node {
int data;
struct Node* prev;
struct Node* next;
};

struct Node* createNode(int data) {


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}

struct Node* insertFront(struct Node* head, int data) {


struct Node* newNode = createNode(data);
if (head == NULL) {
return newNode;
}
newNode->next = head;
head->prev = newNode;
return newNode;
}

struct Node* insertEnd(struct Node* head, int data) {


struct Node* newNode = createNode(data);
if (head == NULL) {
return newNode;
}
struct Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
return head;
}

struct Node* insertPos(struct Node* head, int data, int pos) {


if (pos < 1) return head;
if (pos == 1) return insertFront(head, data);

struct Node* newNode = createNode(data);


struct Node* current = head;
int count = 1;

while (current != NULL && count < pos - 1) {


current = current->next;
count++;
}

if (current == NULL) return head;

newNode->next = current->next;
newNode->prev = current;
if (current->next != NULL) {
current->next->prev = newNode;
}
current->next = newNode;

return head;
}

struct Node* deleteFront(struct Node* head) {


if (head == NULL) return NULL;
struct Node* temp = head->next;
if (temp != NULL) {
temp->prev = NULL;
}
free(head);
return temp;
}

struct Node* deleteEnd(struct Node* head) {


if (head == NULL) return NULL;
if (head->next == NULL) {
free(head);
return NULL;
}

struct Node* current = head;


while (current->next != NULL) {
current = current->next;
}

current->prev->next = NULL;
free(current);
return head;
}

struct Node* deletePos(struct Node* head, int pos) {


if (head == NULL || pos < 1) return head;
if (pos == 1) return deleteFront(head);

struct Node* current = head;


int count = 1;

while (current != NULL && count < pos) {


current = current->next;
count++;
}

if (current == NULL) return head;

current->prev->next = current->next;
if (current->next != NULL) {
current->next->prev = current->prev;
}

free(current);
return head;
}
void display(struct Node* head) {
if (head == NULL) {
printf("Empty list\n");
return;
}
struct Node* current = head;
while (current->next != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("%d\n", current->data);
}

int count(struct Node* head) {


int count = 0;
struct Node* current = head;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}

void search(struct Node* head, int key) {


if (head == NULL) {
printf("Not found\n");
return;
}
struct Node* current = head;
int pos = 1;

while (current != NULL) {


if (current->data == key) {
printf("Found at position %d\n", pos);
return;
}
current = current->next;
pos++;
}
printf("Not found\n");
}
int main() {
struct Node* head = NULL;
int n, operation, data, pos;
scanf("%d", &n);

while (n--) {
scanf("%d", &operation);
switch (operation) {
case 1:
scanf("%d", &data);
head = createNode(data);
printf("Success\n");
break;
case 2:
scanf("%d", &data);
head = insertFront(head, data);
printf("Success\n");
break;
case 3:
scanf("%d", &data);
head = insertEnd(head, data);
printf("Success\n");
break;
case 4:
scanf("%d %d", &data, &pos);
head = insertPos(head, data, pos);
printf("Success\n");
break;
case 5:
head = deleteFront(head);
printf("Success\n");
break;
case 6:
head = deleteEnd(head);
printf("Success\n");
break;
case 7:
scanf("%d", &pos);
head = deletePos(head, pos);
printf("Success\n");
break;
case 8:
display(head);
break;
case 9:
printf("%d\n", count(head));
break;
case 10:
scanf("%d", &data);
search(head, data);
break;
}
}

// Free memory
while (head != NULL) {
struct Node* temp = head;
head = head->next;
free(temp);
}

return 0;
}

Concatenate Two Linked Lists

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

typedef struct Node {


int data;
struct Node* next;
} Node;

Node* createNode(int data) {


Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

Node* createList(int size) {


if (size == 0) return NULL;

int value;
scanf("%d", &value);
Node* head = createNode(value);
Node* current = head;

for (int i = 1; i < size; i++) {


scanf("%d", &value);
current->next = createNode(value);
current = current->next;
}

return head;
}

Node* concatenateLists(Node* list1, Node* list2) {


if (list1 == NULL) return list2;
if (list2 == NULL) return list1;

Node* current = list1;


while (current->next != NULL) {
current = current->next;
}
current->next = list2;

return list1;
}

void printList(Node* head) {


if (head == NULL) {
printf("Empty List\n");
return;
}

Node* current = head;


while (current != NULL) {
printf("%d", current->data);
if (current->next != NULL) {
printf(" ");
}
current = current->next;
}
printf("\n");
}

void freeList(Node* head) {


Node* current = head;
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp);
}
}

int main() {
int n, m;
scanf("%d %d", &n, &m);

Node* list1 = createList(n);


Node* list2 = createList(m);

Node* concatenatedList = concatenateLists(list1, list2);


printList(concatenatedList);

freeList(concatenatedList);
return 0;
}

Linked List Operations

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

struct Node {
int data;
struct Node* next;
};

struct Node* head = NULL;

struct Node* createNode(int data) {


struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

void create(int n) {
head = NULL;
struct Node* temp;
int data;

for(int i = 0; i < n; i++) {


scanf("%d", &data);
struct Node* newNode = createNode(data);
if(head == NULL) {
head = newNode;
temp = head;
} else {
temp->next = newNode;
temp = newNode;
}
}

if(n == 0) {
printf("Empty List\n");
return;
}

printf("List created: ");


display();
}

void reverse() {
struct Node *prev = NULL, *current = head, *next = NULL;

while(current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
printf("Reversed list: ");
display();
}

void merge() {
int n;
scanf("%d", &n);

struct Node* temp = head;


if(temp != NULL) {
while(temp->next != NULL) {
temp = temp->next;
}
}

int data;
for(int i = 0; i < n; i++) {
scanf("%d", &data);
struct Node* newNode = createNode(data);
if(head == NULL) {
head = newNode;
temp = head;
} else {
temp->next = newNode;
temp = newNode;
}
}

printf("Merged list: ");


display();
}

void sort() {
struct Node *i, *j;
int temp;

for(i = head; i != NULL; i = i->next) {


for(j = i->next; j != NULL; j = j->next) {
if(i->data > j->data) {
temp = i->data;
i->data = j->data;
j->data = temp;
}
}
}

printf("Sorted list: ");


display();
}

void display() {
struct Node* temp = head;

if(temp == NULL) {
printf("Empty List\n");
return;
}

while(temp != NULL) {
printf("%d", temp->data);
if(temp->next != NULL)
printf(" ");
temp = temp->next;
}
printf("\n");
}

int count() {
struct Node* temp = head;
int count = 0;

while(temp != NULL) {
count++;
temp = temp->next;
}

return count;
}

int main() {
int choice, n;
scanf("%d", &choice);

switch(choice) {
case 1:
scanf("%d", &n);
create(n);
break;

case 2:
scanf("%d", &n);
create(n);
reverse();
break;

case 3:
scanf("%d", &n);
create(n);
merge();
break;

case 4:
scanf("%d", &n);
create(n);
sort();
break;

case 5:
scanf("%d", &n);
create(n);
display();
break;

case 6:
scanf("%d", &n);
create(n);
printf("Number of nodes: %d\n", count());
break;
}

// Free memory
struct Node* temp;
while(head != NULL) {
temp = head;
head = head->next;
free(temp);
}
return 0;
}

Polynomial Addition

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

#define MAX_DEGREE 11

void addPolynomials(int n1, int coef1[], int exp1[],


int n2, int coef2[], int exp2[]) {
int result[MAX_DEGREE] = {0};

// Add terms from first polynomial


for(int i = 0; i < n1; i++) {
result[exp1[i]] += coef1[i];
}

// Add terms from second polynomial


for(int i = 0; i < n2; i++) {
result[exp2[i]] += coef2[i];
}

// Find highest degree


int maxDegree = MAX_DEGREE - 1;
while(maxDegree >= 0 && result[maxDegree] == 0) {
maxDegree--;
}

// Handle zero polynomial


if(maxDegree < 0) {
printf("0\n");
return;
}

// Print first term (handle sign)


if(result[maxDegree] < 0) {
printf("-");
}
if(abs(result[maxDegree]) != 1 || maxDegree == 0) {
printf("%d", abs(result[maxDegree]));
}
if(maxDegree > 0) {
printf("x");
if(maxDegree > 1) {
printf("^%d", maxDegree);
}
}

// Print remaining terms


for(int i = maxDegree - 1; i >= 0; i--) {
if(result[i] == 0) continue;

printf("%c", result[i] > 0 ? '+' : '-');


if(abs(result[i]) != 1 || i == 0) {
printf("%d", abs(result[i]));
}
if(i > 0) {
printf("x");
if(i > 1) {
printf("^%d", i);
}
}
}
printf("\n");
}

int main() {
int n1, n2;
int coef1[10], exp1[10];
int coef2[10], exp2[10];

// Read first polynomial


scanf("%d", &n1);
for(int i = 0; i < n1; i++) {
scanf("%d %d", &coef1[i], &exp1[i]);
}

// Read second polynomial


scanf("%d", &n2);
for(int i = 0; i < n2; i++) {
scanf("%d %d", &coef2[i], &exp2[i]);
}

addPolynomials(n1, coef1, exp1, n2, coef2, exp2);

return 0;
}

You might also like