Arrays and Linked Lists in C/C++ language.
Data Stuctures and Algorithms : An introduction to linked lists in C/C++ language.
Introduction
In this article I'm going to walk you through an implementation of linked lists in the C programming language, the concept of linked lists may seem difficult at first, but with practice and writing down what's going on in a paper it will get a lot easier, before you start I highly recommend that you take a paper and pen and try to draw the memory, nodes, and everything, this really helped me in the beginning to master linked lists and other data structures that we'll see in future articles.
Arrays and memory
As shown in the figure below, the memory is divided into 4 parts:
The code memory: where the code is stored.
The static/global memory: where the static and global variables are stored.
Stack memory: when we create a new function, for example main, a new frame is created inside the stack memory, this frame will contain all the variables declared in the function, and it will be deleted once the function call is finished.
Heap memory: when we want to specify the size of an array dynamically (at runtime), we allocate this memory using the malloc/calloc functions in C or new in C++.
Difference between Linked Lists & Arrays
As arrays, Linked Lists are linear data structures, suppose we declare an array of up to 10 elements:
int A[10];
The problem is that, if we want to store more data in the array, we won't be able to do so, because the maximum number of elements our array can store is 10 elements, similarly, if we store only 5 elements in our array, then 5*sizeof(int) Bytes of memory will be wasted.
In Linked Lists, we can store as many elements as we want because the elements are not stored in a contiguous place.
Linked Lists
A Linked List is a set of nodes, each node stores the data and address of the next node, as shown in the following figure:
Define a Linked List
Before we start defining our Linked List, let's import some standard libraries for the inputs and outputs, and for the malloc function:
#include <stdio.h>
#include <stdlib.h>
First of all, let's create a node, for this we will use a structure that we will call Node, the structure will contain data and the next element it points to.
// C code
struct Node{
int data;
struct Node* next;
};
After that, let's create the head of the Linked List, this head will store the address of the first node:
struct Node* head = NULL;
This pointer is declared as a global variable, we will be able to access it in functions in the future.
Create a Linked List from an array
To be able to test our functions, let's create a Linked List from an array, the following function takes two parameters, the array and the length of the array, for now let's focus on the other functions and in the future we will see in detail how this function is implemented.
// Create from an array
void create(int A[], int n)
{
struct Node *temp, *last;
head= (struct Node*)malloc(sizeof(struct Node));
head->data = A[0];
head->next = NULL;
last = head;
for(int i=1; i<n; i++){
temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = A[i];
temp->next = NULL;
last->next = temp;
last = temp;
}
}
in the main function, we can call this function as follows:
int main()
{
int A[] = {4, 5, 8, 1, 6, 20};
int n = 6;
create(A, n);
return 0;
}
Display function
Now that we have defined our node structure and the head, we have created our Linked List, we will create a function to display our Linked List :
// Display
void Display(struct Node* p)
{
while(p!=NULL)
{
printf("%d", p->data);
p=p->next;
}
}
the display function takes as parameter a pointer to a Node which is the head of our Linked List, then it will print the data of each Node as long as it is not NULL (we haven't reached the end of the Linked List yet).
Here, we could define a function that takes nothing as parameter, and then we must define a new Node that will be a copy of the head Node, this is important because inside the while loop, we replace the value of p by p->next every time, if we don't create a copy, we will lose the original value of head.
Now, to test our function, we can call it in the main function as follows:
int main()
{
int A[] = {4, 5, 8, 1, 6, 20};
int n = 6;
create(A, n);
Display(head);
return 0;
}
We can also define the previous function recursively :
// Recursive Display
void Display_recursive(struct Node* p)
{
if(p!=NULL)
{
printf("%d", p->data);
Display(p->next);
}
}
Analyzing the complexity of these functions, the time complexity is the same for both of them and it is equal to O(n) where n is the size of the Linked List, however the space complexity is completely different, while the iterative function has a complexity of O(1), the recursive function has a complexity of O(n), this is because this function creates frames in the memory of the stack every time it is called, and the number of frames created is n, where n is the length of our Linked List.
Count the elements of a Linked List
Now, let's define a function to count the number of Nodes in a Linked List :
// Count the Nodes in a Linked List
int count(struct Node *p)
{
int c = 0;
while(p!=NULL){
p = p->next;
c++;
}
return c;
}
This function takes as parameter the head of a Linked List, then we create a copy of the head called p. We define a variable c which will be incremented and returned at the end, then we iterate on the nodes of our Linked List, as long as p is not NULL (which means that we have not yet reached the end of the Linked List) we increment the value of c and we move the p to the address that it points.
Now, let's code our previous function recursively :
int count_recursive(struct Node *p)
{
if(p!=NULL){
return count_recursive(p->next)+1;
}
return 0;
}
As mentioned earlier, the space and time complexity of this function is O(n) where n is the length of the Linked List.
The sum of elements of a Linked List
Now let's define a function to calculate the sum of the elements of a Linked List, this function takes the head of the Linked List. Then we define sum and assign it the value 0, then as long as p is not NULL, we add the node's data to the sum, then increment the value of p to the next address it points to. Finally, we return the sum.
// Sum of elements
int sum(struct Node* p)
{
int sum = 0;
while(p!=NULL)
{
sum = sum + p->data;
p = p->next;
}
return sum;
}
We can define the previous function recursively :
// Sum of elements recursion
int sum_recursive(struct Node *p)
{
if(p==NULL){
return 0;
}
return sum_recursive(p->next) + p->data;
}
Max of a linked list
Now let's create a function that returns the maximum element of a linked list:
// Max element
#define MIN_INT -32768
int max(struct Node *p)
{
int M = MIN_INT;
while(p!=NULL)
{
if(p->data>M)
{
M = p->data;
}
p = p->next;
}
return M;
}
We define a global variable called MIN_INT which is the minimum value of a 2 bytes architecture, we choose this value to be sure that all the values of the array will be higher than it.
Linear search in a linked list
Now, let's create a function that returns the address of a key we are looking for, for that, we will create a function that returns the type : struct Node* since it's an address to a Node, then inside the function we will follow the same procedure of traversing the linked list by incrementing the value of p.
The first function is iterative, and the second is recursive.
// Search in a linked list
struct Node* search(struct Node* p, int key)
{
while(p!=NULL){
if(key==p->data){
return p;
}
p = p->next;
}
return NULL;
}
// Recursive function
struct Node* search_recursive(struct Node* p, int key)
{
if(p==NULL)
{
return NULL;
}
if(key == p->data)
{
return p;
}
return search_recursive(p->next, key);
}
Insert in a Linked List
Now let's Insert a Node In a Linked List, for that, we must traverse our Linked Lists until we reach the index as shown in the next figure :
The function insert takes the data : x, the index and the head of the data structure :
void insert(int x, int index, struct Node* p)
{
struct Node* t = (struct Node*)malloc(sizeof(struct Node));
p->data = x;
for(int i=0; i<index-1; i++)
{
p = p->next;
}
t->next = p->next;
p->next = t;
}
Finally...
This was the first article on Lnked Lists, more features will be added in the future, stay tuned!