In this tutorial, you will learn various types of the linked list. Additionally, you will discover the implementation of a linked list in C.
In this article, you will learn-
What is a linked list?
A linked list is a typical data structure made of a chain of nodes in which every node contains a worth and a pointer to the next node in the chain.
The head pointer points to the first node, and the last element of the list points to null. At the point when the list is vacant, the head pointer points to null.
A linked list can dynamically increase in size and it is not difficult to insert and erase from a linked list on the grounds that not at all like arrays, we just need to change the pointers of the previous element and the next element to insert or erase an element.
Linked lists are typically used to create file systems, adjacency lists, and hash tables.
Before you learn about the type of the linked list, make sure you know about the LinkedList Data Structure.
There are three common types of Linked List.
Singly Linked List
It is the most common. Each node has data and a pointer to the next node.
Node is represented as:
struct node {
int data;
struct node *next;
}
A three-member singly linked list can be created as:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;
Doubly Linked List
We add a pointer to the previous node in a doubly-linked list. In this manner, we can go one or the other way: forward or in reverse.
A node is represented as
struct node {
int data;
struct node *next;
struct node *prev;
}
A three-member doubly linked list can be created as
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; one->prev = NULL; two->next = three; two->prev = one; three->next = NULL; three->prev = two; /* Save address of first node in head */ head = one;
Circular Linked List
A circular linked list is a variety of a linked list where the last element is linked to the primary element. This structures a circular loop.
A circular linked list can be either singly linked or doubly linked.
- for a singly linked list, the next pointer of the last item points to the primary item
- In the doubly linked list, the prev pointer of the first item points to the last item too.
A three-member circular singly linked list can be created as:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = one; /* Save address of first node in head */ head = one;
Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.
