---

We are learning this topic using c programming. Linked list is a type of data structure provided in C language to make use of pointer efficiently.

Introduction to Linked List

1. It is a data Structure which consists if a group of nodes that forms a sequence.
2. It is a very common data structure that is used to create a tree, graph, and other abstract data types.

Linked list comprise of group or list of nodes in which each node have link to next node to form a chain

Linked List definition

1. Linked List is Series of Nodes
2. Each node Consist of two Parts viz Data Part & Pointer Part
3. Pointer Part stores the address of the next node

What is linked list Node?

1. Each Linked List Consists of Series of Nodes
2. In above Diagram, Linked List Consists of three nodes A, B, C etc
3. Node A has two part one data part which consists of the 5 as data and the second part which contain the address of the next node (i.e it contain the address of the next node)

Linked list Blocks

A linked list is created using following elements –

We can represent linked list in real life using the train in which all the buggies are nodes and two coaches are connected using the connectors.

In case of a railway, we have peoples seating arrangement inside the coaches is called as data part of the lined list while a connection between two buggies is address filed of the linked list.

Like the linked list, trains also have the last coach which is not further connected to any of the buggies. The engine can be called as the first node of the linked list

Linked list Advantages

List of advantages :

1. Linked List is Dynamic Data Structure.
2. Linked List can grow and shrink during runtime.
3. Insertion and Deletion Operations are Easier
4. Efficient Memory Utilization, i.e no need to pre-allocate memory
5. Faster Access time can be expanded in constant time without memory overhead
6. Linear Data Structures such as Stack, Queue can be easy implemented using Linked list

The need of a linked list

Suppose you are writing a program which will store marks of 100 students in maths. Then our logic would be like this during compile time –

int marks[100];

Now at runtime i.e after executing the program if a number of students are 101 then how you will store the address of 101th student?

Or if you need to store only 40 students then again you are wasting memory unnecessarily.

Using linked list you can create a memory at runtime or free memory at runtime so that you will able to fulfill your need in an efficient manner

Explanation

Now we will be learning linked list advantages in more details –

1. Linked List is Dynamic in Nature

1. Linked List Data Structure is Dynamic in nature.
2. We can have to just create Linked List structure and memory will be allocated at runtime i.e while running program.
3. At runtime, we can allocate as much memory as we can.
4. Though you can allocate any number of nodes, still there is the limit for allocation of memory. (We can allocate memory considering that heap size will not be exceeded)

 

2. Insertion and Deletion Operations are easy

1. Insertion and Deletion operations in Linked List is very flexible.
2. We can insert any node at any place easily and similarly, we can remove it easily.
3. We don’t have to shift nodes like array insertion. In Insertion operation in a linked list, we have to just update next link of the node.

3. Memory Utilization

1. As explained earlier we don’t have to allocate memory at compile time.
2. Memory is allocated at runtime as per requirement so that Linked list data structure provides us strong command on memory utilization.

Linked list disadvantages

1. Wastage of Memory 

1. Pointer Requires extra memory for storage.
2. Suppose we want to store 3 integer data items then we have to allocate memory –

in case of the array –

Memory Required in Array = 3 Integer * Size
                         = 3 * 2 bytes
                         = 6 bytes

in case of the array –

Memory Required in LL    = 3 Integer * Size of Node
                         = 3 * Size of Node Structure
                         = 3 * Size(data + address pointer)
                         = 3 * (2 bytes + x bytes)
                         = 6 bytes + 3x bytes

*x is the size of complete node structure it may vary

2. No Random Access

1. In array we can access nth element easily just by using a[n].
2. In Linked list no random access is given to user, we have to access each node sequentially.
3. Suppose we have to access nth node then we have to traverse linked list n times.

Suppose Element is present at the starting location then –

We can access element in first Attempt

Suppose Element is present at the Last location then –

We can access element in last Attempt

3. Time Complexity

1. An array can be randomly accessed, while the Linked list cannot be accessed Randomly
2. Individual nodes are not stored in the contiguous memory Locations.
3. Access time for Individual Element is O(n) whereas in Array it is O(1).

4. Reverse Traversing is difficult

1. In case if we are using singly linked list then it is very difficult to traverse linked list from end.
2. If using doubly linked list then though it becomes easier to traverse from the end but still it increases again storage space for the back pointer.

5. Heap Space Restriction

1. Whenever memory is dynamically allocated, It utilizes memory from the heap.
2. Memory is allocated to Linked List at runtime if and only if there is space available in heap.
3. If there is insufficient space in heap then it won’t create any memory.

---