Linked List

What is linked list? 

A linked list is a data structure that consists of a sequence of elements, called nodes, each of which contains an element of the list and a reference (or "link") to the next node in the sequence. The first node in the list is called the head, and the last node is called the tail.

There are two types of linked lists: singly linked lists and doubly linked lists.

Singly linked list: In this type of linked list, each node has a reference to the next node in the list, but not to the previous node. This means that you can only traverse the list in one direction (from head to tail)

Doubly linked list: In this type of linked list, each node has a reference to both the next and previous nodes in the list. This means that you can traverse the list in both directions (from head to tail and from tail to head).

Linked lists have several advantages over other data structures like arrays:

• They are dynamic, which means that their size can change during runtime. This makes them useful for tasks where the number of elements is not known in advance or may change over time.
• They are efficient for inserting and deleting elements at the beginning of the list, as this only requires updating the links between the nodes.
• They do not have the problem of memory fragmentation that can occur with arrays.

However, linked lists also have some disadvantages:

• They are less efficient for random access, as accessing an element requires traversing the list from the head or tail.
• They use more memory than arrays, as each node requires additional memory for the link to the next node.

Linked lists are widely used in many algorithms, like sorting, searching and mathematical computation. They are also used in many programming problems that requires dynamic memory allocation. 

Types of linked list:

There are several types of linked lists, each with their own unique characteristics and uses. Some of the most common types of linked lists include:

1. Singly linked list: In this type of linked list, each node has a reference to the next node in the list, but not to the previous node. This means that you can only traverse the list in one direction (from head to tail).

   

   Singly linked list

2. Doubly linked list: In this type of linked list, each node has a reference to both the next and previous nodes in the list. This means that you can traverse the list in both directions (from head to tail and from tail to head).

   

   Doubly linked list

3. Circular linked list: In this type of linked list, the last node points back to the first node, forming a circular loop. This allows for efficient insertion and deletion at the beginning and end of the list.

   

4. Circular doubly linked list: It is a variation of doubly linked list, where the last node points to the first node and the first node points to the last node, forming a circular loop.

   
   
   

5. Skip List: A skip list is a linked data structure that allows for efficient search, insertion and deletion of elements. It is essentially a linked list with additional "skip" pointers, that allows for faster traversal of the list.

6. XOR Linked List: In this type of linked list, instead of storing the address of next node, it stores the bitwise XOR of addresses of the current and next nodes. This makes it more memory efficient than the traditional linked list.

These are some of the most common types of linked lists, but there are many other types of linked lists as well, each with their own unique characteristics and uses

Why use linked list over and array :

Linked lists and arrays are both data structures that can be used to store and organize data, but they have different characteristics that make them more suitable for different types of problems. Here are some reasons why you might choose to use a linked list over an array:

• Dynamic size: Linked lists are dynamic data structures, which means that their size can change during runtime. This makes them useful for tasks where the number of elements is not known in advance or may change over time. On the other hand, arrays have a fixed size, which means that once an array is declared, its size cannot be changed.

• Insertions and deletions: Linked lists are efficient for inserting and deleting elements at the beginning of the list, as this only requires updating the links between the nodes. On the other hand, in an array, inserting or deleting an element at a specific position is an expensive operation, as it requires shifting the elements to make room for the new element or fill the gap left by the deleted element.

• Memory usage: Linked lists use more memory than arrays, as each node in a linked list requires additional memory for the link to the next node. However, arrays have a problem of memory fragmentation when deleted elements are not compacted, and the array becomes full.

• Searching: Linked lists are less efficient for searching an element, as it requires traversing the list from the head or tail. On the other hand, arrays are efficient for accessing elements by index, which makes them suitable for tasks such as searching and sorting.

In conclusion, linked lists and arrays both have their own advantages and disadvantages, it depends on the specific problem that needs to be solved, and the trade-offs that are acceptable. In general, linked lists are better suited for problems that require dynamic memory allocation and constant insertions/deletions, while arrays are better suited for problems that require efficient random access and a fixed number of elements.

Difference between array and linked list

Array and Linked List are both linear data structures that are used to store and organize data, but they have different characteristics and are more suitable for different types of problems.

The main differences between arrays and linked lists are:

• Memory allocation: Arrays are stored in contiguous memory locations, which means that all elements are stored next to each other in memory. Linked lists, on the other hand, are stored non-contiguously, with each element stored in a separate memory location, and each element pointing to the next element.

• Size: Arrays have a fixed size, which means that once an array is declared, its size cannot be changed. Linked lists, on the other hand, are dynamic data structures, which means that their size can change during runtime. This makes linked lists more suitable for tasks where the number of elements is not known in advance or may change over time.

• Accessing elements: In an array, elements can be accessed directly by specifying the index. Linked lists, on the other hand, are accessed by traversing the list from the head or tail. This makes arrays more efficient for random access and searching, while linked lists are more efficient for inserting and deleting elements.

• Memory usage: Arrays use less memory than linked lists, as they store all elements in contiguous memory locations. However, linked lists are more efficient in terms of memory usage when frequent insertions and deletions are needed.

In summary, arrays and linked lists are both linear data structures, but they have different characteristics and are more suitable for different types of problems. Arrays are more efficient for random access and searching, while linked lists are more efficient for dynamic memory allocation and constant insertions/deletions