Hello Everyone! Finally, something interesting happened in my college yesterday besides learning theories and math. Today I'll be writing about what I've learned during a session about linked lists.
Before we get started we need to understand what are data structures. So in computer science, a data structure is a way to manage, store, and organize data so that it can be accessed efficiently. Now there are many types of data structures, last week in a lecture I was shown this picture that visualizes types of data structures.
For half a year I regularly was taught and used Array to store data but It has It has limitations when it comes to managing data.
Array vs Linked List
You can only store a fixed amount of data in an Array while a linked list can store as much as you want.
Adding new data in an array is only limited to the space declared and any unused spaced declared is still being used in memory.
You can add and delete data anywhere in the linked list with very little processing power compared to arrays.
How Linked List Works
A linked list is comprised of nodes. Each node has two things, data and a pointer to point to the next node. In the beginning, it also has a pointer called a head that points to the very first node. And if a node is at the very end of the list, the pointer will point to NULL or nothing. This effectively connects everything into one like this.
Now I will be explaining the code that I was taught during my session in the lecture. For this, you'll need to already understand the basics of C, arrays, pointers, malloc, and struct.
Declaring the Linked List
I typed in the basic #include <stdio.h> for input and output, #include <stdlib.h> for using malloc() and free(), and #include <stdbool.h> for boolean that will be useful later.
To declare a linked list is pretty straightforward, first, I create a struct called node that consists of an integer called data and a pointer called next. For this code, I'm making a simple linked list to manage numbers. Then I declared the three main pointers that will be used throughout the code.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct node{
int data;
struct node *next;
};
struct node *head = NULL;
struct node *tail = NULL;
struct node *curr = NULL;
The head will be used to point to the start of the list, the tail will be used to point to the very end of the list and curr (means current) will be used to access different parts of the list.
Now I make the main and make a variable to input the data.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct node{
int data;
struct node *next;
};
struct node *head = NULL;
struct node *tail = NULL;
struct node *curr = NULL;
int main()
{
int input;
printf("Input a Number : ");
scanf("%d", &input); fflush(stdin);
return 0;
}
Adding Functions for The Linked List
In my first session, I was taught two functions which are to add new notes and to print all the data in the nodes. First, I made a function called push_back(int data) that adds the inputted data to the end of the list.
int push_back(int data)
{
curr = malloc(sizeof(struct node));
curr->data = data;
curr->next = NULL;
if (head == NULL)
{
head = curr;
tail = head;
}
else
{
tail->next = curr;
tail = curr;
}
}
In the function, I used the curr pointer to allocate new memory for the new node. Assign the current data node I'm pointing to the data inputted, and assign the next pointer to NULL.
curr = malloc(sizeof(struct node));
curr->data = data;
curr->next = NULL;
Then I made an if statement that checks if the head is NULL. If the head is NULL that means the head is empty to begin with so I assign the head to curr and assign the tail to the head because it is currently the beginning and the end of the node.
If the head is not NULL then it already has nodes. This means I just need to assign the next pointer in the tail to the curr and change the pointer tail to the curr since it is now the very end of the list.
Next, I created a function called print_list to print out all the data.
void print_list()
{
curr = head;
while (curr != NULL)
{
printf("%d ", curr->data);
curr = curr->next;
}
}
This function is super simple, first I point the curr pointer to the head, and then while curr is not NULL I print out the data and change the curr pointer to the next in the list until it is NULL.
So to make this a little bit better I added a few lines of code to make the output a little nicer.
void print_list()
{
curr = head;
bool first = false;
printf("{");
while (curr != NULL)
{
if(!first)
{
printf("%d", curr->data);
first = true;
}
else
printf(", %d", curr->data);
curr = curr->next;
}
printf("}\n");
}
This just changes the output from this
10 20 30 40 50 60
to this
{10, 20, 30, 40, 50, 60}
With this two functions, I played around with it in the main function. Here is the full code.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct node{
int data;
struct node *next;
};
struct node *head = NULL;
struct node *tail = NULL;
struct node *curr = NULL;
int push_back(int data)
{
curr = malloc(sizeof(struct node));
curr->data = data;
curr->next = NULL;
if (head == NULL)
{
head = curr;
tail = head;
}
else
{
tail->next = curr;
tail = curr;
}
}
void print_list()
{
curr = head;
bool first = false;
printf("{");
while (curr != NULL)
{
if(!first)
{
printf("%d", curr->data);
first = true;
}
else
printf(", %d", curr->data);
curr = curr->next;
}
printf("}\n");
}
int main()
{
int input;
printf("Input a Number : ");
scanf("%d", &input); fflush(stdin);
push_back(input);
push_back(input + 10);
push_back(input + 20);
push_back(input + 30);
push_back(input + 40);
push_back(input + 50);
print_list();
return 0;
}
Now I have a list that I can add and print out. Of course, there will be more to come when I learn later on in the lecture and I'm looking forward to learning more about linked lists. And that's about it, see ya.