A linked list is another data structure in which elements are linked with one another. Here, each element is said as a node which is divided into two parts.

- Information(data) part stores the information.
- Address or pointer part holds the address of the next element of the same type. The linked list is also known as a self-referential structure.

Each element (node) of a list comprises two items: the data and a reference pointer to the next node.

- The entry point(start) into a linked list is called the
**head**of the list. Note that the head pointer is not a separate node but a reference to the first node. - The last node refers to NULL.
- If the linked list is completely empty, then the head pointer is a null reference.

typedef struct linked list node

{

int data;

struct linkedlistnode * next;

} node;

Above is the syntax of declaring a node that contains two fields in it one is for storing information, and another is for storing the address of other nodes to traverse the list.

**Advantages:**

- Linked lists are the dynamic data structure as they can change them (grow and shrink) during the execution.
- Utilizes memory efficiently because here memory is not pre-allocated.
- Insertion and deletion can be done easily at the desired location.

**Disadvantages:**

- Require more memory if the number of fields is more.
- Access to an arbitrary data item is time-consuming.

**Operations on Linked Lists:**

- The following operations involved in the linked list are as given below
**Creation:**Used to create a lined list. **Insertion:**Used to insert a new node in the linked list at the specified position. A new node may be inserted at the beginning of a linked list.- At the end of a linked list
- At the specified position in a linked list
- In the case of an empty list, a new node is inserted as a first node.
**Deletion:**This operation is used to delete an item from the linked list. A node can be deleted- From the starting (head) of a linked list.
- From the end of a linked list.
- At any specified position.
**Traversing:**Traversing is a process of going through (accessing) all the nodes(items) of a linked list from one to another end.

**Types of Linked Lists**

**Singly Linked List:**In this each node has one data field and only one address field, which points to the next node. So, the main disadvantage of this list is that we can't access the predecessor of a node from the current node.**Doubly Linked List:**Each node of the linked list is having two address fields (or links) which help in accessing both the successor node (next node) and predecessor node (previous node).**Circular Linked List:**It has the address of the first node in the link (or address) field of the last node.**Circular Doubly Linked List:**It has both the previous and next pointer circularly.

**Example1: Reverse of a Singly Linked List with iterations**

**Example 2: Reverse of a Singly Linked List with Recursion**

**Example 3: Reverse of a Doubly Linked List**

**Example 4: Finding the middle of a Linked List**

**Time complexity on Singly Linked Lists of n nodes for the following operations:**

- Adding a new node in the beginning of the list: O(1)
- Adding a new node in the end: O(n)
- Adding a new node after a node : O(n)
- Adding a new node before a node: O(n)
- Adding a new node after k'th node: O(n)
- Searching a node with a given data: O(n)
- Deleting a node from the beginning: O(1)
- Deleting a node at the end: O(n)
- Deleting a node with a given data: O(n)
- Deleting the k'th node: O(n)
- Modifying the data of all nodes of a given linked list: O(n)
- Traverse all nodes: O(n)

**Time complexity on Doubly Linked Lists of n nodes for the following operations:**

- Adding a new node in the beginning of the list: O(1)
- Adding a new node in to the end: O(n)
- Adding a new node after k'th node: O(n)
- Adding a new node after a node: O(n)
- Adding a new node before a node: O(n)
- Searching a node with a given data: O(n)
- Traversing all nodes: O(n)
- Deleting a node from the beginning: O(1)
- Deleting a node from the end: O(n)
- Deleting a node with a given data: O(n)
- Deleting the k'th node: O(n)
- Modifying the data of all nodes in a linked list: O(n)

**Time complexity on Circular Linked Lists of n nodes for the following operations:**

- Adding a new node in the beginning of the list: O(n)
- Adding a new node to the end: O(n)
- Adding a new node after k'th node: O(n)
- Adding a new node after a node: O(n)
- Adding a new node before a node: O(n)
- Searching a node with a given data: O(n)
- Deleting a node from the beginning: O(n)
- Deleting a node from the end: O(n)
- Deleting a node with a given data: O(n)
- Deleting the k'th node: O(n)
- Modifying the data of all nodes in a linked list: O(n)
- Traversing all nodes: O(n)

**Time complexity on Circular Doubly Linked Lists of n nodes for the following operations:**

- Adding a new node in the beginning of the list: O(1)
- Adding a new node to the end: O(1)
- Adding a new node after k'th node: O(n)
- Searching a node with a given data: O(n)
- Adding a new node after a node with a given data: O(n)
- Adding a new node before a node with a given data: O(n)
- Traversing all nodes: O(n)
- Deleting a node from the beginning: O(1)
- Deleting a node from the end: O(1)
- Deleting a node with a given data: O(n)
- Deleting the k'th node: O(n)
- Modifying the data of all nodes in a linked list: O(n)

So that was about Linked Lists.

For the detailed schedule of the **GATE Computer Science Engineering(CSE) 2022 Champion Study Plan, **click here

**GATE Computer Science Engineering(CSE) 2022 Champion Study Plan**

## Click Here to Avail GATE CSE Test Series!

**Thanks**

**Sahi Prep Hai Toh Life Set Hai !!!!**

## Comments

write a commentAjitem JoshiJul 5, 2018

Sachin Kumar SaxenaSep 25, 2018

Amit KumarAug 6, 2019

Ramashankar YadavOct 12, 2019

Mukesh KumarMar 11, 2020

...Read MoreAnil NayakJun 27, 2020

PradhnyaJul 22, 2020

Bikram DasNov 6, 2020

...Read MoreRohit ModiMar 20, 2021

Aashish ParmarJul 24, 2021