Algorithm Review 2

0. Time complexity table

1. Singly Linked List

💡Key Idea
The List structure has only one pointer named head. The head pointer points to the head node, which is linked to other nodes.
Each node has data and next field. The types are int and pointer of the node structure each.

1) node.h

#pragma once

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

typedef Node* pNode;

2) node.c

#include "node.h"
#include <stdio.h>

pNode new_node(int data) {
	pNode new_node = malloc(sizeof(*new_node));

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

	return new_node;
}

3) list.h

#pragma once
#include "node.h"

typedef struct List {
	pNode head;
}List;

typedef List* pList;

3) list.c

#include "list.h"
#include <stdio.h>

void new_list(pList plist) {
	plist->head = NULL;
}

void insert_node_at_end(pList plist, int data) {
	pNode pnode = new_node(data);

	// The case that list is empty
	if (!plist->head) {
		plist->head = pnode;
		return;
	}

	pNode current = plist->head;

	// Move to the proper position
	while (current->next != NULL) {
		current = current->next;
	}
	current->next = pnode;
}

void insert_node_in_ascending_order(pList plist, int data) {
	pNode pnode = new_node(data);

	if (!plist->head) {
		plist->head = pnode;
		return;
	}

	pNode current = plist->head;
	pNode pprev = NULL;

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

	// insert at the end
	if (current == NULL) {
		pprev->next = pnode;
	}
	else {
		// insert at the front or in the middle
		if (pprev == NULL) {
			// insert at front
			pnode->next = plist->head;
			plist->head = pnode;
		}
		else {
			// insert in the middle
			pprev->next = pnode;
			pnode->next = current;
		}
	}
}

void print_list(List list) {
	pNode current = list.head;

	// traverse the list while printing the data
	while (current != NULL) {
		printf("%d\n", current->data);
		current = current->next;
	}
}

4) main.c

#include "list.h"
#include <stdio.h>

int main() {
	List my_list;
	new_list(&my_list);

	insert_node_in_ascending_order(&my_list, 3);
	insert_node_in_ascending_order(&my_list, 5);
	insert_node_in_ascending_order(&my_list, 1);
	insert_node_in_ascending_order(&my_list, 2);

	print_list(&my_list);
}

2. Circular Queue using Array

💡Key Concept
"Circular" means that the next element after the rear becomes the front. To implement this using an array, variables for the front and rear indices are needed.
By using these variables in the enqueue and dequeue functions, we can add and remove elements from the queue properly.
It is also important to use modifying character (%) to represent the circular system of the queue.

#define N 5
#include <stdio.h>

int queue[N];
int front = -1, rear = -1;

void enqueue(int x) {
	if (front == -1 && rear == -1) {
		// starting point of the queue
		front = 0;
		rear = 0;
		queue[rear] = x;
	}
	else if ((rear + 1) % N == front) {
		printf("Queue is full.\n");
	}
	else {
		// General insertion
		rear = (rear + 1) % N;
		queue[rear] = x;
	}
}

void dequeue() {
	if (front == -1 && rear == -1) {
		printf("Queue is empty.\n");
	}
	else if (front == rear) {
		// when queue becomes empty after dequeuing
		// initialize the indices
		front = -1;
		rear = -1;
	}
	else {
		// General removal
		printf("%d dequeued.\n", queue[front]);
		front = (front + 1) % N;
	}
}

int main() {
	enqueue(2);
	enqueue(-1);
	enqueue(5);
	enqueue(6);
	enqueue(7);
	dequeue();
}

3. Circular Queue using Singly Linked List

💡Key Concept
Unike a Singly Linked List, the Circular Queue structure has front and rear index fields. During the insertion and deletion, sine the rear node's next field points back to the front node, the circular structure can be created.

#include "list.h"

void new_list(List* my_list) {
	my_list->front = NULL;
	my_list->rear = NULL;
}

void enqueue(List* queue, int data) {
	struct Node* node = new_node(data);


	if (queue->front == NULL) {
		// if the queue is empty
		queue->front = node;
		queue->rear = node;

		queue->rear->next = queue->front;

		return;
	}
	// insert the node
	node->next = queue->front; // make circular structure
	queue->rear->next = node; // add to the rear
	queue->rear = node;
}

void dequeue(List* my_list) {
	if (my_list->front == NULL) {
		printf("Queue is empty.");
		return;
	} 

	if (my_list->front == my_list->rear) {
		// only one element in the queue
		free(my_list->front);
		my_list->front = NULL;
		my_list->rear = NULL;
	}

	else {
		struct Node* pnext = my_list->front->next;

		my_list->rear->next = pnext;

		free(my_list->front);

		my_list->front = pnext;
	}
}

void printQueue(List* my_list) {
	if (my_list->front == NULL) {
		printf("Queue is empty.");
		return;
	}

	struct Node* current = my_list->front;
	while (current->next != my_list->front) {
		printf("%d ", current->data);
		current = current->next;
	}
	printf("%d", my_list->rear->data);
}