What is liked list? Types and operations
What is a Linked list?
A linked list is a linear data structure in which data elements are connected to each other via links. We can say that a linked list is the collection of nodes that are connected to each other like a chain.
Each node contains a data value and a pointer (address) to the next node.
Header points to the first node and the last value of the node point to Null because there is no node further. For an empty linked list, the header points to null.
A linked list is the most used Data Structure after array. It is easy to increase the size of a linked list.
Linked lists are used to create hash tables, adjacency lists, and file systems.
What are the Important terms in linked list?
Link: A link in a linked list is a place to store the data or item called an element.
First: Each link has a connection to their previous link called First.
Next- Each link points toward the next link called Next.
Representation of a link list:
A linked list is a connection of nodes in which each link points toward the next links.
Following are the points to be considered in Linked list:
- Each link contains a link element called first
- Each link stores data called elements and points toward the next link called next.
- The last link points to null to show that list ends here.
Types of the Linked list:
There are basically three types of Linked list:
- Singly (unidirectional ) linked list
- Doubly (Bi-directional) linked list
- Circular Linked list.
Singly linked list: Singly linked list is uni directional and in this each node has a data and pointer to the next node.
Node representation:
struct node {
int data;
struct node *next;
}
Representation for 3 nodes Singly linked list
/* 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;
/* In head, save first node element */
head = one;
- Doubly linked list: The doubly linked list is bi-directional and in this, we can go in either backward or forward direction. In the Doubly linked list, each node has pointers to its previous and next nodes.
Node representation
struct node {
int data;
struct node *next;
struct node *prev;
}
Representation for three nodes of Doubly linked list
/* 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;
/* In head, save first node element*/
- Circular linked list:
A circular linked list can be unidirectional and bidirectional.
In a unidirectional circular linked list, the last node is connected to the first node. In a bi-directional circular linked list, the last node is connected to the first node and the first node is connected to the last node as well.
Node representation:
/* 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 the first node in head */
head = one;
Basic operations of a linked list:
With the help of a linked list, we can perform many operations, which are:
- Insertion: Add an element at a given position.
- Deletion: Delete a specific element from the list.
- Searching: Search the desired element by value.
- Sorting: Arrange the nodes in an ordered way in the linked list.
- Merging: Merge two lists into one.
- Traversal: Traverse the nodes one after another
- Updating: Update a node.
To know more about the linked list in Data Structure, do visit our online education platform of Hep me study bro. It is one of the leading online platforms for everyone who wants to learn data structure and algorithms in a very easy way. Virtual learning over traditional learning
