# Singly Linked List Data Structure

A Singly Linked List is a linear data structure in which each element called a node, contains two parts, the data and a reference to the next node in the sequence. The reference to the next node is called a pointer or a link.

Each node only stores the address of its successor node and not its predecessor. The last node in the list contains a null pointer, indicating the end of the list. Unlike arrays, linked lists do not require contiguous memory allocation, allowing for flexible size adjustments during runtime.

## Representation of a Singly Linked List

A singly linked list is a linear data structure where elements, known as nodes, are connected in a sequential order. Each node contains data and a reference (link) to the next node in the sequence. The last node typically points to null, indicating the end of the list. In this structure, each node contains two fields:

• Data: This field stores the value of the node.
• Link: This field contains the memory address of the next node in the list.
```// Define a Node structure to hold a value and
// a pointer to the next node
struct Node {
int value;
struct Node* next;
};
```
Key concepts of singly linked lists:
• Node : The basic building block containing data and a reference to the next node.

• Head : The starting point of the list, representing the first node.

• Tail : The last node in the list, where the reference points to null.

• Null : The reference in the last node, indicating the end of the list.

## Uses of Singly Linked List

Singly Linked List data structure is commonly used in situations where data needs to be stored and accessed in a sequential manner, but the size of the data is not known in advance. Some common use cases of linked list include:

• Implementing dynamic data structures such as stacks, queues, and hash tables.
• Implementing graph algorithms such as topological sort, Dijkstra's shortest path, and minimum spanning tree algorithms.
• Managing memory in operating systems and programming languages.

• Dynamic size: The size of a linked list can be changed dynamically, unlike arrays, which have a fixed size.

• Easy insertion and deletion: Singly Linked List allows easy insertion and deletion of nodes, as only the pointers need to be modified.

• Efficient memory utilization: Singly Linked List allows efficient memory utilization as nodes can be allocated as needed.

• No random access: Singly Linked List does not allow for random access of elements like arrays, as it requires sequential traversal from the head node. Accessing elements in a linked list requires traversing the list sequentially, making random access less efficient compared to arrays. Unlike arrays, which offer constant-time access to elements based on an index, linked lists require O(n) time for access, where n is the position of the element.

• Extra memory overhead: Singly Linked List requires extra memory to store the link field for each node.

## Common Singly Linked List Operations

To add a node to a Singly Linked List, we first create a new node and assign its data field with the value we want to store. We then update the link field of the new node to point to the current head node, and update the head node to point to the new node.

```void addNode(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
}
```

### Traverse a Singly Linked List

To traverse a Singly Linked List, we start at the head node and follow the link field of each node until we reach the end of the list (the node with a null pointer).

```void traverse() {
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
}
```

### Delete a Node from a Singly Linked List

To delete a node from a Singly Linked List, we need to find the node to delete and update the link field of the previous node to point to the next node. We then free the memory of the deleted node.

```void deleteNode(int value) {
Node *previous = NULL;

// Traverse the list to find the node to delete
while (current != NULL && current->data != value) {
previous = current;
current = current->next;
}

// If the node to delete is found, update the link field of the previous node
if (current != NULL) {
if (previous == NULL) {
} else {
previous->next = current->next;
}
free(current);
}
}
```

### Search an Element in Singly Linked List

To search for an element in a Singly Linked List, we start at the head node and traverse the list until we find the node with the desired value, or reach the end of the list.

```bool search(int value) {
while (current != NULL) {
if (current->data == value) {
return true;
}
current = current->next;
}
return false;
}
```

### Singly Linked List Operations Time Complexity

The time complexity of the common operations on a Singly Linked List are as follows:
• Add a node to the beginning: O(1)
• Traverse the list: O(n)
• Delete a node: O(n)
• Search an element: O(n)

## Singly Linked List Implementation Program

Now that we have an understanding of the Singly Linked List data structure and its operations, let's look at how to implement a Singly Linked List in C.

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

// Define a Node structure to hold a value and a pointer to the next node
struct Node {
int value;
struct Node* next;
};

// Allocate memory for a new node
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

// Set the value and next pointer of the new node
newNode->value = value;
newNode->next = NULL;

// If the Linked List is empty, set the head to the new node
return;
}

// Traverse to the end of the Linked List
while (current->next != NULL) {
current = current->next;
}

// Set the next pointer of the last node to the new node
current->next = newNode;
}

// Traverse the Linked List and print each value
void traverse() {
while (current != NULL) {
printf("%d ", current->value);
current = current->next;
}
printf("\n");
}

// Delete a node from the Linked List with the specified value
void deleteNode(int value) {
// If the head node contains the value, delete it and set the head to the next node
free(temp);
return;
}

// Traverse the Linked List to find the node with the value
while (current->next != NULL && current->next->value != value) {
current = current->next;
}

// If the node is not found, print an error message and return
if (current->next == NULL) {
return;
}

// Delete the node and set the next pointer of the previous node to the next node
struct Node* temp = current->next;
current->next = current->next->next;
free(temp);
}

// Search the Linked List for a node with the specified value
void search(int value) {
while (current != NULL && current->value != value) {
current = current->next;
}
if (current == NULL) {
} else {
printf("%d found in Linked List\n", value);
}
}

int main() {
// Create a Linked List with nodes containing values 3, 7, 1, and 9

// Print the initial state of the Linked List
traverse();

// Demonstrate deleting a node with value 1
deleteNode(1);
printf("Linked List after deleting 1: ");
traverse();

// Demonstrate searching for a node with value 7
search(7);

// Clean up memory by deleting all nodes in the Linked List
struct Node* temp;
while (current != NULL) {
temp = current;
current = current->next;
free(temp);
}

return 0;
}
```
Output
```Initial Linked List: 3 7 1 9
Linked List after deleting 1: 3 7 9