Previous versions of this question
Changes
I added these operations:
Pop_back
Pop_front
You are not allowed to insert_sll at the front or back, but only in position i such that 0 < i < n=size-1.
I also tested the functions, so everything is working!
Thanks in advance for any improvement ideas!
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* head = NULL;
Node* tail = NULL;
Node* create_node(int elm) {
Node* node = malloc(sizeof * node), *exits = NULL;
if (!node) return exits;
node->data = elm;
node->next = NULL;
return node;
}
int is_empty_sll() { //O(1)
return head == NULL;
}
int size_sll() { //O(n)
int count = 0;
Node* last = head;
while (last) {
count += 1;
last = last->next;
}
return count;
}
Node* node_k_sll(int k) { // 0-based index
int n = size_sll() - 1;
if (!is_empty_sll() && (k >= 0 && k <= n)) {
int i = 0;
Node* node = head;
while (i != k) {
i += 1;
node = node->next;
}
return node;
}
else {
printf("Out of Index");
Node* node = NULL;
return node;
}
}
void append_sll(int elm) { //O(1)
Node* cur = create_node(elm);
if (!head) {
head = cur;
}
else {
tail->next = cur;
}
tail = cur;
}
void prepend_sll(int elm) {
Node* updated_head = create_node(elm);
if (!head) {
head = updated_head;
tail = head;
}
else {
updated_head->next = head;
head = updated_head;
}
}
void insert_sll(int elm, int i) {
if (!is_empty_sll()) {
int k = 1, size = size_sll(); // we don't prepend, so K > 0
Node* cur = create_node(elm);
if (!head) {
head = cur;
}
else {
Node* last = head;
if (i > 1 && i < size) { // 1 < i < size | 1:prepend, n:append
while (k != i) {
k += 1;
last = last->next;
}
cur->next = last->next;
last->next = cur;
}
else {
printf("Out of Index");
}
}
}
}
void delete_sll(int elm) {
int n = size_sll();
Node* node = head;
if (head->data == elm) {
head = head->next;
free(node);
}
else {
Node* prev = head;
for (int i = 0; i < n; i++) {
if (node->data != elm) {
prev = node;
node = node->next;
}
else {
break;
}
}
prev->next = node->next;
free(node);
}
}
int search_sll(int elm) { //O(n)
if (!is_empty_sll()) {
int i, n = size_sll();
Node* last = head;
for (i = 0; i < n; i++) {
if (last->data != elm) {
last = last->next;
}
else {
break;
}
}
return i;
}
}
void swap_sll(int i, int j) {//O(n) --swap value of position i with j
Node* node_i = node_k_sll(i);
Node* node_j = node_k_sll(j);
int temp = node_i->data;
node_i->data = node_j->data;
node_j->data = temp;
}
void print_sll() {
Node* trav = head;
while (trav) {
printf("%d ", trav->data);
trav = trav->next;
}
printf("\n");
}
void reverse_sll() {
if (!is_empty_sll()) {
Node* prev = head;
Node* cur = head->next, * next_node = cur;
while (next_node) {
next_node = cur->next;
cur->next = prev;
prev = cur;
cur = next_node;
}
head->next = next_node;
Node* temp = head;
head = tail;
tail = temp;
}
}
//void reverse_sll() {
// Node* prev = NULL, *cur = head, *next;
// while (cur) {
// next = cur->next;
// cur->next = prev;
// prev = cur;
// cur = next;
// }
// head = prev;
// Node* temp = head;
// head = prev;
// prev = temp;
//}
void clear_sll() { //O(n)
while (head) {
Node* temp = head;
head = head->next;
free(temp);
}
printf("List Cleared!\n");
}
Node* get_tail() {
// Node* tail = head;
// while (tail->next != NULL) {
// tail = tail->next;
// }
return tail;
}
void rotate_sll(int k) {
int size = size_sll();
Node* tail = get_tail();
Node* k_node = node_k_sll(k);
tail->next = head;
for (int i = 0; i < size; i++) {
printf("%d ", k_node->data);
k_node = k_node->next;
}
tail->next = NULL;
printf("\n");
}
void pop_front_sll() {
Node* node = head;
head = head->next;
free(node);
}
void pop_back_sll() {
int size = size_sll();
int elm = node_k_sll(size - 1)->data;
delete_sll(elm);
}
// void sort_sll() {// //different algorithms
// }
int main() {
prepend_sll(-13);
append_sll(1);
append_sll(2);
append_sll(4);
print_sll();
insert_sll(3, 2);
print_sll();
prepend_sll(0);
print_sll();
printf("size: %d\n", size_sll());
printf("index of 3 is: %d\n", search_sll(3));
delete_sll(2);
print_sll();
swap_sll(0, 1);
print_sll();
reverse_sll();
print_sll();
append_sll(0);
append_sll(-1);
print_sll();
rotate_sll(2);
pop_front_sll();
print_sll();
pop_back_sll();
print_sll();
clear_sll();
print_sll();
return 0;
}
