Imagine you are given a task where you have to maintain a data entry of cars entering a parking lot. Since the number of cars entering will be different and may change daily, constructing a fixed-sized data structure like an array might not be helpful. This is when linked lists come into the picture, which allows us to add and remove cars easily. Unlike arrays, linked lists have a variable size and can be modified to our needs.

### What is a Linked List?

It is a linear data structure that can be visualized as a chain with different nodes connected, where each node represents a different element. The difference between arrays and linked lists is that, unlike arrays, the elements are not stored at a contiguous location.

Since for any element to be added in an array, we need the exact next memory location to be empty, and it is impossible to guarantee that it is possible. Hence adding elements to an array is not possible after the initial assignment of size.

A linked list is a data structure containing two crucial pieces of information, the first being the data and the other being the pointer to the next element. The ‘head’ is the first node, and the ‘tail’ is the last node in a linked list.

There are two information sets to store at every node, thus there is a need to create a self-defined data type to handle them. Therefore, we will use the help of structs and classes. To learn about structs and classes, you can refer to this article.

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

Code:

## C++ Code

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'; // returns the memory value
cout<<y->data<<'\n'; // returns the data stored at that memory point
}

Output:

0x11b7f90
2

## Java Code

class Node {
int data;      // the data value
Node next;      // the reference to the next Node in the linked list
// Constructors
Node(int data1, Node next1) {
this.data = data1;  // Initialize data with the provided value
this.next = next1;  // Initialize next with the provided reference
}
Node(int data1) {
this.data = data1;  // Initialize data with the provided value
this.next = null;   // Initialize next as null since it's the end of the list
}
}
public static void main(String[] args) {
int[] arr = {2, 5, 8, 7};
// Creating a new Node with the value from the array
Node y = new Node(arr[0]);
// Printing the data stored in the Node
System.out.println(y.data);
}
}

Output: 2

## Python Code

class Node:
def __init__(self, data1, next1=None):
self.data = data1
self.next = next1
# Creating a new Node with the value from the array
y = Node(2)
# Printing the data stored in the Node
print(y.data)

Output: 2

## JavaScript Code

class Node {
constructor(data1, next1 = null) {
this.data = data1;
this.next = next1;
}
}
// Creating a new Node with the value from the array
let y = new Node(2);
// Printing the data stored in the Node
console.log(y.data);

Output: 2

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

1. 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.
2. There is a constructor which assigns the values to a new node.
3. 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 variable that stores the memory address of another variable. In simpler terms, it “points” to the location in memory where data is stored. This allows you to indirectly access and manipulate data by referring to its memory address.

Code:

## C++ Code

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

Output: 0x61ff0c

Java does not explicitly use pointers or take the address of variables as you do in C++. Instead, we have reference variables. These reference variables do not directly contain memory addresses like pointers in languages such as C or C++. Instead, they hold references to objects in memory.

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:

## C++ Code

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

## Java Code

class Node {
int data;         // Data stored in the node
Node next;        // Reference to the next node in the linked list
// Constructor
public Node(int data1, Node next1) {
this.data = data1;
this.next = next1;
}
// Constructor
public Node(int data1) {
this.data = data1;
this.next = null;
}
}
public class Main {
public static void main(String[] args) {
int[] arr = {2, 5, 8, 7};
// Create a Node 'x' with the first element of the array
Node x = new Node(arr[0]);
// Create a reference 'y' pointing to the same Node 'x'
Node y = x;
// Print the reference 'y', which represents the memory address of the Node 'x'
System.out.println(y);
}
}

Output: 1dbd16a6

## Python Code

class Node:
def __init__(self, data1, next1=None):
self.data = data1
self.next = next1
# Creating a Node 'x' with the first element of the array
x = Node(2)
# Creating a reference 'y' pointing to the same Node 'x'
y = x
# Printing the reference 'y', which represents the memory address of the Node 'x'
print(y)

Output: 0x7fde9de582e0

## JavaScript Code

class Node {
constructor(data1, next1 = null) {
this.data = data1;
this.next = next1;
}
}
// Creating a Node 'x' with the first element of the array
let x = new Node(2);
// Creating a reference 'y' pointing to the same Node 'x'
let y = x;
// Printing the reference 'y', which represents the memory address of the Node 'x'
console.log(y);

Output: 1f776h

### Memory Space:

Let’s talk about assuming the data stored is integer. Another main difference between an array and a linked list is the memory used. In the case of an array, we are storing integers that consume 4 Bytes for every int, whereas in a linked list, we are storing data and a pointer at every node, so the memory used up will depend on the configuration of the system.

Therefore, in the case of a 64 Bit system, it occupies or consumes more space than a 32 Bit system.

1. Creating Data Structures: Linked lists serve as the foundation for building other dynamic data structures, such as stacks and queues.
2. Dynamic Memory Allocation: Dynamic memory allocation relies on linked lists to manage and allocate memory blocks efficiently.
3. Web Browser is one important application of Linked List.