Check if a doubly-linked list of characters is a palindrome or not

Shreya Deep
Last Updated: May 13, 2022

Introduction

A palindrome is a sequence of characters that reads the same in both 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. Each node in a doubly-linked list has three attributes: a) data of the current node (data) b) pointer to the next node (next) c) pointer to the previous node (prev). You can read more about doubly-linked data structures here.

In this article, we’ll learn to find if a doubly-linked list of characters is a palindrome or not. 

Problem Statement 

Given a doubly-linked list of characters, return true if the doubly-linked list is a palindrome. Otherwise, false.

For example:

INPUT : a->b->b->a

OUTPUT: true

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

INPUT : a->b->c->d

OUTPUT: false

The above doubly-linked list contains characters “abcd.” On forward reading, it’s “abcd.” On backward reading, it’s “dcba.” Therefore, not a palindrome.

Solution Approach

The idea is quite simple. Since we’ve to check for the palindrome, we can start comparing the elements from start and 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 there start<end. If at any point in time the start and end elements are not equal, return false. In the end, return true otherwise. 

The steps are:

  • Input a string.
  • Create a doubly-linked list that has nodes having data as characters and insert the string characters in it at the end. We’ll create do the insert operation in the end in the same ways 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” which will 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, find the pointer to the end node. For finding this, traverse to the end of the doubly-linked list.
    • Once you’ve found out the end pointer, run a while loop until 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 start to the next node of the start node and 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. 

C++ implementation

Below is the C++ implementation of the above idea.

#include<bits/stdc++.h>
using namespace std;
class Node
{
public:
    char data;
    Node* next;  // Pointer to the next node
    Node* prev;  // Pointer to previous node
        
        // Constructor for creating a new node
    Node(char value)
    {
        data = value;
        next = prev = NULL;
    }
};

Node* head=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);
    
    // A temporary pointer that will be used for traversing DLL
    Node* temp = head;
    
    // 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;
        return;
    }
    
    // If DLL is not empty, then traverse till the end of DLL. Make
    // the next pointer of the original last node point to the new
    // last node and the previous of the last node to the original 
    // last node
    
    while(temp->next != NULL)
    {
        temp = temp->next;
    }  // Now temp points to the original last node
    
    // Illustarted by Blue color in the diagram
    temp->next = newNode;

    // Illstrated by orange color in the diagram
    newNode->prev = temp;
}

bool isPalindrome(Node *start)
{
    if (start == NULL) // check if the start itself is null. If yes, the list is //empty, thus return true
      return true;
 
    // Find the end node
    Node *end = start;
    while (end->next != NULL) // Traverse to the end fo the doubly-linked list
        end = end->next;
 
    while (start!= end) // Keep checking if the data at the start pointer of the //linked list is equal to that of the end pointer. 
    {
        if (start->data != end->data) // If the data at start is not equal to data //at end, return false.
            return false;
        // Else move ahead
        start = start->next;
        end = end->prev;
    }
 
    return true;
}

int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++){
        insertAtLast(s[i]);
    }
    //printLinkedList(head);
    Node* start = head;
    if(isPalindrome(start)==true){
        cout<<"true"<<endl;
    }
    else{
        cout<<"false"<<endl;
    }
    return 0;
}

Input

anna

Output

true

Complexities

Time complexity

O(n), where n is the number of elements in the doubly-linked list.

Reason: We’re only traversing the list only once. Therefore, the complexity will be O(n).

Space complexity

O(1) 

Reason: No extra space is taken here other than the variables, start, and end. And they take only constant space.

Frequently asked questions

  1. What is a double-ended linked list?
    Unlike a doubly linked list which has two pointers, one pointing to the next and the other pointing to the previous node, a doubly ended linked list each node has just one pointer which points to the next .” node The difference is that instead of just one "head" node, it contains two pointers of this kind ("first" and "last"), so someone can insert elements to list from both ends of it.
  2. What is the difference between single and doubly linked lists?
    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.
  3. What is the difference between array and linked list?
    An array is a sequential data structure that stores the elements at contiguous memory locations. A linked list, on the other hand, stores elements at different memory locations. Each node is linked to the next node of the sequence using pointers. There is a head pointer that points to the first node of the linked list.
  4. What is a palindrome?
    A palindrome is a sequence of characters that reads the same in both forward and reverse directions. 

Key Takeaways

In this article, we discussed the problem of finding if 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: Count triplets in a sorted doubly linked list whose sum is equal to a given value xFind pair with a given sum in a doubly-linked listReverse A Doubly Linked ListConvert A Given Binary Tree To Doubly Linked List, and Sort a "k" sorted doubly linked list.      

To practice more such problems, Codestudio is a one-stop destination. You can also Attempt our Online Mock Test Series. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.IllustratedIllustrated

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think