What is a Linked List?

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are called nodes. Each node contains a data field and a reference(link) to the next node in the list.

The elements in a linked list are linked using pointers as shown in the below image:

Types of Linked List

There are two types of linked lists:

1. Singly Linked List

2. Doubly Linked List

   
   There is also a variation of the linked list called a circular linked list.

Singly Linked List

In a singly linked list, each node contains a data field and a reference(link) to the next node in the list.

Doubly Linked List

In a doubly linked list, each node contains a data field, and two references (link) fields, one to the next node in the list and one to the previous node in the list.

Circular Linked List

A circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or a doubly circular linked list.

Advantages of Linked List

1. Dynamic size
2. Ease of insertion/deletion

Disadvantages of Linked List

1. Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary searches with linked lists.
2. Extra memory space for a pointer is required with each element of the list.
3. Not cache-friendly. Since array elements are contiguous locations, there is the locality of reference which is not there in the case of linked lists.

Applications of Linked List

1. Implementation of stacks, graphs and queues
2. Used in undoing functionality at many places like editors, photoshop.
3. Used in Hash Table implementation
4. Used in Operating systems for process management
5. Used in File System for file management
6. Used in Memory management
7. Used in Garbage Collection

Summary

1. The Linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.
2. Each node contains a data field and a reference(link) to the next node in the list.
3. There are two types of linked lists: singly linked lists and doubly linked lists.
4. There is also a variation of the linked list called a circular linked list.
5. Advantages of linked list: Dynamic size, Ease of insertion/deletion
6. Disadvantages of linked list: Random access is not allowed, Extra memory space for a pointer is required with each element of the list, Not cache-friendly.
7. Applications of linked list: Implementation of stacks, graphs and queues, Used in undoing functionality at many places like editors, photoshop.

I'll be writing a lot on Data structures and Algorithms so follow and let's learn together 🚀.

Here's the repo for all the DSAs I've covered so far: github.com/princecodes247/20-days-of-dsa

Thanks for reading ✨️

Contributing

If you have any suggestions or improvements, feel free to open an issue or pull a request.