Last Updated on July 27, 2023 by Mayank Dham
Doubly linked lists exhibit versatility as a data structure, facilitating bidirectional traversal and seamless insertion and deletion of elements. They prove invaluable in diverse programming scenarios, providing elegant solutions to numerous challenges. An intriguing problem that commonly arises is determining whether a doubly linked list of characters forms a palindrome.
A palindrome is a sequence of characters that reads the same forwards and backwards. When dealing with doubly linked lists, this concept extends to checking whether the list remains unchanged when traversed in both directions, forming a palindrome-like structure.
Let’s look into our problem “How to check doubly linked list of character is palindrome?”
How To Check Palindrome In Doubly Linked List
This question is relatively straightforward. We need to verify whether the given doubly linked list of characters is a palindrome or not. A list is considered a palindrome if it reads the same both backward and forward.
Input:
Output: Palindrome
Explanation: The given list of characters is palindrome.
We can use the two-pointers method to solve this. Can you guess why we are using the two-pointers method? Yes, with the help of this method, we can solve this problem by only doing a single traversal of the given list. This approach is going to take O(n) time. Let us have a glance at the approach.
Approach For Checking Palindrome In Doubly Linked List
As mentioned earlier, we are going to use the two pointers technique here. We will create two pointers, left and right. The left pointer will point at the head of the list, while the right pointer will point at the end of the list. To make the right pointer point to the end of the list, we will make it initially point to the head. Then, we will increment it till we reach the end of the list.
Now, we have a clear idea about the approach for palindrome words list, let’s see the algorithm for implementing “How to check doubly linked list of character is palindrome?
Algorithm To Check Palindrome In Doubly Linked List
- Initialize two pointers, left and right. Left will point at the head of the list and right will point at the tail of the list.
- To make the right pointer point to the tail of the list, first, make it point to the head. Then, traverse till the end and keep increasing the right pointer. In the end, it will point at the tail.
- Compare the values at the left node and the right node. If they are equal, then increment the left pointer and decrement the right pointer till the middle of the given list.
- If, at any point, the value at the left node is not equal to the value at the right node, return false.
- In the end, return true.
Dry Run To Check Palindrome In Doubly Linked List
Code Implementation To Check If characters is Palindrome in Doubly Linked List
#includeusing namespace std; struct Node { char data; struct Node *next; struct Node *prev; }; void push(struct Node** head_ref, char new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); new_node->prev = NULL; if ((*head_ref) != NULL) (*head_ref)->prev = new_node ; (*head_ref) = new_node; } bool isPalindrome(struct Node *left) { if (left == NULL) return true; struct Node *right = left; while (right->next != NULL) right = right->next; while (left != right) { if (left->data != right->data) return false; left = left->next; right = right->prev; } return true; } int main() { struct Node* head = NULL; push(&head, 'c'); push(&head, 'i'); push(&head, 'v'); push(&head, 'i'); push(&head, 'c'); if (isPalindrome(head)) printf("Palindrome"); else printf("Not Palindrome"); return 0; }
public class PrepBytes
{
// Structure of node
static class Node
{
char data;
Node next;
Node prev;
};
static Node push(Node head_ref, char new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
new_node.prev = null;
if (head_ref != null)
head_ref.prev = new_node ;
head_ref = new_node;
return head_ref;
}
static boolean isPalindrome(Node left)
{
if (left == null)
return true;
Node right = left;
while (right.next != null)
right = right.next;
while (left != right)
{
if (left.data != right.data)
return false;
left = left.next;
right = right.prev;
}
return true;
}
public static void main(String[] args)
{
Node head = null;
head = push(head, 'c');
head = push(head, 'i');
head = push(head, 'v');
head = push(head, 'i');
head = push(head, 'c');
if (isPalindrome(head))
System.out.printf("It is Palindrome");
else
System.out.printf("Not Palindrome");
}
}
Output
Palindrome
Time Complexity To Check Palindrome In Doubly Linked List: O(n), as list traversal is needed.
Conclusion
In conclusion, the proficiency to detect palindromes in doubly linked lists empowers developers to efficiently address intricate challenges. Throughout this article, we delved into the intricacies of identifying palindromes in character sequences within doubly linked lists. By following a step-by-step algorithm and gaining a comprehensive understanding of palindrome properties, readers are now equipped to confidently tackle this problem.
FAQ related to How to check doubly linked list of character is palindrome.
Here are a few FAQs on the program to check palindrome words list of doubly linked lists.
Q1. What is a doubly linked list?
A doubly linked list is a data structure consisting of nodes where each node contains two pointers: one pointing to the previous node (called the ‘prev’ pointer) and another pointing to the next node (called the ‘next’ pointer). This bidirectional linkage allows for easy traversal in both directions, making it versatile for various programming scenarios.
Q2. What is a palindrome?
In the context of character sequences, a palindrome is a sequence of characters that reads the same forwards and backwards. For example, "radar" and "level" are palindromes, while "hello" and "world" are not.
Q3. Why is checking for palindromes in doubly linked lists important?
Checking for palindromes in doubly linked lists is crucial as it finds applications in various text processing and data manipulation tasks. It allows developers to efficiently determine if a sequence of characters remains unchanged when read in both directions, making it valuable in many programming challenges.
Q4. How does the algorithm efficiently check for palindromes in doubly linked lists?
The algorithm uses a divide-and-conquer approach to efficiently compare characters from both ends of the doubly linked list. By recursively moving towards the center of the list while comparing characters, it efficiently identifies whether the list forms a palindrome.
Q5. What are the time and space complexities of the algorithm?
The time complexity of the algorithm is O(N), where N is the number of characters in the doubly linked list. The space complexity is O(1) as the algorithm utilizes only a constant amount of additional memory.