Introduction to Singly LinkedList
Linked-List
Fundamentals (Single LL)
Editorial
Imagine a train with a series of carriages connected together. Each carriage can be added or removed independently without disturbing the others. This is similar to a linked list, where each element (carriage) points to the next, allowing for flexible addition and removal.
In contrast, think of an array as a train where all carriages are welded together. Adding or removing a carriage in the middle would require shifting all the subsequent carriages, making the process laborious and inefficient.
So, if you frequently need to add or remove carriages (elements) in your application, a linked list is like having a train with detachable carriages, providing greater flexibility and efficiency.
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.
Difference Between
What is a Linked List ?
A linked list is a linear data structure resembling a chain, where each node is connected to the next, and each node represents an individual element. Unlike arrays, the elements in a linked list are not stored in contiguous memory locations. In arrays, adding a new element requires the next memory location to be empty, which cannot always be guaranteed. Therefore, expanding an array beyond its initial size can be challenging and inefficient. This limitation is not present in linked lists, which can dynamically grow and shrink as needed.
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.
Why Linked List over arrays ?
Unlike arrays, the size of the Linked List can be decreased or increased at any location and at any point of time efficiently.Difference Between Struct and Class in Linked Lists
| Aspect | Struct | Class |
|---|---|---|
| Definition | A struct is a user-defined data type that groups together different data types to form a single unit. It is primarily used for simple data structures. |
A class is a blueprint for creating objects, providing more advanced features such as inheritance, encapsulation, and polymorphism. |
| Access Control | By default, all members of a struct are public. |
By default, all members of a class are private. |
| Usage in Linked Lists | Often used for defining the nodes in a simple linked list where each node typically contains data and a pointer to the next node. | Used for defining more complex linked list structures that require encapsulation and additional functionality, such as methods for insertion, deletion, and traversal. |
| Memory Management | Typically used in simpler scenarios with straightforward memory management, often using stack allocation. | More suitable for dynamic memory management using heap allocation, allowing for more control over the lifecycle of linked list nodes. |
| Example |
struct Node {
int data;
Node* next;
};
|
class Node {
private:
int data;
Node* next;
public:
Node(int data) : data(data), next(nullptr) {}
int getData() { return data; }
Node* getNext() { return next; }
void setNext(Node* nextNode) { next = nextNode; }
};
|
Creating a Linked List
12345678910111213141516171819202122232425262728293031323334353637383940
#include<bits/stdc++.h>
using namespace std;
struct Node {
public:
int data;
Node* next;
public:
Node(int data1, Node* next1) {
data = data1;
next = next1;
}
};
int main() {
vector<int> arr = {2, 5, 8, 7};
/*Assigning values to
the nodes*/
Node* y1 = new Node(arr[0], nullptr);
Node* y2 = new Node(arr[1], nullptr);
Node* y3 = new Node(arr[2], nullptr);
Node* y4 = new Node(arr[3], nullptr);
/**Linking of
* Nodes*/
y1->next = y2;
y2->next = y3;
y3->next = y4;
/**Printing Nodes with their
* values and data*/
cout << y1->data << " " << y1->next << "\n";
cout << y2->data << " " << y2->next << "\n";
cout << y3->data << " " << y3->next << "\n";
cout << y4->data << " " << y4->next << "\n";
return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
import java.util.*;
class Node {
public int data;
public Node next;
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
public class Main {
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<>();
arr.add(2);
arr.add(5);
arr.add(8);
arr.add(7);
/*
* Assigning values to
* the nodes
*/
Node y1 = new Node(arr.get(0), null);
Node y2 = new Node(arr.get(1), null);
Node y3 = new Node(arr.get(2), null);
Node y4 = new Node(arr.get(3), null);
/*
* Linking of
* Nodes
*/
y1.next = y2;
y2.next = y3;
y3.next = y4;
/*
* Printing Nodes with their
* values and data
*/
System.out.println(y1.data + " " + y1.next);
System.out.println(y2.data + " " + y2.next);
System.out.println(y3.data + " " + y3.next);
System.out.println(y4.data + " " + y4.next);
}
}
12345678910111213141516171819202122232425262728293031323334
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
if __name__ == "__main__":
arr = [2, 5, 8, 7]
"""
Assigning values to
the nodes
"""
y1 = Node(arr[0], None)
y2 = Node(arr[1], None)
y3 = Node(arr[2], None)
y4 = Node(arr[3], None)
"""
Linking of
Nodes
"""
y1.next = y2
y2.next = y3
y3.next = y4
"""
Printing Nodes with their
values and data
"""
print(f"{y1.data} {y1.next}")
print(f"{y2.data} {y2.next}")
print(f"{y3.data} {y3.next}")
print(f"{y4.data} {y4.next}")
12345678910111213141516171819202122232425262728293031323334353637383940414243
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
function main() {
const arr = [2, 5, 8, 7];
/*
* Assigning values to
* the nodes
*/
const y1 = new Node(arr[0]);
const y2 = new Node(arr[1]);
const y3 = new Node(arr[2]);
const y4 = new Node(arr[3]);
/*
* Linking of
* Nodes
*/
y1.next = y2;
y2.next = y3;
y3.next = y4;
/*
* Printing Nodes with their
* values and data
*/
printNode(y1);
printNode(y2);
printNode(y3);
printNode(y4);
}
function printNode(node) {
console.log(`Node data: ${node.data}, Next node: ${node.next ? node.next.data : null}`);
}
main();
Let's break this code to understand how it works:
- The struct has two data types:
datawhich contains the value of the node and a pointernext, which points to the next node in the list. - There is a constructor which assigns the values to a new node.
- A
newkeyword is used to dynamically allocate memory to a node withdataasarr[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.
Pointers are a powerful feature in C++ that enable dynamic memory allocation and the creation of complex data structures like linked lists, trees, and graphs. They are declared using an asterisk (*) before the pointer name, and the address-of operator (&) is used to obtain the memory address of a variable.
For example, if you have a variable int x = 10;, a pointer to this variable can be declared as int* ptr = &x;. The pointer ptr now holds the memory address of x. You can access the value of x indirectly through the pointer by using the dereference operator (*), like this: *ptr.
Pointers are essential for efficient memory management and are widely used in low-level programming, performance optimization, and working with advanced data structures. Understanding how to use pointers effectively can greatly enhance your ability to write efficient and powerful C++ programs.
123456789101112131415161718192021222324
#include <bits/stdc++.h>
using namespace std;
int main() {
int x = 10;
// Declare a pointer and assign it the address of x
int* ptr = &x;
// Print the value of x and the address of x
cout << "Value of x: " << x << endl;
cout << "Address of x: " << &x << endl;
// Print the value stored in ptr and the value pointed to by ptr
cout << "Value stored in ptr (address of x): " << ptr << endl;
cout << "Value pointed to by ptr: " << *ptr << endl;
// Modify the value of x using the pointer
*ptr = 20;
// Print the new value of x
cout << "New value of x after modification: " << x << endl;
return 0;
}
Value of x: 10
Address of x: 0x7ffde8dbc7e4
Value stored in ptr (address of x): 0x7ffde8dbc7e4
Value pointed to by ptr: 10
New value of x after modification: 20
Difference Between Node and Node*
In C++, the terms Node and Node* are related but refer to different concepts:
-
Node:- This represents a variable of type
Node. - It is an instance of the
Nodestructure or class. - When you declare a variable as
Node, it directly holds the data and any member variables defined in theNodestructure or class. - Example:
Node node1;creates aNodeobject namednode1.
- This represents a variable of type
-
Node*:- This represents a pointer to a
Nodetype. - It does not hold the actual data but rather the memory address where a
Nodeobject is stored. - Using a pointer allows for dynamic memory allocation, meaning you can create and manage nodes at runtime using the
newoperator. - Example:
Node* nodePtr = new Node();creates a pointer to a dynamically allocatedNodeobject.
- This represents a pointer to a
Memory Space
Let's consider storing integers. A key difference between arrays and linked lists is their memory usage. For arrays, each integer takes up 4 bytes of memory. In contrast, linked lists store both data and a pointer in each node, so the memory usage depends on the system configuration.
Therefore, on a 64-bit system, linked lists use more memory compared to a 32-bit system.
Applications of Linked Lists:
- Creating Data Structures: Linked lists serve as the foundation for building other dynamic data structures, such as stacks and queues.
- Dynamic Memory Allocation: Dynamic memory allocation relies on linked lists to manage and allocate memory blocks efficiently.
- Web Browser: Web browsers use linked lists to manage the history of visited pages.
Types of Linked List
- Singly Linked Lists: In a singly linked list, each node points to the next node in the sequence. Traversal is straightforward but limited to moving in one direction, from the head to the tail.
- Doubly Linked Lists: In this type, each node points to both the next node and the previous node, allowing for bidirectional connectivity.
- Circular Linked Lists: In a circular linked list, the last node points back to the head node, forming a closed loop.
Convert an array to Linked List
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
#include <bits/stdc++.h>
using namespace std;
// Define a Node structure
struct Node {
int data;
Node* next;
// Constructor to initialize a new node
Node(int val) : data(val), next(nullptr) {}
};
// Function to convert an array to a linked list
Node* arrayToLinkedList(int arr[], int size) {
if (size == 0) return nullptr;
// Create head of the linked list
Node* head = new Node(arr[0]);
Node* current = head;
/* Iterate through the array
and create linked list nodes*/
for (int i = 1; i < size; i++) {
current->next = new Node(arr[i]);
current = current->next;
}
return head;
}
// Function to print the linked list
void printLinkedList(Node* head) {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "nullptr" << endl;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
// Convert array to linked list
Node* head = arrayToLinkedList(arr, size);
// Print the linked list
printLinkedList(head);
return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
import java.util.*;
class Node {
int data;
Node next;
// Constructor to initialize a new node
Node(int val) {
data = val;
next = null;
}
}
public class LinkedList {
// Function to convert an array to a linked list
public static Node arrayToLinkedList(int[] arr) {
int size = arr.length;
if (size == 0) return null;
// Create head of the linked list
Node head = new Node(arr[0]);
Node current = head;
/* Iterate through the array
and create linked list nodes */
for (int i = 1; i < size; i++) {
current.next = new Node(arr[i]);
current = current.next;
}
return head;
}
// Function to print the linked list
public static void printLinkedList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
// Convert array to linked list
Node head = arrayToLinkedList(arr);
// Print the linked list
printLinkedList(head);
}
}
123456789101112131415161718192021222324252627282930313233343536373839
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to convert an array to a linked list
def arrayToLinkedList(arr):
size = len(arr)
if size == 0:
return None
# Create head of the linked list
head = Node(arr[0])
current = head
# Iterate through the array and create linked list nodes
for i in range(1, size):
current.next = Node(arr[i])
current = current.next
return head
# Function to print the linked list
def printLinkedList(head):
current = head
while current is not None:
print(f"{current.data} -> ", end="")
current = current.next
print("None")
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5]
# Convert array to linked list
head = arrayToLinkedList(arr)
# Print the linked list
printLinkedList(head)
1234567891011121314151617181920212223242526272829303132333435363738394041424344
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Function to convert an array to a linked list
function arrayToLinkedList(arr) {
const size = arr.length;
if (size === 0) return null;
// Create head of the linked list
let head = new Node(arr[0]);
let current = head;
/* Iterate through the array
and create linked list nodes */
for (let i = 1; i < size; i++) {
current.next = new Node(arr[i]);
current = current.next;
}
return head;
}
// Function to print the linked list
function printLinkedList(head) {
let current = head;
while (current !== null) {
process.stdout.write(current.data + " -> ");
current = current.next;
}
console.log("null");
}
const arr = [1, 2, 3, 4, 5];
// Convert array to linked list
const head = arrayToLinkedList(arr);
// Print the linked list
printLinkedList(head);
Output:-
1 -> 2 -> 3 -> 4 -> 5 -> nullptr
Length of Linked List
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
#include <bits/stdc++.h>
using namespace std;
// Define a Node structure
struct Node {
int data;
Node* next;
// Constructor to initialize a new node
Node(int val) : data(val), next(nullptr) {}
};
// Function to convert an array to a linked list
Node* arrayToLinkedList(int arr[], int size) {
if (size == 0) return nullptr;
// Create head of the linked list
Node* head = new Node(arr[0]);
Node* current = head;
/* Iterate through the array
and create linked list nodes */
for (int i = 1; i < size; i++) {
current->next = new Node(arr[i]);
current = current->next;
}
return head;
}
// Function to print the linked list
void printLinkedList(Node* head) {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "nullptr" << endl;
}
// To calculate length of linked list
int lengthOfLinkedList(Node* head) {
int length = 0;
Node* current = head;
// Count the nodes
while (current != nullptr) {
length++;
current = current->next;
}
return length;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
// Convert array to linked list
Node* head = arrayToLinkedList(arr, size);
// Print the linked list
printLinkedList(head);
// Calculate the length of the linked list
int length = lengthOfLinkedList(head);
cout << "Length of the linked list: " << length << endl;
return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
import java.util.*;
class Node {
int data;
Node next;
// Constructor to initialize a new node
Node(int val) {
data = val;
next = null;
}
}
// Function to convert an array to a linked list
public class LinkedList {
public static Node arrayToLinkedList(int[] arr) {
int size = arr.length;
if (size == 0) return null;
// Create head of the linked list
Node head = new Node(arr[0]);
Node current = head;
/* Iterate through the array
and create linked list nodes */
for (int i = 1; i < size; i++) {
current.next = new Node(arr[i]);
current = current.next;
}
return head;
}
// Function to print the linked list
public static void printLinkedList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
// To calculate length of linked list
public static int lengthOfLinkedList(Node head) {
int length = 0;
Node current = head;
// Count the nodes
while (current != null) {
length++;
current = current.next;
}
return length;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
// Convert array to linked list
Node head = arrayToLinkedList(arr);
// Print the linked list
printLinkedList(head);
// Calculate the length of the linked list
int length = lengthOfLinkedList(head);
System.out.println("Length of the linked list: " + length);
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
#include <bits/stdc++.h>
using namespace std;
// Define a Node structure
struct Node {
int data;
Node* next;
// Constructor to initialize a new node
Node(int val) : data(val), next(nullptr) {}
};
// Function to convert an array to a linked list
Node* arrayToLinkedList(int arr[], int size) {
if (size == 0) return nullptr;
// Create head of the linked list
Node* head = new Node(arr[0]);
Node* current = head;
/* Iterate through the array
and create linked list nodes */
for (int i = 1; i < size; i++) {
current->next = new Node(arr[i]);
current = current->next;
}
return head;
}
// Function to print the linked list
void printLinkedList(Node* head) {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "nullptr" << endl;
}
// To calculate length of linked list
int lengthOfLinkedList(Node* head) {
int length = 0;
Node* current = head;
// Count the nodes
while (current != nullptr) {
length++;
current = current->next;
}
return length;
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
// Convert array to linked list
Node* head = arrayToLinkedList(arr, size);
// Print the linked list
printLinkedList(head);
// Calculate the length of the linked list
int length = lengthOfLinkedList(head);
cout << "Length of the linked list: " << length << endl;
return 0;
}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Function to convert an array to a linked list
function arrayToLinkedList(arr) {
const size = arr.length;
if (size === 0) return null;
// Create head of the linked list
let head = new Node(arr[0]);
let current = head;
/* Iterate through the array
and create linked list nodes */
for (let i = 1; i < size; i++) {
current.next = new Node(arr[i]);
current = current.next;
}
return head;
}
// Function to print the linked list
function printLinkedList(head) {
let current = head;
while (current !== null) {
process.stdout.write(current.data + " -> ");
current = current.next;
}
console.log("null");
}
// To calculate length of linked list
function lengthOfLinkedList(head) {
let length = 0;
let current = head;
// Count the nodes
while (current !== null) {
length++;
current = current.next;
}
return length;
}
const arr = [1, 2, 3, 4, 5];
// Convert array to linked list
const head = arrayToLinkedList(arr);
// Print the linked list
printLinkedList(head);
// Calculate the length of the linked list
const length = lengthOfLinkedList(head);
console.log("Length of the linked list:", length);
Output:-
1 -> 2 -> 3 -> 4 -> 5 -> nullptr
Length of the linked list: 5
Search an Element in Linked List
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
#include <bits/stdc++.h>
using namespace std;
using namespace std;
// Define a Node structure
struct Node {
int data;
Node* next;
// Constructor to initialize a new node
Node(int val) : data(val), next(nullptr) {}
};
// Function to print the linked list
void printLinkedList(Node* head) {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "nullptr" << endl;
}
// To search for an element in the linked list
bool searchElement(Node* head, int target) {
Node* current = head;
// Traverse the linked list
while (current != nullptr) {
if (current->data == target) {
return true;
}
current = current->next;
}
return false;
}
int main() {
// Create a linked list manually
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
// Print the linked list
printLinkedList(head);
// Search for an element in the linked list
int target = 3;
if (searchElement(head, target)) {
cout << "Element " << target << " found in the linked list." << endl;
} else {
cout << "Element " << target << " not found in the linked list." << endl;
}
return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
import java.util.*;
class Node {
int data;
Node next;
// Constructor to initialize a new node
Node(int val) {
data = val;
next = null;
}
}
public class LinkedList {
// Function to print the linked list
public static void printLinkedList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
// To search for an element in the linked list
public static boolean searchElement(Node head, int target) {
Node current = head;
// Traverse the linked list
while (current != null) {
if (current.data == target) {
return true;
}
current = current.next;
}
return false;
}
public static void main(String[] args) {
// Create a linked list manually
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
// Print the linked list
printLinkedList(head);
// Search for an element in the linked list
int target = 3;
if (searchElement(head, target)) {
System.out.println("Element " + target + " found in the linked list.");
} else {
System.out.println("Element " + target + " not found in the linked list.");
}
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to print the linked list
def printLinkedList(head):
current = head
while current is not None:
print(f"{current.data} -> ", end="")
current = current.next
print("None")
# To search for an element in the linked list
def searchElement(head, target):
current = head
# Traverse the linked list
while current is not None:
if current.data == target:
return True
current = current.next
return False
if __name__ == "__main__":
# Create a linked list manually
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
# Print the linked list
printLinkedList(head)
# Search for an element in the linked list
target = 3
if searchElement(head, target):
print(f"Element {target} found in the linked list.")
else:
print(f"Element {target} not found in the linked list.")
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Function to print the linked list
function printLinkedList(head) {
let current = head;
while (current !== null) {
process.stdout.write(current.data + " -> ");
current = current.next;
}
console.log("null");
}
// To search for an element in the linked list
function searchElement(head, target) {
let current = head;
// Traverse the linked list
while (current !== null) {
if (current.data === target) {
return true;
}
current = current.next;
}
return false;
}
// Create a linked list manually
const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
// Print the linked list
printLinkedList(head);
// Search for an element in the linked list
const target = 3;
if (searchElement(head, target)) {
console.log(`Element ${target} found in the linked list.`);
} else {
console.log(`Element ${target} not found in the linked list.`);
}
Output:-
1 -> 2 -> 3 -> 4 -> 5 -> None
Element 3 found in the linked list.