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

Implement basic form of singly linked list

• 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

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 {
new_node->next = list;
list = new_node;
}
}
``````
``````// Add - add ascending order

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;
}
if (cur != NULL) {
new_node->next = cur;
prev->next = new_node;
}
else {
prev->next = new_node;
}
}
}
}
``````
``````// Add - add only unique value
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 `cur`and `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

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 {
new_node->next = list;
list = new_node;
}
}

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;
}
if (cur != NULL) {
new_node->next = cur;
prev->next = new_node;
}
else {
prev->next = new_node;
}
}
}
}

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 = { 2, 4, 6, 8, 1, 3, 5, 7, 9 };
int arr_duplicated = { 8, 1, 3, 2, 4, 6, 8, 1, 3, 5, 7, 9, 2, 4, 6, 5, 7, 9 };
int arr_rmv = { 2, 9, 8, 100 };

init();
for (int i = 0; i < sizeof(arr) / sizeof(arr); ++i) {
}
traverse();

init();
for (int i = 0; i < sizeof(arr) / sizeof(arr); ++i) {
}
traverse();

init();
for (int i = 0; i < sizeof(arr_duplicated) / sizeof(arr_duplicated); ++i) {
}
traverse();

// Remove specific values in list
for (int i = 0; i < sizeof(arr_rmv) / sizeof(arr_rmv); ++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
``````

Updated on