# What is a Linked List

## What is a Linked List?

A Linked List is a very commonly used linear data structure that consists of a group of nodes in a sequence. Each node holds its data and the address of the next node hence forming a chain-like structure.

You have to start somewhere, so we give the address of the first node a special name called HEAD.

Each node is separated into two different parts:

1. The first part holds the information of the element or node
2. The second piece contains the address of the next node (link / next-pointer field) in this structure list.

The end of the list isn’t a node but rather a node that points to a null or an empty value.

You might have played the game, Treasure Hunt, where each clue includes the information about the next clue. That is how the linked list operates.

## Structure of a linked list

Each node has a data item and a pointer to another node.

The power of a linked list comes from the ability to break the chain and rejoin it. For example, if you want to put an element 4 between 1 and 2, the steps would be:

• Create a new node and allocate memory to it.
• Add its data value as 4
• Point its next pointer to the node containing 2 as the data value
• Change the next pointer of “1” to the node we just created.

Doing something similar in an array would have required shifting the positions of all the subsequent elements.

## Operations

Let’s have a look at the basic operations supported by 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.

There are 3 different implementations of Linked List available, they are:

Singly-linked lists are one of the most primitive data structures you will go through. Here each node makes up a singly linked list and consists of a value and a reference to the next node (if any) in the list.

A Singly Linked list is one in which all nodes are linked together in some sequential manner.

Hence, it is also called a linear linked list. A singly linked list allows traversal of data only in one way. Clearly, it has the beginning and the end.

In a singly linked list, every node has a link to its next node in the sequence. So, we can traverse from one node to another node only in one direction and we can not traverse back.

We can solve this kind of problem by using a double-linked list.

A Doubly Linked List is a data structure where each node has its data, left pointer, and right pointer.

Here, each node has the address of its next node as well as its previous node (except the last node, the next pointer of the last node will point to NULL, which means the end of a node).

Its advantage over the singly-linked lists is that you will have access to the previous node. You can traverse both from left to right and vice versa.