Linked Lists :

Linked list is a linear structure of information. Pointers are used to link the components in a linked list. It is a data structure composed of a node set representing a sequence together. Each node includes a field of information and a reference in the list to the next node. It enables the effective insertion or removal of components during iteration from any place in the sequence.

It is following arrays the easiest and most popular data structure. It is a dynamic structure of information because there is no set amount of nodes in a list. As per our demands, we can develop and reduce its size. The final node has a null reference. The access point is called the head to a linked list. Head is not a distinct node, but the first node reference.

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.

Doubly Linked List :

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

Circular Linked List :

Here, 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 first node by next pointer and also the first node points to last node by previous pointer.

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
}

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.