Linked List:
A linked list is a linear data structure consisting of a sequence of elements called nodes. Each node contains two parts: data and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not have a fixed size and can dynamically grow or shrink as needed.
Representation of Singly Linked List:
In a singly linked list, each node has a data part and a next part that points to the next node in the sequence. The last node points to NULL to indicate the end of the list.
Implementation of Singly Linked List:
Here’s how a singly linked list can be implemented in C:
 // Node structure
typedef struct Node {
int data;
struct Node* next;
} Node;// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf(“Memory allocation failed\n”);
exit(EXIT_FAILURE);}
newNode->data = data;
newNode->next = NULL;
return newNode;}// Function to insert a new node at the beginning of the linked list
Node* insertAtBeginning(Node* head, int data) {Node* newNode = createNode(data);
newNode->next = head;
return newNode;}// Function to insert a new node at the end of the linked list
Node* insertAtEnd(Node* head, int data) {
Node* newNode = createNode(data);
if (head == NULL)
return newNode;
Node* current = head;
while (current->next != NULL)
current = current->next;
current->next = newNode;
return head;}// Function to display the linked list
void displayList(Node* head) {
Node* current = head;
while (current != NULL) {
printf(“%d -> “, current->data);
current = current->next;}
printf(“NULL\n”);}// Function to free memory allocated to the linked list
void freeList(Node* head) {
Node* current = head;
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp);}
}int main() {Node* head = NULL;// Inserting nodes at the beginning
head = insertAtBeginning(head, 10);
head = insertAtBeginning(head, 20);
head = insertAtBeginning(head, 30);// Inserting nodes at the end
head = insertAtEnd(head, 40);
head = insertAtEnd(head, 50);// Displaying the linked list
printf(“Linked List: “);
displayList(head);// Freeing memory
freeList(head);
return 0;}
In this implementation:
- We define a
Nodestructure to represent each node in the linked list. - We create helper functions such as
createNodeto create a new node,insertAtBeginningto insert a node at the beginning of the list, andinsertAtEndto insert a node at the end of the list. - We also have functions to display the linked list (
displayList) and free memory allocated to the linked list (freeList).
This implementation demonstrates the basic operations of singly linked lists, including node creation, insertion at the beginning and end, display, and memory deallocation.