A palindrome is a sequence of characters that reads the same in forward and reverse directions. For example, “anna.” On both backward and forward reading, it’s “anna.” A Doubly Linked List is a data structure that contains a set of sequentially linked numbers in the form of nodes.

In this article, we’ll learn about a famous problem to check whether a doubly-linked list of characters is a palindrome.

Given a doubly-linked list of characters, return true if the doubly-linked list is a palindrome. Otherwise, false. A palindrome is a sequence of characters that reads the same in forward and reverse directions. In the below example, string “ABCBA” can be read the same if it starts from node 1 or from the last node. Hence it is a palindrome.

Sample Examples

Input

Output

True

Explanation

The above doubly-linked list contains characters “abcba.” On both backward and forward reading, it’s “abcba.” Therefore it is a palindrome.

Input

Output

False

Explanation

The above doubly-linked list contains the characters “abca.” On forward reading, it’s “abca.” On backward reading, it’s “acba.” Therefore it is, not a palindrome.

Approach

The idea is quite simple. Since we’ve to check for the palindrome, we can compare the elements from start to end. If both are the same, move to the next element from the start and the previous element from the end. Keep doing this until their start < end. If the start and end elements are not equal at any point in time, return false. In the end, return true otherwise.

Algorithm

The steps are:

Create a doubly-linked list with nodes with data as characters and insert the string characters at the end. We’ll create the insert operation in the end in the same way as done in this article.

Once you’ve completed the above steps, initialize a node named “start” to the head of the doubly-linked list and make a function named “isPalindrome” to tell if the doubly-linked list is a palindrome.

In this function:

Pass the node “start” as a parameter.

First, check if the start itself is null. If yes, the list is empty; thus, return true.

Otherwise, initialize a new pointer to the point to the end node. For finding this, traverse to the end of the doubly-linked list.

Once you’ve found the end pointer, run a while loop until the start != end. In the while loop:

Keep checking if the data at the start pointer of the linked list is equal to that of the end pointer.

If it is equal, move the start to the next node of the start node and the end to the previous node of the end. If not equal, return false.

In the end, return true.

Print the value returned by the “isPalindrome” function.

Dry Run

Let’s understand the working of the algorithm using an example. For this example, we will take string = “ABCBA”. Now we will create a doubly linked list using each string character. Our doubly linked list looks like this:

Step 1

Using this doubly linked list, we will call the isPalindrome() function. Create two start and end pointers pointing to the head node. Traverse through the whole list to reach the last node. The positions of our pointers will be like this:

Step 2

The next step is to compare the data of pointers start and end. If the data on both pointers is the same, then increment the start pointer and the end pointer. As in the above figure, start = A = end, so, now the position of both pointers will be as follows:

Step 3

Since the data at start and end pointers is the same, i.e., B, we will now increment the start and decrement end pointer. Now the positions are as follows:

As now start and end pointers are pointing to the same node. This indicates that the doubly linked list forms a palindrome. So, we will return true.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
// Node structure
char data;
Node *next;
Node *prev;
// Constructor for creating a new node
Node(char value)
{
data = value;
next = prev = NULL;
}
};
Node *head = NULL;
Node *tail = NULL;
// To insert a node at the end of a Doubly Linked List
void insertAtLast(char data)
{
// Creating a new node with the given data
struct Node *newNode = new Node(data);
// Making the next of newNode as Null
newNode->next = NULL;
/*
If DLL is empty then this node will be both the first as
well as the last node
*/
if (head == NULL)
{
newNode->prev = NULL;
head = newNode;
tail = newNode;
return;
}
/*
If DLL is not empty, then insert the new node at the next
position of tail pointer and update the tail pointer.
*/
tail->next = newNode;
newNode->prev = tail;
tail=tail->next;
}
bool isPalindrome(Node *start)
{
// Check if the start itself is null. If yes, the list is empty, thus return true
if (start == NULL)
return true;
// Initialize the end node with tail pointer
Node *end = tail;
/* Keep checking if the data at the start pointer of the
linked list is equal to that of the end pointer. */
while (start != end && end != start->prev)
{
/* If the data at start is not equal to data
at end, return false.*/
if (start->data != end->data)
return false;
// Else move ahead
start = start->next;
end = end->prev;
}
return true;
}
int main()
{
// String input
string s = "abcba";
cout << "Elements of Doubly Linked list : ";
cout << s << endl;
// Insert string to doubly linked list
for (int i = 0; i < s.length(); i++)
insertAtLast(s[i]);
// Check for palindrome
Node *start = head;
if (isPalindrome(start))
cout << "Yes, Doubly Linked list forms a palindrome." << endl;
else
cout << "No, Doubly Linked list does not form a palindrome." << endl;
return 0;
}

Output

Elements of Doubly Linked list : abcba
Yes, Doubly Linked list forms a palindrome.

Implementation in Python

# Node class
class Node:
def __init__(self, value):
self.data = value
self.next = None
self.prev = None
# To insert a node at the end of a Doubly Linked List
def insertAtLast(data):
global head
global tail
# Creating a new node with the given data
newNode = Node(data)
# Making the next of newNode as None
newNode.next = None
"""
If DLL is empty then this node will be both the first as
well as the last node
"""
if head is None:
newNode.prev = None
head = newNode
tail = newNode
return
"""
If DLL is not empty, then insert the new node at the next
position of tail pointer and update the tail pointer.
"""
tail.next = newNode
newNode.prev = tail
tail=tail.next
def isPalindrome(start):
# Check if the start itself is None. If yes, the list is empty, thus return True
if start is None:
return True
# Initialize the end node with tail
end = tail
# Keep checking if the data at the start pointer of the linked list is equal to that of the end pointer.
while start != end and end != start.prev:
# If the data at start is not equal to data at end, return False.
if start.data != end.data:
return False
# Else move ahead
start = start.next
end = end.prev
return True
# String input
s = "abcba"
print("Elements of Doubly Linked list: ", s)
# Insert string to doubly linked list
head = None
for i in range(len(s)):
insertAtLast(s[i])
# Check for palindrome
start = head
if isPalindrome(start):
print("Yes, Doubly Linked list forms a palindrome.")
else:
print("No, Doubly Linked list does not form a palindrome.")

Output

Elements of Doubly Linked list : abcba
Yes, Doubly Linked list forms a palindrome.

Complexities

Time complexity

The time taken by the program is O(n), where n is the number of elements in the doubly-linked list because we’re traversing the list only once. Therefore, the complexity will be O(n).

Space complexity

The space required is constant, i.e., O(1) , because no extra space is taken here for computation.

A linked list is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node.

What is a palindrome?

A palindrome is a sequence of characters that reads the same in forward and reverse directions.

What is a double-ended linked list?

A doubly linked list has two-pointers. One pointer points to the next, and the other points to the previous node.

What is the difference between single and doubly linked lists?

A singly linked list has a pointer pointing to the next node in the sequence. There is no concept of a previous pointer, and a node does not know about the previous node. While in a doubly-linked list, each node has two pointers pointing to the previous and the current node, respectively.

What is the difference between an array and a linked list?

An array is a sequential data structure storing elements at contiguous memory locations. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations.

Conclusion

In this article, we discussed whether a doubly linked list is a palindrome or not. A prerequisite of this problem is the knowledge of doubly-linked lists. You can read the details of this data structure here.

Also, there are many other problems based on this data structure. These are: