// Jake's LL demo
// But now Henry Hickman is here!
// Add integers to a LL.
// Print the entire structure
#include <stdio.h>
#include <stdlib.h>
struct node {
// the data! Also called the payload.
int data;
// a pointer to the next node in the LL.
struct node *next;
};
// A function that creates a struct node, with some data that's passed in.
// Returns a pointer to the node on the heap.
// we do this to clean up main.
struct node *create_node(int data_to_add) {
// Allocate memory on the heap
// we'll use sizeof(struct node) to get the exact memory required
printf("Allocating %lu bytes on the heap for a new node\n", sizeof(struct node)); // keep in mind struct packing might make the answer surprise you
struct node *new_node = malloc(sizeof(struct node));
// initialises the new node's fields
// The aarrow oeprator -> is equivalent to a derefence then a field access: (*new_node).data = data_to_add;
new_node->data = data_to_add;
new_node->next = NULL; // NULL is a memory address reserved, that can't be dereferenced. usually at 0x000000
// we return the address of this node on the heap
return new_node;
}
void print_linked_list(struct node *head) {
// we need a current node that iterates through the list
// starting from the head node, we don't actually want to move the 'head' pointer.
// we are creating a pointer to refer to where head was pointing to...
struct node *current = head;
printf("Linked list: ");
// we loop. We loop as long as the current node is NOT at the NULL pointer.
while (current != NULL) {
printf("%d->", current->data);
current = current->next;
}
printf("NULL\n");
}
//Free all nodes in the linked list
void free_all_nodes(struct node *head) {
struct node *current = head;
//Traverses the linked list until we're at the end
while (current != NULL) {
//Gets the current node in preperation of freeing it
struct node *node_to_free = current;
//Moves on with our life to the next node
current = current->next;
//Frees the node, so we don't have a memory leak
free(node_to_free);
}
printf("Freed all the nodes in the linked list\n");
}
//Insert at the beginning of a linked list
struct node *insert_at_head(struct node *head, struct node *new_node) {
struct node *prev_head = head;
//Our new node points to what use to be the start of the linked list
new_node->next = prev_head;
//The start of our linked list is now the new node
head = new_node;
return head;
}
//Inserts at the tail of a linked list
struct node *insert_at_tail(struct node *head, struct node *new_node) {
if (head == NULL) {
head = new_node;
return head;
}
struct node *current = head;
//So that we don't fall of the end of our linked list
//Stop when the next item is NULL
while (current->next != NULL) {
current = current->next;
}
//We are at the very last node in our list
//Make it point to our new node
current->next = new_node;
return head;
}
//Inserts in the middle of a linked list
struct node *insert_at_index(struct node *head, struct node *new_node, int index) {
struct node *current = head;
int counter = 0;
//Will continue until we are one before where we want our node to end up
while (counter < index - 1) {
current = current->next;
//Keeps track of what index we are at
counter++;
}
struct node *prev_next = current->next;
current->next = new_node;
new_node->next = prev_next;
return head;
}
//Deletes from a given index
struct node *delete_at_index(struct node *head, int index) {
if (index == 0) {
struct node *prev_head = head;
head = head->next;
free(prev_head);
return head;
}
struct node *current = head;
int counter = 0;
//Counts up to where we want to go
while (counter < index - 1) {
//Proceeds to next
current = current->next;
counter++;
}
//Gets the node we want to delete
struct node *node_to_free = current->next;
//Gets the node we want to point at next
//Only if it exists
struct node *to_point_at;
if (node_to_free->next != NULL) {
to_point_at = node_to_free->next;
} else {
//Otherwise we will point to NULL
to_point_at = NULL;
}
current->next = to_point_at;
free(node_to_free);
return head;
}
int main(void) {
// the first node in a linked list is the head of our list.
struct node *head = create_node(11);
// create the next few nodes
struct node *second_node = create_node(8);
struct node *third_node = create_node(7);
struct node *fourth_node = create_node(15);
struct node *fifth_node = create_node(20);
// we need to LINK the nodes in the linked list.
// the head node (11) should point to the second node
head = insert_at_tail(head, second_node);
head = insert_at_tail(head, third_node);
head = insert_at_tail(head, fourth_node);
head = insert_at_tail(head, fifth_node);
struct node *sixth_node = create_node(55);
head = insert_at_index(head, sixth_node, 2);
// and so on.
print_linked_list(head);
head = delete_at_index(head, 1);
print_linked_list(head);
free_all_nodes(head);
return 0;
}