Check if a Doubly-Linked List of Characters is a Palindrome or Not

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;
}

You can also try this code with Online C++ Compiler

Run Code

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.")

You can also try this code with Online Python Compiler

Run Code

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.

You can also read about Palindrome Number in Python here.

Frequently Asked Questions

What is a linked List?

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: 

• Reverse A String In C
• Count triplets in a sorted doubly linked list whose sum is equal to a given value x
• Find pair with a given sum in a doubly-linked list
• Reverse A Doubly Linked List
• Convert A Given Binary Tree To Doubly Linked List
• Sort a "k" sorted doubly linked list

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!