Introduction to Linked List in Data Structure

Introduction

Like array, Linked list is a linear data structure. Unlike array, linked list nodes (elements) are not stored in continuous memory location, nodes are connected using reference to the node. Nodes and elements can be used interchangeably.

Each element(node) of a list is comprising of two items - the data and a reference to the next node.

Why Linked List?

Both Array and Linked list are linear data structure, but have following limitation.

• The size of an array is fixed. So we must know the upper limit of it in advance. The allocated memory is equal to upper limit irrespective of usage.
• Insertion and deletion of an element in an array is expensive. Let's suppose you need to insert an element in sorted array then need to create room for new element, for that need to shift the elements of array.

For example: Lets suppose a sorted array of ids.

ids[] = [100, 110,120,130,140]
Now we want to insert an id say 115, then to maintain the sorted order, we have to shift all element after 110 to right.

Lets we want to delete an id 110 from sorted array, then to maintain the sorted order we have to shift all the element to left. Now the sorted array become [100, 120,130,140].

Advantage of Linked List

• Linked List is dynamic in nature which allocates memory when required. You don't need to specify the size while creating the linked list.
• Ease of insertion and deletion.
• Stack and queue can be easily implemented using linked list.

Disadvantage of Linked List

• Memory is wasted as reference need to maintained for next node.
• Random access of nodes is not possible. We have to access the node sequentially from starting of the first node.
• Not cache friendly. Node stored in non-continuous address location.

Type of Linked List

There is three type of linked list. They are

1. Singly Linked List
2. Doubly Linked List
3. Circularly Linked List

Let's know more about them and how they are different from each other.

---

Singly Linked List

Singly linked list is a collection of nodes that collectively form a linear sequence. In a singly linked list, each node stores data, and as well as a reference to the next node of the list.

---

Doubly Linked List

The doubly linked contain data and an explicit reference to the node before it and a reference to the node after it.

---

Circularly Linked List

The circularly linked list is almost same as singly linked list, only difference is that the last node of it holds the reference to first node hence forming the circular chain.