Linked Lists

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 which 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 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. 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.

linked-list-Data-Structure-MSA Technosoft

Benefits of Linked lists

Size is not fixed. We can add or remove any node according to our requirement.

Insertion or deletion of node 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 contain pointer reference to 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 value of 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

Linked list can be of several types. This is 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 reference to the next node along with data.

singly-Linkedlist-MSA-Technosoft

Doubly Linked List

It has two references, one to the next node and another to previous node.

doubly-linkedlist-MSA-Technosoft

Circular Linked List

Here, last node of the list points back to the first node (or the head) of the list.

Circular-LinkedList-MSA-Technosoft

Doubly Circular Linked List

Here, two consecutive elements are linked or connected by previous and next pointer and the last node points to first node by next pointer and also the first node points to last node by previous pointer.

doubly-circular-linked-list-MSA-Technosoft

Operations on linked list

We can perform 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 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 is used for dynamic memory allocation in c language. typedef defines a datatype.

Adding a node to 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 next sub element of node p. NULL denotes 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.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.