[Algorithm](EN) Singly Linked List Implementation in C/C++

Implement basic form of singly linked list


Environment and Prerequisite

  • C++


What is Singly Linked List?

Concept

  • It is a data structure which have datas in one node and point to other node sequentially.
  • It is an advantage compared with array in insertion and deletion. However accessing takes O(n).
  • It is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.



Implementation

Common

  • list is a head of list
  • You can modify insertion, deletion and finding codes if you want.
#include <stdio.h>
#include <stdlib.h>

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

// Global list
Node * list;


Insertion/Delettion Common

  • It is easy to implement if we consider the head(or first element) of list
  • It is helpful if there are cur pointer which points current node and prev pointer which points previous node of current node. They are helpful in insertion and deletion.
  • In deletion, if there is a node that we want to delete, then it returns true. If not, then return false.


Insertion

  • Like below picture, find the position of new node. Then, point new node’s next to next node and previous node’s next to new node.
  • There are 3 types of functions.
  • add: add just new node
  • ascending_order_add: add node in middle(by ascending order)
  • add_unique: add only unique node



// Add - one by one
void add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	// Check first element
	if (list == NULL) {
		list = new_node;
	}
	else {
		// Add new node to head
		new_node->next = list;
		list = new_node;
	}
}

// Add - add ascending order
void ascending_order_add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {

		Node * cur = list;
		Node * prev = NULL;

		// If first element is larger than key
		if (cur->data > new_node->data) {
			new_node->next = cur;
			list = new_node;
		}
		// Other cases
		else {
			while (cur != NULL && cur->data < new_node->data) {
				prev = cur;
				cur = cur->next;
			}
			// Add in middle
			if (cur != NULL) {
				new_node->next = cur;
				prev->next = new_node;
			}
			// Add to end
			else {
				prev->next = new_node;
			}
		}
	}
}

// Add - add only unique value
void add_unique(int key) {
	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {
		Node * cur = list;

		// Duplication check
		while (cur != NULL) {
			if (cur->data == key) {
				return;
			}
			cur = cur->next;
		}

		new_node->next = list;
		list = new_node;
	}
}


Deletion

  • Like below picture, find the position of node which will be deleted. Then, points previous node’s next to current node’s(which will be deleted) next.
  • Use curand prev pointers.



// Remove
bool remove(int key) {

	if (list == NULL) {
		return false;
	}

	if (list->data == key) {
		Node * cur = list;
		list = list->next;
		free(cur);
		return true;
	}
	else {
		Node * cur = list->next;
		Node * prev = list;
		while (cur != NULL && cur->data != key) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}


Code

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

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

// Global list
Node * list;

// Init
void init() {

	if (list == NULL) {
		return;
	}
	else {
		Node * cur;
		cur = list;

		while (cur != NULL) {
			list = cur->next;
			free(cur);
			cur = list;
		}
	}
}

// Add - one by one
void add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	// Check first element
	if (list == NULL) {
		list = new_node;
	}
	else {
		// Add new node to head
		new_node->next = list;
		list = new_node;
	}
}

// Add - add ascending order
void ascending_order_add(int key) {

	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {

		Node * cur = list;
		Node * prev = NULL;

		// If first element is larger than key
		if (cur->data > new_node->data) {
			new_node->next = cur;
			list = new_node;
		}
		// Other cases
		else {
			while (cur != NULL && cur->data < new_node->data) {
				prev = cur;
				cur = cur->next;
			}
			// Add in middle
			if (cur != NULL) {
				new_node->next = cur;
				prev->next = new_node;
			}
			// Add to end
			else {
				prev->next = new_node;
			}
		}
	}
}

// Add - add only unique value
void add_unique(int key) {
	Node * new_node = (Node*)malloc(sizeof(Node));
	new_node->data = key;
	new_node->next = NULL;

	if (list == NULL) {
		list = new_node;
	}
	else {
		Node * cur = list;

		// Duplication check
		while (cur != NULL) {
			if (cur->data == key) {
				return;
			}
			cur = cur->next;
		}

		new_node->next = list;
		list = new_node;
	}
}

// Remove
bool remove(int key) {

	if (list == NULL) {
		return false;
	}

	if (list->data == key) {
		Node * cur = list;
		list = list->next;
		free(cur);
		return true;
	}
	else {
		Node * cur = list->next;
		Node * prev = list;
		while (cur != NULL && cur->data != key) {
			prev = cur;
			cur = cur->next;
		}

		if (cur == NULL) return false;

		prev->next = cur->next;
		free(cur);
		return true;
	}
}

// Traverse
void traverse() {

	Node * cur = list;
	while (cur != NULL) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");

}

int main() {

	int arr[9] = { 2, 4, 6, 8, 1, 3, 5, 7, 9 };
	int arr_duplicated[18] = { 8, 1, 3, 2, 4, 6, 8, 1, 3, 5, 7, 9, 2, 4, 6, 5, 7, 9 };
	int arr_rmv[4] = { 2, 9, 8, 100 };


	// Add to list 1
	init();
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
		add(arr[i]);
	}
	printf("After add(normal): ");
	traverse();


	// Add to list 2
	init();
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
		ascending_order_add(arr[i]);
	}
	printf("After add(ascending): ");
	traverse();


	// Add to list 3
	init();
	for (int i = 0; i < sizeof(arr_duplicated) / sizeof(arr_duplicated[0]); ++i) {
		add_unique(arr_duplicated[i]);
	}
	printf("After add(unique): ");
	traverse();


	// Remove specific values in list
	for (int i = 0; i < sizeof(arr_rmv) / sizeof(arr_rmv[0]); ++i) {
		remove(arr_rmv[i]);
	}
	printf("After remove: ");
	traverse();

	return 0;

}

Result

After add(normal): 9 7 5 3 1 8 6 4 2
After add(ascending): 1 2 3 4 5 6 7 8 9
After add(unique): 9 7 5 6 4 2 3 1 8
After remove: 7 5 6 4 3 1


Reference

Read More

[Java] API 테스트를 위한 Rest Assured 준비와 예제

Published on January 28, 2024

[Java](EN) Rest Assured Setting and Example for API Test

Published on January 28, 2024

[AWS] Policy에서 AWS IAM ARN이 고유 식별자(Unique Identifier)로 바뀌는 이유와 해결 방법

Published on January 01, 2024