Linked List using C language. Understand Linked List easily.

In this blog, I will share some concepts of Linked Lists.

What are Linked Lists?

A linked list is a linear data structure, in which elements are not stored in contiguous memory locations. Instead, each element consists of a data field and a reference to the next element in the list. The elements in a linked list are linked using a pointer.

Linked lists are useful for dynamic memory allocation, as they can be easily inserted or removed without reallocation or reorganization of the entire structure. They are also often used in the implementation of stacks, queues, and other abstract data types.

Representation of a Linked List

Elements in a linked list are usually called nodes. Each node has a data field and a pointer to the next node. Head is a pointer pointing to the first node in the above representation, with the next pointer pointing to the second node, and so on until NULL is reached.

You can use any name of pointers but it is always a good practice to use Head as the first node name because it prevents confusion.

The next pointer contains the address of the next node.

You might be thinking that what is NULL?

A null pointer has a reserved value that is called a null pointer constant for indicating that the pointer does not point to any valid object or function. Click here to learn more about the null pointers.

So far we have a good idea that what a linked list is.

Now let's see the operations which can be performed in a linked list. I will use C language to demonstrate, although concepts are the same in every language, the syntax is different.

1. Creation of a node in a linked list.

To create a node we need to create a Struct data type that allows a way to group several related variables into one place.

NOTE - A node has a data field and a reference to the next node.

struct node{
    int data; // used to store the integer information.
    struct node *next; //It is used to refer to the next node. It will hold the address of the next node.
};

Let's create and allocate memory for two nodes and assign values to them.

struct node *head, *last;

//allocating memory for each node
head = malloc(sizeof(struct node)); // malloc is used for allocating memory.
last = malloc(sizeof(struct node));

//assigning values to each node
head->data = 10;
last->data = 20;

//connecting each nodes. head->last
head->next = last;
last->next = NULL;

// for better understanding check the images

What does sizeof(struct node) mean?

if you will print the sizeof(struct node), it will give 8 as its output. So what does this convey? In the struct data type, we have an Integer data field that takes the memory of 4 bytes and the next pointer that also takes 4 bytes of memory.

The malloc(sizeof(struct node)) allocates 8 bytes of memory for each node. 4 for the data field and 4 for the next pointer.

1000 is the address of the Head node and 2000 is the address of the Last node.

The next pointer of the Head node is holding the address of the Last node. So that nodes can be connected.

2. Traversing through the linked list

I have a question to ask you when do we use while loops and for loops? The answer is simple when we don't know the size/length we use while loops and we use for loops when we know the size.

In our example, we know that there are only two nodes, so we can use for loop. But remember linked lists use dynamic memory allocation so the user can insert any number of nodes. So we should always use while loops for traversing in the linked list.

//temp is a reference for head pointer.
struct node *temp = head;
//till the node becomes null, printing each nodes data
while (temp != NULL){
    printf("%d\t",temp->data); // \t is used for tabular space
    temp = temp->next; // temp shift to next node
}

Why do we need to use the temp node instead head?

If we use the head pointer instead of the temp while printing the linked list, we will miss the track of the starting node. (After printing the data head node will point to the NULL).

To avoid that, we should not change the head node's address while processing the linked list. We should always use a temporary node to manipulate the linked list.

Putting everything together

#include<stdio.h>
#include<stdlib.h>

//node structure
struct node
  {
      int data;
      struct node *next;
  };

int main()
{
  //declaring nodes
  struct node *head,*last;
  //allocating memory for each node
  head = malloc(sizeof(struct node));
  last = malloc(sizeof(struct node));
  //assigning values to each node
  head->data = 10;
  last->data = 20;
  //connecting each nodes. head->last
  head->next = last;
  last->next = NULL;
  //temp is a reference for head pointer.
  struct node *temp = head;
  //till the node becomes null, printing each nodes data
  while(temp != NULL)
  {
      printf("%d->",temp->data);
      temp = temp->next;
  }

  return 0;
}

3. Inserting a node in a Linked List

To insert a node at the beginning of a linked list, we need to create a function that will make our code easier to understand. Before that let us visualize what we need to do.

Step 1. We have to create a new node.

Step 2. Then we have to assign data to our new node (Temp), and the next pointer to NULL.

Step 3. We need to connect our new node with the Head. Now our first node is the new node (Temp).

NOTE - The first node of a linked list should always point to the Head.

Step 4 - Then we will point the first node to the Head.

Now we will create a function that will do our work.

void addFirst(struct node *head, int val)
{
      //create a new node
      struct node *temp= malloc(sizeof(struct node));
      temp->data = val; 
      temp->next = NULL;
      //connecting our node with head
      temp->next = head
      // pointing the first node to head
      head = temp;
}

Similarly, you can insert the node at the last of a linked list.

4. Deleting a node in a Linked List

We will visualize what we need to do.

We will delete the node that has the data 10.

1. If the head node has the given key, make the head node point to the second node and free its memory.

2. Otherwise, From the current node, check whether the next node has the given key if yes, make the current->next = current->next->next and free the memory. Else, update the current node to the next and do the above process (from step 2) till the last node.

A. Head node has the given key

void deleteNode(struct node *head, int key)
{
      //temp is used to freeing the memory
      struct node *temp;
      //key found on the head node.
      //move to head node to the next and free the head.
      if(head->data == key)
      {
          temp = head;    //backup the head to free its memory
          head = head->next;
          free(temp);
      }
}

1. Make the head points to the next node.

2. Free the head node's memory.

3. Finally, the new linked list.

B. For other nodes (Non-Head)

void deleteNode(struct node *head, int key)
{
      //temp is used to freeing the memory
      struct node *temp;
      //key found on the head node.
      //move to head node to the next and free the head.
      if((*head)->data == key)
      {
          temp = head;    //backup to free the memory
          head = head->next;
          free(temp);
      }
      else
      {
          struct node *current  = head;
          while(current->next != NULL)
          {
              //if yes, we need to delete the current->next node
              if(current->next->data == key)
              {
                  temp = current->next;
                  //node will be disconnected from the linked list.
                  current->next = current->next->next;
                  free(temp);
                  break;
              }
              //Otherwise, move the current node and proceed
              else
                  current = current->next;
          }
      }
}

1. Make the current node point to the head node. (current => data = 50).

2. current => next. (current=>next=>data = 10).

3. current => next => next. (current=>next=>next=>data = 20).

4. We have to remove node 10. Since current => next = 10 we can remove the node by setting current => next = current =>next => next. And then free the node.

5. Finally, the new linked list.

What so far we have learned?

We have learned some important concepts of singly linked lists. Let me summarize it for you 1. What is a Linked List? 2. What is the use of a Linked List? 3. How does Linked List work? 4. Operations on a Linked List

You have to practice by yourself. Understanding concepts are important and practice will make concepts even stronger. And the best way is to practice using pen and paper and when you become confident enough then code it.

If you have found this blog informative, please Like, comment, and share this blog with your friends.

Follow me for more Informative content. - linkfree.eddiehub.io/skmominali17

See you in the next blog till then keep practicing.

Sk Momin Ali's Blog