LINKED LIST INTRODUCTION:
● A collection of elements linked together by pointers, allowing for dynamic
insertion and deletion.
● A linked list's size can be increased or decreased as needed.
● It does not take up much memory space.
TERMINOLOGIES FOR LINKED LIST:
● Node Structure: A node in a linked list typically consists of two components:
● Data: It holds the actual value or data associated with the node.
● Next Pointer: It stores the memory address (reference) of the next node in the sequence.
● Head(Start):Linked lists contain a pointer variable START(head) that stores the
address of the first node in the list.es. If START = NULL, then the linked list is
empty and contains no nodes.
● Tail(End): The last node in the list points to NULL or null ptr, indicating the end of the
list. This node is known as the tail node.
MEMORY ALLOCATION & DEALLOCATION FOR LINKED LIST:
Why malloc():
● No need to initially occupy a large amount of memory.
● Memory can be allocated as well as de-allocated as per necessity.
● It avoids the memory shortage as well as memory wastage.
● In the Linked List, data is stored in the form of nodes and at runtime memory is
allocated for creating nodes using malloc() function.
ptr = (cast-type*) malloc(byte-size);
In C, we can implement a linked list using the following code:
struct node{
int data;
struct node *next;
};
TYPES OF LINKED LIST:
There are 3 different implementations of Linked List available, they are:
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
a. Single Circular
b. Double Circular
1.Singly Linked List:
● is the most common type of Linked List. Each node has data and a pointer field
containing an address to the next node.
● Each node has two parts:
○ The first part is known as the info(data) part which holds the element.
○ Second part is known as the next(link) part which holds the address of the next
node.
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a linked list node
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) {
printf("Memory error\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning of the list
void insertAtBeginning(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
*head = newNode;
}
}
// Function to print the linked list
void printList(Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
Node* head = NULL;
// Insert nodes at the beginning
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtBeginning(&head, 30);
// Print the linked list
printf("Linked List: ");
printList(head);
return 0;
}
