## Algorithm

A linked list is a fundamental data structure in computer science used to organize and store data. It consists of a sequence of elements, called nodes, where each node contains a data field and a reference (link or pointer) to the next node in the sequence. Linked lists offer dynamic memory allocation, efficient insertion and deletion of elements, and are particularly useful when the size of the data is not known in advance.

Here's a comprehensive overview of linked lists:

### Basic Components of a Linked List:

1. Node:

• A basic building block of a linked list.
• Contains data (payload) and a reference to the next node.

• The first node in a linked list.
• Serves as the entry point for accessing the list.
3. Tail:

• The last node in a linked list.
• Points to `null` or an indication that it is the end of the list.

• Each node points to the next node in the sequence.
• Simple and memory-efficient.

• Each node points to both the next and the previous node.
• Supports bidirectional traversal.

• The last node points back to the first node, forming a circle.
• Useful in applications where the list needs to be traversed endlessly.

1. Insertion:

• Adding a new node to the list.
• Three main types:
• Insertion at the beginning.
• Insertion at the end.
• Insertion at a specific position.
2. Deletion:

• Removing a node from the list.
• Three main types:
• Deletion at the beginning.
• Deletion at the end.
• Deletion at a specific position.
3. Traversal:

• Visiting each node in the list to perform a specific operation.
4. Searching:

• Locating a node with a specific value.
5. Merging:

• Combining two linked lists into one.

1. Dynamic Size:

• Easily accommodates varying amounts of data.
2. Efficient Insertion and Deletion:

• Adding or removing elements doesn't require moving other elements.
3. No Wasted Memory:

• Allocates memory as needed.

1. Random Access:

• Accessing elements by index is slower compared to arrays.
2. Extra Memory:

• Requires extra memory for storing the pointers

## Code Examples

### #1 Linked List Operations: Traverse, Insert and Delete implement in java

```Code - Java Programming```

``````class Node {
int data;
Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

// Traverse the linked list and print each element
public void traverse() {
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}

// Insert a new node at the end of the linked list
public void insert(int data) {
Node newNode = new Node(data);

} else {
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
}

// Delete a node with a given data value from the linked list
public void delete(int data) {
System.out.println("List is empty. Nothing to delete.");
return;
}

return;
}

Node prev = null;

while (current != null && current.data != data) {
prev = current;
current = current.next;
}

if (current == null) {
} else {
prev.next = current.next;
}
}
}

public class Main {
public static void main(String[] args) {

// Insert elements

// Traverse and print elements

// Delete an element

// Traverse and print elements after deletion
}
}
``````
Copy The Code &

### #2 Linked List Operations: Traverse, Insert and Delete implement in Python

```Code - Python Programming```

``````class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def traverse(self):
while current:
print(current.data, end=" -> ")
current = current.next
print("None")

def insert(self, data):
new_node = Node(data)
else:
while current.next:
current = current.next
current.next = new_node

def delete(self, data):

# Case: Deleting the head node
if current and current.data == data:
del current
return

# Case: Deleting a node in the middle or at the end
prev = None
while current and current.data != data:
prev = current
current = current.next

if current is None:
return

prev.next = current.next
del current

# Example usage:

# Inserting nodes

# Traversing the list

# Deleting a node

# Traversing again after deletion
``````
Copy The Code &

### #3 Linked List Operations: Traverse, Insert and Delete implement in C

```Code - C Programming```

``````#include <stdio.h>
#include <stdlib.h>

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

// Function to traverse the linked list
}
printf("\n");
}

// Function to insert a new node at the end of the linked list
void insert(struct Node** head, int newData) {
// Allocate memory for the new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = newData;
newNode->next = NULL;

// If the linked list is empty, make the new node the head
return;
}

// Traverse to the end of the linked list
while (last->next != NULL) {
last = last->next;
}

// Insert the new node at the end
last->next = newNode;
}

// Function to delete a node with a given key from the linked list
void deleteNode(struct Node** head, int key) {
// If the linked list is empty, return
return;
}

// If the key is in the head node
free(temp);
return;
}

// Traverse the linked list to find the node with the key
struct Node* prev = NULL;
while (current != NULL && current->data != key) {
prev = current;
current = current->next;
}

// If the key is not present
if (current == NULL) {
return;
}

prev->next = current->next;

// Free the memory of the deleted node
free(current);
}

// Main function for testing
int main() {

// Insert some nodes

// Traverse and print the linked list

// Delete a node with key 2

// Traverse and print the linked list after deletion

return 0;
}
``````
Copy The Code &

### #4 Linked List Operations: Traverse, Insert and Delete implement in C++

```Code - C++ Programming```

``````#include <iostream>

// Node structure for the linked list
struct Node {
int data;
Node* next;

// Constructor to initialize a new node
Node(int value) : data(value), next(nullptr) {}
};

private:

public:
// Constructor to initialize an empty linked list

// Function to traverse and print the elements of the linked list
void traverse() {
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}

// Function to insert a new node at the end of the linked list
void insert(int value) {
Node* newNode = new Node(value);

} else {
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}

// Function to delete a node with a specific value from the linked list
void deleteNode(int value) {
Node* prev = nullptr;

// Traverse the list to find the node with the given value
while (current != nullptr && current->data != value) {
prev = current;
current = current->next;
}

if (current == nullptr) {
std::cout << "Node with value " << value << " not found." << std::endl;
return;
}

// If the node to be deleted is the head
if (prev == nullptr) {
} else {
prev->next = current->next;
}

delete current; // Free the memory of the deleted node
}
};

// Example usage
int main() {

// Inserting elements
myList.insert(1);
myList.insert(2);
myList.insert(3);

// Traversing and printing elements
myList.traverse();

// Deleting a node
myList.deleteNode(2);

// Traversing and printing elements after deletion
std::cout << "Linked List after deletion: ";
myList.traverse();

return 0;
}
``````
Copy The Code &