// The goal of this program: create a linked list
// with elements 1, 5 and 17
// Lecture 11 Week 7
#include <stdio.h>
#include <stdlib.h>
// What does a single node of a linked list have in it?
struct node {
int data;
struct node *next;
};
// First function:create_node
// Input: int, struct node *next
// Output: struct node*
struct node *create_node(int data, struct node *next);
// Function that will print the list
// Input: a pointer to the start of the list (struct node *head)
// Output: void
void print_list(struct node *head);
struct node *insert_tail(int data, struct node *head);
struct node *insert_at_posn(int data, int position, struct node *head);
int main(void) {
// Get some memory to create a node
// Put the node at the head of the list
// Next.... THE LIST THAT I WANT 7, 5, 1,
// To create a node, I need some memory to place
// this node into
/*struct node *head = malloc(sizeof(struct node));
// Initialise data, *next
head->data = 7;
head->next = NULL;
struct node *head2 = malloc(sizeof(struct node));
head2->data = 5;
head2->next = NULL;
// head->next = head2
// 5, 7, NULL
*/
struct node *head = create_node(1, NULL);
// Let's create one more node with 5!
head = create_node(5, head);
head = create_node(7, head);
print_list(head);
// Now how do we move this to a function?
insert_tail(11, head);
print_list(head);
insert_at_posn(42, 2, head);
print_list(head);
return 0;
}
struct node *create_node(int data, struct node *next) {
// To create a node:
// 1. Malloc some space for the node
// 2. Initialise the node with values
//
struct node *new_node = malloc(sizeof(struct node));
new_node->data = data;
new_node->next = next;
return new_node;
}
void print_list(struct node *head) {
struct node *current = head;
while (current != NULL) { // while we have not reached the end of LL
printf("%d\n", current->data);
current = current->next;
}
// current = NULL
}
// Let's have a function that inserts at the tail of the list
// Input: head of the list, node
// Output: head of the list
// insert_tail( 11, head);
struct node *insert_tail(int data, struct node *head) {
// it will return the address of a new_node with data (11) and NULL
struct node *new_node = create_node(data, NULL);
struct node *current = head;
while (current->next != NULL) {
current = current->next;
}
// I am now standing at teh very last node
current->next = new_node;
return head;
}
// I want a function that will insert a node at a specified
// position in the linked list
// Input: int position, int data, head
// Output: head
// insert_at_posn(42, 2, head);
struct node *insert_at_posn(int data, int position, struct node *head) {
struct node *new_node = create_node(data, NULL);
// Anytime you insert into a list, think about:
// 1. Inserting at the head of the list (the head will change)
// 2. Inserting into an empty list (will become the head, and head will
// change)
// What happens if the position is at the head of the list and
// the list is empty?
if (position == 0 && head == NULL) {
head = new_node;
return head;
}
// What happens if the position is at the head of the list
// and the list is not empty
if (position == 0 && head != NULL) {
new_node->next = head;
head = new_node;
return head;
}
// loop until we get to teh position just before where we
// want to insert a node
struct node *current = head;
int counter = 1;
while (current != NULL && counter != position) {
counter++;
current = current->next;
}
// current == NULL --- reached the end of the list
// OR
// counter == position = we have gotten to the position to insert
if (counter == position) {
new_node->next = current->next;
current->next = new_node;
return head;
}
// reached the end of the list (current == NULL)
// counter has never equalled the position no
printf("The position number doesn't exist\n");
return head;
}