Linked list

Linked list

A linked list is a fundamental data structure used in computer science and programming. It consists of a sequence of elements, called nodes, where each node contains some data and a reference (or pointer) to the next node in the sequence.

struct Node{
       int data;
       struct Node* next;
       };

Here are some key points about linked lists:

1. Nodes: Each node in a linked list contains two components: the data itself and a reference (or pointer) to the next node in the sequence.
2. Head: The first node of a linked list is called the head. It serves as the starting point for traversing the list.
3. Tail: The last node in the linked list, whose next pointer is typically set to null, indicates the end of the list.
4. Types of Linked Lists:
   • Singly Linked List: In this type, each node only has a reference to the next node in the sequence.
   • Doubly Linked List: In a doubly linked list, each node has references to both the next and the previous nodes in the sequence.
   • Circular Linked List: In this type, the last node’s reference points back to the head, forming a circular structure.
5. Dynamic Size: Linked lists can dynamically grow or shrink in size during program execution, unlike arrays which have a fixed size.
6. Insertion and Deletion: Inserting and deleting elements from a linked list can be efficient compared to arrays, especially when dealing with large lists. However, accessing elements by index in a linked list is less efficient than in an array since linked lists do not have direct access to elements by index.

Linked list vs Array

Linked lists and arrays are both fundamental data structures used in programming, but they have different characteristics and are suitable for different scenarios. Here’s a comparison between linked lists and arrays:

1. Memory Allocation:
   • Arrays: Arrays allocate memory in a contiguous block, meaning all elements are stored in adjacent memory locations.
   • Linked Lists: Linked lists use dynamic memory allocation. Each node can be scattered in memory, and they are connected through pointers.
2. Insertion and Deletion:
   • Arrays: Insertion and deletion operations in arrays can be inefficient, especially if elements need to be shifted to accommodate the change.
   • Linked Lists: Linked lists are efficient for insertion and deletion, especially when done at the beginning or end of the list, as they require adjusting pointers without shifting elements.
3. Access Time:
   • Arrays: Arrays offer constant-time access to elements using an index.
   • Linked Lists: Linked lists have variable access time. Accessing elements by index in a linked list requires traversing the list from the beginning, resulting in linear time complexity.
4. Memory Overhead:
   • Arrays: Arrays have a fixed size, which may lead to memory wastage if the array size is larger than required.
   • Linked Lists: Linked lists use additional memory for storing pointers, which can increase memory overhead compared to arrays.
5. Dynamic Size:
   • Arrays: Arrays have a fixed size, and resizing them can be inefficient as it may involve creating a new array and copying elements.
   • Linked Lists: Linked lists can dynamically grow or shrink in size during program execution without the need for resizing operations.
6. Cache Efficiency:
   • Arrays: Arrays have better cache locality, as elements are stored contiguously, leading to better performance when accessing elements sequentially.
   • Linked Lists: Linked lists have poor cache locality due to scattered memory locations of nodes, which may result in cache misses during traversal.
7. Implementation Complexity:
   • Arrays: Arrays have a simple implementation and are supported by most programming languages with built-in syntax for array operations.
   • Linked Lists: Linked lists require more complex implementation due to managing pointers and memory allocation. However, they offer flexibility and efficiency for certain operations.