Last active
November 1, 2020 15:06
-
-
Save sriramster/393d25dc2adbf363c09d5bdb6a03b989 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Header only implementation of linked list, & some operations | |
| #pragma once | |
| volatile size_t sz; | |
| typedef struct _node { | |
| int data; | |
| struct Node * next; | |
| } __attribute__((aligned)) Node; | |
| size_t get_size() { | |
| return sz; | |
| } | |
| Node * _new(int data) { | |
| Node * new = (Node *)malloc(sizeof(Node)); | |
| new->data = data; | |
| new->next = NULL; | |
| return new; | |
| } | |
| // Insert at the head if NULL or insert after. | |
| Node * _insert_last(Node * head, int data) { | |
| if (head == NULL) | |
| head = _new(data); | |
| else { | |
| Node * tmp = head; | |
| while (tmp->next != NULL) | |
| tmp = tmp->next; | |
| tmp->next = _new(data); | |
| } | |
| sz++; | |
| return head; | |
| } | |
| Node * _insert_first(Node * head, int data) { | |
| if (head == NULL) | |
| head = _new(data); | |
| else { | |
| Node * tmp = head->next; | |
| head->next = _new(data); | |
| head->next->next = tmp; | |
| } | |
| return head; | |
| } | |
| void _delete_last(Node * head) { | |
| if (head == NULL) | |
| return; | |
| else { | |
| Node * tmp = head; | |
| while (tmp->next != NULL) | |
| tmp = tmp->next; | |
| free(tmp); | |
| } | |
| } | |
| void _delete_pos(Node * head, int pos) { | |
| if (head == NULL) | |
| return; | |
| Node * tmp = head; | |
| if (pos == 0) { | |
| head = tmp->next; | |
| free(tmp); | |
| sz--; | |
| return; | |
| } | |
| else { | |
| // Find the prev node to delete, assuming 0 is also a pos | |
| for (i = 0 && tmp != NULL ; i < pos - 1 ; i++) | |
| tmp = tmp->next; | |
| if (tmp == NULL || tmp->next == NULL) | |
| return; | |
| Node * next = tmp->next->next; | |
| // Delete the node | |
| free(tmp->next); | |
| // Re-link the 'links' | |
| tmp->next = next; | |
| } | |
| sz--; | |
| return head; | |
| } | |
| void _delete_last(Node * head, int pos) { | |
| if (head == NULL) | |
| return; | |
| else { | |
| Node * tmp = head; | |
| while (tmp->next != NULL) | |
| tmp = tmp->next; | |
| tmp->next = new_node(data); | |
| } | |
| sz--; | |
| return head; | |
| } | |
| Node * _rev(Node * head, approach_t approach) { | |
| switch(approach) { | |
| case ITERATIVE: | |
| return _rev_iterative(head, sz); | |
| case KNOWN: | |
| return _rev_with_size(head, sz); | |
| case UNKNOWN: | |
| return _rev_without_size(head); | |
| default: | |
| return NULL; | |
| } | |
| return NULL; | |
| } | |
| Node * _rev_iterative(Node ** head) { | |
| // Node is empty nothing to reverse | |
| if (head == NULL) | |
| return NULL; | |
| if (head->next == NULL) | |
| return head; | |
| Node * cur = *head; | |
| Node * pre = NULL; | |
| Node * next = NULL; | |
| /* |prev|cur|next| | |
| |cur| -> head | |
| |cur->next| | |
| */ | |
| while (cur->next != NULL) { | |
| next = cur->next; | |
| cur->next = prev; | |
| // Re-linking back | |
| prev = cur; | |
| cur = next; | |
| } | |
| } | |
| Node * _rev_recursive(Node * head) { | |
| // Node is empty nothing to reverse | |
| if (head == NULL) | |
| return NULL; | |
| if (head->next == NULL) | |
| return head; | |
| Node * rest = _rev_recursive(head->next); | |
| // Re-link head to rest and then make head->next to signify end | |
| // of list | |
| /* |head|n1|n2|...|nnull| | |
| |head->next == n1->next = head | commutative relink with head | |
| */ | |
| head->next->next = head; | |
| head->next = NULL; | |
| return rest; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment