Skip to content

Instantly share code, notes, and snippets.

@lobster1234
Last active April 22, 2020 07:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lobster1234/301849aae348d48c88ad2280e63f51b7 to your computer and use it in GitHub Desktop.
Save lobster1234/301849aae348d48c88ad2280e63f51b7 to your computer and use it in GitHub Desktop.
Plain vanilla singly linked list
#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