Last active
April 22, 2020 07:31
-
-
Save lobster1234/301849aae348d48c88ad2280e63f51b7 to your computer and use it in GitHub Desktop.
Plain vanilla singly linked list
This file contains hidden or 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
#include<stdio.h> | |
#include<stdlib.h> | |
/* | |
Coding a C linked list after 1995. It took a global pandemic. | |
*/ | |
/* | |
First off, lets create a node struct called Node | |
*/ | |
typedef struct Node | |
{ | |
int data; | |
struct Node* next; | |
} Node; | |
/* | |
Insert a new node at the tail and return the head, like enqueue | |
*/ | |
Node* insert_tail(Node* head, Node* new_node); | |
/* | |
Insert a new node at the head and return the head, like push | |
*/ | |
Node* insert_head(Node* head, Node* new_node); | |
/* | |
Return the size of this list | |
*/ | |
int size(Node* head); | |
/* | |
Print this list | |
*/ | |
void print_list(Node* head); | |
/* | |
Print the list in reverse | |
*/ | |
void print_reverse(Node* head); | |
/* | |
Delete the head (pop) | |
*/ | |
Node* delete_head(Node *head); | |
/* | |
Free the memory | |
*/ | |
void free_list(Node* head); | |
int main(void) | |
{ | |
//lets create a list | |
Node* list = NULL; | |
//lets create 10 nodes and insert them at the tail (enqueue) | |
for (int i = 0; i < 10; i++) | |
{ | |
Node* node = malloc(sizeof(Node)); | |
node -> data = i; | |
node -> next = NULL; | |
list = insert_tail(list, node); | |
} | |
//now we print this list | |
print_list(list); | |
//now lets insert at the head (push) | |
for (int i = 0; i < 10; i++) | |
{ | |
Node* node = malloc(sizeof(Node)); | |
node -> data = i*10; | |
node -> next = NULL; | |
list = insert_head(list, node); | |
} | |
//get the size of the list | |
int count = size(list); | |
printf("The list has a total of %i nodes\n", count); | |
//print again | |
printf("Here is the list - \n"); | |
print_list(list); | |
//print the list in reverse | |
printf("Here is the list in reverse - \n"); | |
print_reverse(list); | |
printf("\n"); | |
//lets delete the head | |
printf("We are deleting the head now - \n"); | |
list = delete_head(list); | |
print_list(list); | |
//we free the memory here | |
free_list(list); | |
} | |
Node* insert_head(Node* head, Node* new_node) | |
{ | |
//lets check if the head is NULL, if so, then this is the head | |
if (head == NULL) | |
{ | |
printf("The head is null, inserting this node [%i] as head \n", new_node -> data); | |
head = new_node; | |
return head; | |
} | |
//we insert at the head, so this new node's next points to the current head | |
//and it becomes the new head | |
//lets check if the new_node is not null | |
if(new_node != NULL) | |
{ | |
printf("Inserting [%i] at the head [%i]\n", new_node -> data, head -> data); | |
new_node -> next = head; | |
} | |
else | |
{ | |
printf("Cannot insert a NULL node at the head \n"); | |
} | |
return new_node; | |
} | |
Node* delete_head(Node* head) | |
{ | |
//if head is null or head is the only node | |
if(head == NULL) | |
{ | |
return NULL; | |
} | |
else if(head -> next == NULL) | |
{ | |
free(head); | |
return NULL; | |
} | |
else | |
{ | |
//we store the head.next in a variable | |
Node* temp = head -> next; | |
free(head); //we cannot let it float in the ether | |
return temp; | |
} | |
} | |
Node* insert_tail(Node* head, Node* new_node) | |
{ | |
//lets check if the head is NULL, if so then this node is head | |
if(head == NULL) | |
{ | |
printf("The head is null, inserting this node [%i] as head \n", new_node -> data); | |
head = new_node; | |
return head; | |
} | |
//lets create a temp pointing to the head | |
Node* current = head; | |
//we insert node_to_insert at the tail | |
//we are assuming (heh) that node_to_insert -> next is NULL | |
while(1) | |
{ | |
if(current -> next == NULL) | |
{ | |
printf("We are at the tail [%i], inserting [%i]\n", current -> data, new_node -> data); | |
//insert here | |
current -> next = new_node; | |
break; | |
} | |
else | |
{ | |
//we keep moving on towards the tail | |
current = current -> next; | |
} | |
} | |
return head; | |
} | |
int size(Node* head) | |
{ | |
if(head == NULL) | |
{ | |
return 0; | |
} | |
else | |
{ | |
return 1 + size(head -> next); | |
} | |
} | |
void print_list(Node* head) | |
{ | |
if(head == NULL) | |
{ | |
printf(" \n"); | |
} | |
else | |
{ | |
printf(" [%i] ", head -> data); | |
print_list(head -> next); //recursive call is _after_ printf, so we are stacking printfs | |
} | |
} | |
void print_reverse(Node* head) | |
{ | |
if(head != NULL) | |
{ | |
print_reverse(head -> next); //keep buffering and stacking the calls | |
printf(" [%i] ", head ->data); //open the flood gates | |
} | |
} | |
void free_list(Node* head) | |
{ | |
//to free the memory we cant orphan anything, so we store | |
//the next in a temp variable as we free it | |
//we can check any leaks with valgrind | |
if(head == NULL) | |
{ | |
//we got a dud | |
return; | |
} | |
printf("Freeing nodes .."); | |
while(1) | |
{ | |
if(head -> next == NULL) | |
{ | |
printf("[%i]\n", head -> data); | |
free(head); | |
break; | |
} | |
else | |
{ | |
Node* temp = head -> next; | |
printf(" [%i] ", head -> data); | |
free(head); | |
head = temp; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment