Linked List

The linked list is a linear data structure where each node has two parts.

1. Data

2. Reference to the next node

Data

In this section, we can store the required information. It can be any data type.

Example

int age;
char name[20];

Reference to the next node

It will hold the next nodes address.

Head Node - Starting node of a linked list.

Last Node - Node with reference pointer as NULL.

Selecting a data type for the linked list

As we discussed earlier, each node in a linked list has two parts.

Data - it can be any data type. int,char,float,double etc.

Reference Part - It will hold the address of the next node. So, it is a type pointer.

Here, we need to group two different data types (heterogeneous).

Which data type is used to group the different data types?

That is a structure. So, every node in a linked list is a structure data type.

Sample Linked List Node

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

where,

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 3 nodes

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

struct node *head,*middle,*last;

head   = malloc(sizeof(struct node));
middle = malloc(sizeof(struct node));
last   = malloc(sizeof(struct node));

Assign values to each node

head->data   = 10;
middle->data = 20;
last->data   = 30;

1. Stack memory stores all the local variables and function calls (static memory).

Example: int a = 10;

2. Heap memory stores all the dynamically allocated variables.

Example: int *ptr = malloc(sizeof(int)); Here, memory will be allocated in the heap section. And the ptr resides in the stack section and receives the heap section memory address on successful memory allocation.

3. Address of the dynamic memory which will be assigned to the corresponding variable.

Linking each nodes

headnode middlenode lastnode NULL

head->next   = middle;
middle->next = last;
last->next   = NULL;     //NULL indicates the end of the linked list

1. head => next = middle. Hence head => next holds the memory address of the middle node (2024).

2. middle => next = last. Hence middle => next holds the memory address of the last node (3024).

3. last => next = NULL which indicates it is the last node in the linked list.

4. The simplified version of the heap memory section.

Let's print each node data in a linked list

To print each node's data, we have to traverse the linked list till the end.

Algorithm

1. Create a temporary node(temp) and assign the head node's address.

2. Print the data which present in the temp node.

3. After printing the data, move the temp pointer to the next node.

4. Do the above process until we reach the end.

Visual Representation

1. temp points to the head node. temp => data = 10 will be printed. temp will point to the next node (Middle Node).

2. temp != NULL. temp => data = 20 will be printed. Again temp will point to the next node (Last Node).

3. temp != NULL. temp => data = 30 will be printed. Again temp will point to the next node which is NULL.

4. temp == NULL. Stop the process we have printed the whole linked list.

Code

struct node *temp = head;

while(temp != NULL)
{
    printf("%d ",temp->data);
    temp = temp->next;
}

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 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.

Sample Linked List Implementation

Example

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

int main()
{
  //node structure
  struct node
  {
      int data;
      struct node *next;
  };

  //declaring nodes
  struct node *head,*middle,*last;

  //allocating memory for each node
  head   = malloc(sizeof(struct node));
  middle = malloc(sizeof(struct node));
  last   = malloc(sizeof(struct node));

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

  //connecting each nodes. head->middle->last
  head->next   = middle;
  middle->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;
  }
  printf("NULL");

  return 0;
}