Linked List is a linear and dynamic data structure that consists of series of nodes connected to each other. The elements are not stored contiguously, but linked with pointers .In linked list each node stores the data and the address of the next node. The head is the pointer that stores the address of the first node.

Strengths and Drawbacks of Linked List

Strengths:

1) Fast operation at the beginning: inserting elements at beginning of a linked list is O(1).

2) Variable size : no need to specify how many elements we are going to store ahead of time.

Drawbacks:

1) Costly lookups : the time taken to access an item in a linked list is O(n).

2) Not cache-friendly : the elements are not stored contiguously.

Linked List Complexity

Types of Linked Lists:

Singly Linked List

This is the most common type of linked list. Each node has data and a next field that contains the address to the next node. In singly linked list, we can traverse the linked list in only one direction. The next pointer of the last node in singly linked list, points to NULL.

Doubly Linked List

In Doubly Linked List, each node has prev field that contains the address of the previous node, the data field and the next field that contains the address of the next node. In doubly linked list, we can traverse the linked list in both forward and backward directions.

Circular Linked List

The Circular Linked List is similar to the singly linked list. The only difference is that the last node is connected to the first node, forming a circular loop in the circular linked list.

Uses of Linked List

• Dynamic memory allocation

• Implementation of an Adjacency Matrix Graph.

• Implementation of Stacks and Queues

• Implementation of Hash Table and Graphs

---