In C programming language, a linked list is a data structure in which each element (or node) contains two fields: a data field and a pointer to the next (and/or previous) element in the list. There are three main types of linked lists: singly linked lists, doubly linked lists, and circular linked lists.
Singly Linked List: A singly linked list is a list in which each node points only to the next node in the list. It is the simplest and most common type of linked list. Singly linked lists are easy to traverse in one direction, starting from the head of the list, but can be difficult to traverse in reverse order. Here’s an example of a singly linked list in C:
typedef struct node {
int data;
struct node* next;
} Node;
Node* head = NULL;
// add an element to the beginning of the list
void insert(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = head;
head = newNode;
}
// traverse the list and print its elements
void printList() {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("n");
}In this example, we define a Node struct that contains an integer data field and a pointer to the next node in the list. We then define a head pointer to the first node in the list, which is initially NULL.
The insert function adds a new element to the beginning of the list by creating a new node with the given data, setting its next pointer to the current head of the list, and updating the head pointer to point to the new node.
The printList function traverses the list starting from the head and prints out the data field of each node.
Doubly Linked List: A doubly linked list is a list in which each node points to both the next and the previous node in the list. This makes it easier to traverse the list in both directions. Here’s an example of a doubly linked list in C:
typedef struct node {
int data;
struct node* prev;
struct node* next;
} Node;
Node* head = NULL;
// add an element to the beginning of the list
void insert(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = head;
if (head != NULL) {
head->prev = newNode;
}
head = newNode;
}
// traverse the list forwards and print its elements
void printListForward() {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("n");
}
// traverse the list backwards and print its elements
void printListBackward() {
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
while (current != NULL) {
printf("%d ", current->data);
current = current->prev;
}
printf("n");
}In this example, we define a Node struct that contains an integer data field and pointers to both the previous and next nodes in the list. We again define a head pointer to the first node in the list, which is initially NULL.