Category: Arrays and Lists

A singly linked list is a data structure in which each node contains a value and a reference to the next node in the list. It is a type of linear data structure where each node points only to the next node in the list and does not have a reference to the previous node. The first node in the list is known as the head of the list and the last node in the list has a NULL value in its reference, indicating the end of the list.

Here’s an example implementation of a singly linked list in C:

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

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

struct Node* head = NULL;

void insertAtBegin(int data){
  struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
  temp->data = data;
  temp->next = head;
  head = temp;
}

void printList(){
  struct Node* temp = head;
  while(temp != NULL){
    printf("%d ", temp->data);
    temp = temp->next;
  }
  printf("\n");
}

int main(){
  insertAtBegin(1);
  insertAtBegin(2);
  insertAtBegin(3);
  printList();
  return 0;
}

In this example, we define a structure Node with two fields: data and next. The head variable represents the head of the linked list and is initially set to NULL, indicating an empty list. The insertAtBegin function creates a new node, sets its data to the given value, and sets the next reference to the current head of the list. The printList function iterates through the list and prints the values of each node.

A circular linked list is a type of linked list where the last node of the list points to the first node, forming a cycle. In other words, it’s a linked list that has no end, the tail of the list is connected to the head of the list. Unlike a normal linked list, in a circular linked list, you can traverse the list indefinitely, moving from one node to the next.

Here is an example implementation of a circular linked list in C:

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

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

struct Node* head = NULL;

void insertAtEnd(int data){
  struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
  temp->data = data;
  temp->next = head;

  if(head == NULL){
    head = temp;
    return;
  }

  struct Node* ptr = head;
  while(ptr->next != head){
    ptr = ptr->next;
  }
  ptr->next = temp;
}

void printList(){
  struct Node* ptr = head;
  if(ptr == NULL){
    printf("The list is empty\n");
    return;
  }
  do{
    printf("%d ", ptr->data);
    ptr = ptr->next;
  }while(ptr != head);
  printf("\n");
}

int main(){
  insertAtEnd(1);
  insertAtEnd(2);
  insertAtEnd(3);
  printList();
  return 0;
}

This is just a basic example of a circular linked list, you can add more functionality to it based on your requirements.

A doubly linked list is a data structure in which each element of the list is linked to both the element before it and the element after it. In C, a doubly linked list can be implemented using a structure that contains two pointers, one to the previous element in the list and one to the next element in the list.

Here is an example of a doubly linked list in C:

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

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

struct node *head = NULL;

void insert_at_beginning(int data) {
  struct node *new_node = (struct node*) malloc(sizeof(struct node));
  new_node->data = data;
  new_node->prev = NULL;
  new_node->next = head;
  head = new_node;
}

void insert_at_end(int data) {
  struct node *new_node = (struct node*) malloc(sizeof(struct node));
  new_node->data = data;
  new_node->next = NULL;
  if (head == NULL) {
    new_node->prev = NULL;
    head = new_node;
    return;
  }
  struct node *temp = head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  temp->next = new_node;
  new_node->prev = temp;
}

void print_list() {
  struct node *temp = head;
  printf("List: ");
  while (temp != NULL) {
    printf("%d ", temp->data);
    temp = temp->next;
  }
  printf("\n");
}

int main() {
  insert_at_beginning(1);
  insert_at_end(2);
  insert_at_end(3);
  print_list();
  return 0;
}

In this example, the structure node represents a node in the doubly linked list. Each node contains an int value data, a pointer to the previous node in the list (prev), and a pointer to the next node in the list (next).

The head the pointer points to the first element in the list. The insert_at_beginning function adds a new node to the beginning of the list, and the insert_at_end function adds a new node to the end of the list. The print_list function displays the elements in the list.

This is just one example of how to implement a doubly linked list in C. There are many variations and optimizations that can be made to this basic structure, but the basic idea is the same: each node in the list contains pointers to both the previous node and the next node.