Tail Pointer in Linked List

The tail pointer in a linked list refers to a pointer that directly points to the last node of the list. It is an enhancement commonly used to optimize operations like insertion at the end of the list. Without a tail pointer, traversing the entire list is required to find the last node, which is inefficient.

Tail pointer Advantages

The tail pointer in a linked list serves several important purposes, depending on the specific requirements of the data structure. Here are the primary reasons for using a tail pointer:

1. Efficient Access to the Last Node

Important Questions about Tail Pointer

1. can we use head in tail both pointers in linked list

Yes, you can (and often should) use both the head and tail pointers in a linked list. Using both improves the efficiency of certain operations and provides better access to the start and end of the list.

2. Can we use only one pointer, either the head or the tail?

Yes, you can use only one pointer, either the head or the tail, in a linked list. Whether to use only one pointer or both depends on the operations you want to perform and their efficiency.

Note: The entire list can be lost if you only use a tail pointer in singly linked list.

3. How do you identify if a linked list has only one node using the head and tail pointers?

Answer:
If the head and tail pointers both point to the same node and the next pointer of that node is NULL, then the linked list has only one node.

Code Example (Singly Linked List):

4. Code to implement head and tail pointer in C

A tail pointer in C is used to efficiently keep track of the last node in a linked list. Here’s an implementation of a singly linked list with a tail pointer:

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

// Define the structure for a node
typedef struct Node {
int data; // Data to store the value
struct Node* next; // Pointer to the next node in the list
} Node;

// Define the structure for the linked list
typedef struct LinkedList {
Node* head; // Pointer to the first node (head) in the list
Node* tail; // Pointer to the last node (tail) in the list
} LinkedList;

// Function to initialize the linked list
LinkedList initializeList() {
LinkedList list;
list.head = NULL; // Initially, the head is NULL (empty list)
list.tail = NULL; // Initially, the tail is NULL (empty list)
return list;
}

// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node)); // Allocate memory for a new node
if (!newNode) {
printf("Memory allocation failed\n");
exit(EXIT_FAILURE); // Exit the program if memory allocation fails
}
newNode->data = data; // Set the data of the new node
newNode->next = NULL; // Set the next pointer to NULL (it will be the last node initially)
return newNode; // Return the created node
}

// Function to add a node to the end of the list
LinkedList append(LinkedList list, int data) {
Node* newNode = createNode(data); // Create a new node with the given data
if (list.tail == NULL) { // If the list is empty (tail is NULL)
list.head = newNode; // The new node will be both head and tail
list.tail = newNode;
} else {
list.tail->next = newNode; // Attach the new node to the end of the list
list.tail = newNode; // Update the tail to point to the new node
}
return list; // Return the modified list
}

// Function to display the list
void displayList(LinkedList list) {
Node* current = list.head; // Start from the head of the list
while (current != NULL) { // Traverse the list until we reach the end
printf("%d -> ", current->data); // Print the current node's data
current = current->next; // Move to the next node
}
printf("NULL\n"); // Indicate the end of the list
}

// Function to free the list (free memory used by the nodes)
LinkedList freeList(LinkedList list) {
Node* current = list.head; // Start from the head of the list
while (current != NULL) { // Traverse the list until we reach the end
Node* temp = current; // Store the current node in temp
current = current->next; // Move to the next node
free(temp); // Free the memory of the current node
}
list.head = NULL; // Set head to NULL (list is empty now)
list.tail = NULL; // Set tail to NULL (list is empty now)
return list; // Return the modified list (now empty)
}

// Main function to test the linked list
int main() {
LinkedList list = initializeList(); // Initialize the list

// Add nodes to the list
list = append(list, 10);
list = append(list, 20);
list = append(list, 30);

// Display the list
printf("Linked List: ");
displayList(list);

// Print the last node using the tail pointer
if (list.tail != NULL) {
printf("Last Node: %d\n", list.tail->data); // Tail points to the last node
}

// Free the memory used by the list
list = freeList(list);

return 0;
}

Output:

Linked List: 10 -> 20 -> 30 -> NULL
Last Node: 30

Explanation of the tail pointer:

• The tail pointer in a linked list is used to keep track of the last node in the list.
• This allows you to efficiently append new nodes to the end without having to traverse the entire list each time, as the tail pointer directly points to the last node.
• The tail pointer is updated every time a new node is added, ensuring it always points to the last node in the list.