What is a Linked List?
Linked list is a linear data structure. The elements in a linked list are linked together using pointers. It is a data structure consisting of a collection of nodes that together represent a sequence. Each node contains a data field and a reference to the next node in the list. It allows for efficient insertion or removal of elements from any position in the sequence during iteration.
It is the simplest and most common data structure after arrays. It is a dynamic data structure because the number of nodes in a list is not fixed. We can grow and shrink its size as per our requirements. The last node has a reference to null. The entry point to a linked list is called the head. The Head is not a separate node but the reference to the first node. If the list is empty then the head is a null reference.
Benefits of Linked lists
The size is not fixed. We can add or remove any node according to our requirements.
Insertion or deletion of nodes at any position is very easy.
Flaws of Linked lists
Random access is not feasible. We have to traverse the list sequentially that takes more time.
Use more memory because each node also contains pointer reference to the next node.
Linked list Implementation
A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then the value of the head is NULL. Each node in a list consists of at least two parts: data and Pointer to the next node.
We wrap both the data item and the next node reference in a structure as:
struct node
{
int data;
struct node *next;
};
Here, data stores the element, and next is a pointer to store the address of the next node.
Types of Linked Lists
A linked list can be of several types. This is a very simple data structure and can be implemented in any programming languages like c, c++, c#, java, python, etc. Linked lists have different types as follows:
Singly Linked List
It contains a reference to the next node along with data.
Doubly Linked List
It has two references, one to the next node and another to the previous node.
Circular Linked List
Here, the last node of the list points back to the first node (or the head) of the list.
Doubly Circular Linked List
Here, two consecutive elements are linked or connected by previous and next pointer and the last node points to the first node by the next pointer and also the first node points to the last node by the previous pointer.
Operations on a linked list
We can perform the following basic operations in a linked list:
Insertion: Adds an element at the beginning of the list.
Deletion: Deletes an element at the beginning of the list.
Display: Displays the complete list.
Search: Searches an element using the given key.
Delete: Deletes an element using the given key.
Creating a node in the Linked list
A node in the linked list is a self-referencing pointer. We can use the following c programming code to create a node
typedef struct LinkedList *node; //Define node as pointer of data type struct LinkedList
node createNode()
{
node temp; // declare a node
temp = (node)malloc(sizeof(struct LinkedList)); // allocate memory using malloc()
temp->next = NULL;// make next point to NULL
return temp;//return the new node
}
malloc() function that is used for dynamic memory allocation in c language. typedef defines a datatype.
Adding a node to a linked list
node addNode(node head, int value){
node temp,p;// declare two nodes temp and p
temp = createNode();//createNode will return a new node with data = value and next pointing to NULL.
temp->data = value; // add element's value to data part of node
if(head == NULL){
head = temp; //when linked list is empty
}
else{
p = head;//assign head to p
while(p->next != NULL){
p = p->next;//traverse the list until p is the last node.The last node always points to NULL.
}
p->next = temp;//Point the previous last node to the new node created.
}
return head;
}
Traversing the linked list
node p;
p = head;
while(p != NULL){
p = p->next;
}
Here -> is used to access the next sub-element of node p. NULL denotes the end of the list.
Was this article helpful? Must share your views in the comment section below.
Keep visiting our Tech Blogs for our latest blogs.