Linked List

 

Why we need  Linked List ?

Think about a library where you need to keep track of books being borrowed and returned. Since the number of books can change all the time, using a fixed list like an array wouldn’t be practical. Instead, linked lists are a great option. They can easily grow or shrink whenever a book is borrowed or returned, allowing you to add or remove books without any trouble. Unlike arrays, linked lists adjust their size as needed, making them perfect for keeping track of the library’s books.

What is a Linked List ?

It is a linear data structure. Imagine a train made up of different cars, where each car represents an item. In this case, a linked list is like a train where the cars (nodes) are connected but not necessarily in a straight line in memory.

In contrast, think of an array as a row of parking spaces. Each parking space (element) is right next to the other. If you want to add a new car (element) to the row, you need an empty space directly next to it. If all the spaces are full, you can’t add more cars without rearranging everything.

With a linked list, you can easily add new cars anywhere on the train without worrying about needing an empty space next to the existing cars, making it more flexible for changing needs.

A linked list is a data structure that consists of nodes, each containing two key components: the data itself and a pointer (or reference) to the next node in the sequence. 

Creating a Linked List

To create a linked list, each node needs to store two pieces of information: the data and a pointer to the next node. To manage this, we’ll define our own data type using structs or classes.

To understand linked lists better, let’s take the help of an example:

Code

#include<bits/stdc++.h>
      using namespace std;
      class Node{
    public: // access modifier
    int data; // the data value
    Node* next; // the pointer to the next value
    public:
    // constructor
    Node (int data1, Node* next1){
        data=data1;  // Initialize data with the provided value
        next=next1;  // Initialize next with the provided
    }
    Node (int data1){
        data=data1;  // Initialize data with the provided value
        next=nullptr;  // Initialize next as null since it's the end of the list

    }
};
int main(){
    vector <int>arr={2,5,8,7};
    Node* y= new Node(arr[0]);
        cout<<y<<"\n";
    cout<<y->data<<'\n'; // returns the data stored at that memory point
}
Output:

0x11b7f90
2

Let's break this example to understand how it works:

• The struct has two data types: data which contains the value of the node and a pointer next, which points to the next node in the list.
• There is a constructor which assigns the values to a new node.
• A new keyword is used to dynamically allocate memory to a node with data as arr[0].

The combination of the given parameters and functions initializes a linked list.

Understanding Pointers

A pointer is a special type of variable that holds the memory address of another variable. In simpler words, it "points" to where data is stored in memory. This lets you access and change the data indirectly by using its memory address instead of the actual value.

Code

 int main(){
    int x=2;
    int* y=&x; // y reference x
    cout<<y<<"\n

}    

Understanding the difference between Node and Node*

A node refers to the structure that contains data and the pointer to the next node. In contrast, Node* (Node pointer) specifically denotes a pointer variable that stores the address of the Node it is pointing to.

Code 

      #include<bits/stdc++.h> 
      using namespace std;
      class Node {
    public:
        int data;         // Data stored in the node
        Node* next;       // Pointer to the next node in the linked list
        // Constructors
        Node(int data1, Node* next1) {
            data = data1;
            next = next1;
        }
        // Constructor
        Node(int data1) {
            data = data1;
            next = nullptr;
        }
};
int main() {
    vector<int> arr = {2, 5, 8, 7};
    // Create a Node 'x' with the first element of the vector and a null next reference
    Node x = Node(arr[0], nullptr);
    // Create a pointer 'y' pointing to the Node 'x'
    Node* y = &x;
    // Print the memory address of the Node 'x' using the pointer 'y'
    cout << y << '\n';
}
Output: 0x61fee4

Types of Linked Lists:

✋Thank You For Visiting✋