(DSL7) Linked Lists

Singly Linked List

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

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

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

void insertNode(struct Node **head, int data)
{
	struct Node *newNode = createNode(data);
	if (*head == NULL)
	{
		*head = newNode;
		return;
	}
	struct Node *temp = *head;
	while (temp->next != NULL)
	{
		temp = temp->next;
	}
	temp->next = newNode;
}

void deleteNode(struct Node **head, int data)
{
	struct Node *temp = *head;
	struct Node *prev = NULL;

	if (temp != NULL && temp->data == data)
	{
		*head = temp->next;
		free(temp);
		return;
	}

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

	if (temp == NULL)
	{
		printf("Element %d not found in the list.\n", data);
		return;
	}

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

void traverse(struct Node *head)
{
	struct Node *temp = head;
	while (temp != NULL)
	{
		printf("%d ", temp->data);
		temp = temp->next;
	}
	printf("\n");
}

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

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

	insertNode(&head, 1);
	insertNode(&head, 2);
	insertNode(&head, 3);

	printf("Linked list: ");
	traverse(head);

	insertNode(&head, 4);
	printf("After insertion: ");
	traverse(head);

	deleteNode(&head, 2);
	printf("After deletion: ");
	traverse(head);

	freeList(head);
}

Doubly Linked List

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

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

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

void insertNode(struct Node **head, int data)
{
	struct Node *newNode = createNode(data);
	if (*head == NULL)
	{
		*head = newNode;
		return;
	}
	struct Node *temp = *head;
	while (temp->next != NULL)
	{
		temp = temp->next;
	}
	temp->next = newNode;
	newNode->prev = temp;
}

void deleteNode(struct Node **head, int data)
{
	struct Node *temp = *head;

	while (temp != NULL && temp->data != data)
		temp = temp->next;

	if (temp == NULL)
	{
		printf("Element %d not found in the list.\n", data);
		return;
	}

	if (temp->prev != NULL)
		temp->prev->next = temp->next;
	if (temp->next != NULL)
		temp->next->prev = temp->prev;

	free(temp);
}

void traverse(struct Node *head)
{
	struct Node *temp = head;
	while (temp != NULL)
	{
		printf("%d ", temp->data);
		temp = temp->next;
	}
	printf("\n");
}

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

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

	insertNode(&head, 1);
	insertNode(&head, 2);
	insertNode(&head, 3);

	printf("Linked list: ");
	traverse(head);

	insertNode(&head, 4);
	printf("After insertion: ");
	traverse(head);

	deleteNode(&head, 2);
	printf("After deletion: ");
	traverse(head);

	freeList(head);
}

Circular Linked List

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

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

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

void insertNode(struct Node **head, int data)
{
	struct Node *newNode = createNode(data);
	if (*head == NULL)
	{
		newNode->next = newNode;
		*head = newNode;
		return;
	}
	struct Node *temp = *head;
	while (temp->next != *head)
	{
		temp = temp->next;
	}
	temp->next = newNode;
	newNode->next = *head;
}

void deleteNode(struct Node **head, int data)
{
	struct Node *temp = *head;
	struct Node *prev = NULL;

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

	do
	{
		if (temp->data == data)
		{
			if (prev != NULL)
			{
				prev->next = temp->next;
			}
			if (temp == *head)
			{
				*head = (*head)->next;
			}
			free(temp);
			return;
		}
		prev = temp;
		temp = temp->next;
	} while (temp != *head);

	printf("Element %d not found in the list.\n", data);
}

void traverse(struct Node *head)
{
	struct Node *temp = head;
	if (temp != NULL)
	{
		do
		{
			printf("%d ", temp->data);
			temp = temp->next;
		} while (temp != head);
	}
	printf("\n");
}

void freeList(struct Node **head)
{
	struct Node *temp;
	while (*head != NULL && (*head)->next != *head)
	{
		temp = (*head)->next;
		(*head)->next = temp->next;
		free(temp);
	}
	free(*head);
	*head = NULL;
}

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

	insertNode(&head, 1);
	insertNode(&head, 2);
	insertNode(&head, 3);

	printf("Circular linked list: ");
	traverse(head);

	insertNode(&head, 4);
	printf("After insertion: ");
	traverse(head);

	deleteNode(&head, 2);
	printf("After deletion: ");
	traverse(head);

	freeList(&head);
}