Linked List Palindrome

Introduction to Linked List Palindrome

A Linked List Palindrome refers to a linked list where the sequence of values in the nodes is the same forwards as it is backwards. This concept is often explored in computer science and data structures. It provides an interesting challenge for algorithm design and can be used to understand and practice various techniques for traversing and analyzing linked lists.

Overview of Linked List Palindrome

A linked list is a data structure in which elements point to the next element in the sequence, forming a chain-like structure. A palindrome is a sequence that reads the same backwards as forwards. Therefore, a linked list palindrome is a linked list that reads the same forwards and backwards. This is usually achieved when the sequence of node values in the linked list is the same when read from the first node to the last, and vice versa. This concept, while simple in theory, can be complex in implementation, and is a common problem presented in computer science and data structures courses.

Code

# Copy rights to venkys.io
# For more information visit https://venkys.io
# Python program to perform Linked List Palindrome
# Stable:Yes
# Inplace:Yes
# Adaptive:No
# Space complexity: O(1)
# Time complexity:O(n)
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def create_list(llist):
    head = None
    temp = None
    for i in llist:
        if not temp:
            temp = Node(i)
            head = temp
        else:
            temp.next = Node(i)
            temp = temp.next
    return head

def check_palindrome(head):
    temp = head
    stack = []

    # Push elements of the first half onto the stack
    while head:
        stack.append(head.data)
        head = head.next

    # Compare the second half with the elements popped from the stack
    while temp:
        if temp.data != stack.pop():
            return False
        temp = temp.next

    return True

if __name__ == "__main__":
    # Take user input for the linked list
    user_input = input("Enter elements of the linked list separated by spaces: ")
    llist = list(map(int, user_input.split()))

    # Create the linked list
    head = create_list(llist)

    # Check if the linked list is a palindrome
    result = check_palindrome(head)

    # Print the result
    if result:
        print("The linked list is a palindrome.")
    else:
        print("The linked list is not a palindrome.")

Step-by-Step Explanation

Node Class Definition: The Node class is defined with an initializer that takes a data parameter and sets the next attribute to None. This class will be used to create nodes for the linked list.
Creating the Linked List: The createlist function takes a list as input and creates a linked list from it. It initializes the head and temp to None. Then, for each element in the input list, it creates a new node and updates temp to the new node.
Checking for Palindrome: The checkpalindrome function takes the head of the linked list as input and checks if the linked list is a palindrome. It initializes an empty stack and a temp variable pointing to the head. Then, it iterates through the linked list, adding each node's data to the stack. Next, it iterates through the linked list again, this time popping elements from the stack and comparing them with the node data. If a node's data does not match the popped stack element, it returns False. If it completes the iteration without finding a mismatch, it returns True.
Main Function: In the main function, a list is defined, and the createlist function is called with this list to create a linked list. The checkpalindrome function is then called with the head of this linked list, and the result is printed. If the linked list is a palindrome, it prints Plaindrome; otherwise, not palindrome.

Test Case 1 :Null Linked List

Input: user_input = "" (Empty string)
Output: "The linked list is a palindrome." (Since it's an empty list, it is considered a palindrome.)

Test Case 2

Input: user_input = "1 2 3 2 1"
Output: "The linked list is a palindrome." (The linked list contains a palindrome sequence.)

Test Case 3

Input: user_input = "1 2 3 4 5"
Output: "The linked list is not a palindrome." (The linked list is not a palindrome as the elements do not read the same backward as forward.)

Code

//Copy rights to venkys.io
//For more information visit https://venkys.io
// Java program to perform Linked List Palindrome
// Stable:Yes
// Inplace:Yes
// Adaptive:No
// Space complexity: O(1)
// Time complexity:O(n)
import java.util.Scanner;
import java.util.Stack;

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

public class Main {

    // Function to create a linked list from an array of values
    static Node createList(int[] values) {
        Node head = null, temp = null;
        for (int value : values) {
            if (temp == null) {
                temp = new Node(value);
                head = temp;
            } else {
                temp.next = new Node(value);
                temp = temp.next;
            }
        }
        return head;
    }

    // Function to check if a linked list is a palindrome
    static boolean checkPalindrome(Node head) {
        Node temp = head;
        Stack<Integer> stack = new Stack<>();

        // Push elements of the first half onto the stack
        while (head != null) {
            stack.push(head.data);
            head = head.next;
        }

        // Compare the second half with the elements popped from the stack
        while (temp != null) {
            if (temp.data != stack.pop()) return false;
            temp = temp.next;
        }

        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Prompt the user to enter values for the linked list
        System.out.print("Enter elements of the linked list separated by spaces: ");
        String userInput = scanner.nextLine();
        String[] valuesString = userInput.split(" ");

        // Convert the input values to integers
        int[] values = new int[valuesString.length];
        for (int i = 0; i < valuesString.length; i++) {
            values[i] = Integer.parseInt(valuesString[i]);
        }

        // Create the linked list
        Node head = createList(values);

        // Check if the linked list is a palindrome
        boolean result = checkPalindrome(head);

        // Print the result
        if (result) {
            System.out.println("The linked list is a palindrome.");
        } else {
            System.out.println("The linked list is not a palindrome.");
        }
    }
}

Step-by-Step Explanation

Node Class Definition: The Node class is defined with an initializer that accepts a data parameter. This class is used to create nodes for the linked list.
Creating the Linked List: The createList function takes an array as input and creates a linked list from it. It initializes head and temp to null. Then, for each element in the input array, it creates a new node and updates temp to the new node.
Checking for Palindrome: The chechPalindrome function takes the head of the linked list as input and checks if the linked list is a palindrome. It initializes an empty stack and a temp variable pointing to the head. Then, it goes through the linked list, adding each node's data to the stack. Next, it goes through the linked list again, this time popping elements from the stack and comparing them with the node data. If a node's data does not match the popped stack element, it returns false. If it completes the iteration without finding a mismatch, it returns true.
Main Function: In the main function, an array is defined, and the createList function is called with this array to create a linked list. The chechPalindrome function is then called with the head of this linked list, and the result is printed. If the linked list is a palindrome, it prints palindrome; otherwise, it prints not palindrome.

Test Case 1 :Null Linked List

Input: user_input = "" (Empty string)
Output: "The linked list is a palindrome." (Since it's an empty list, it is considered a palindrome.)

Test Case 2

Input: user_input = "1 2 3 2 1"
Output: "The linked list is a palindrome." (The linked list contains a palindrome sequence.)

Test Case 3

Input: user_input = "1 2 3 4 5"
Output: "The linked list is not a palindrome." (The linked list is not a palindrome as the elements do not read the same backward as forward.)

Code

/* Copy rights to venkys.io */
/* CPP program to perform Linked List Palindrome */
/* Stable:Yes */
/* Inplace:Yes */
/* Adaptive:No */
/* Space complexity: O(1) */
/* Time complexity:O(n) */
#include <iostream>
using namespace std;

/* Node class for the linked list */
class VSDnode {
public:
    int data;
    VSDnode* next;

    /* Constructor to initialize node with given value */
    VSDnode(int val) {
        data = val;
        next = NULL;
    }
};

/* Function to add a new node at the head of the linked list */
void add_head(VSDnode* &head, int val) {
    VSDnode* n = new VSDnode(val);
    n->next = head;
    head = n;
}

/* Function to add a new node at the tail of the linked list */
void add_tail(VSDnode* &head, int val) {
    VSDnode* n = new VSDnode(val);
    if (head == NULL) {
        head = n;
        return;
    }
    VSDnode* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = n;
}

/* Function to display the linked list */
void display(VSDnode* head) {
    VSDnode* temp = head;
    while (temp != NULL) {
        cout << temp->data << "->";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}

/* Function to reverse the linked list */
VSDnode* reverse(VSDnode* head) {
    VSDnode* prev = NULL;
    VSDnode* curr = head;

    while (curr) {
        VSDnode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

/* Function to check if the linked list is a palindrome */
void is_palindrome(VSDnode* head) {
    VSDnode* new_head = reverse(head);
    VSDnode* temp1 = head;
    VSDnode* temp2 = new_head;

    while (temp1) {
        if (temp1->data != temp2->data) {
            cout << "The linked list is not a palindrome" << endl;
            return;
        }
        temp1 = temp1->next;
        temp2 = temp2->next;
    }
    cout << "The linked list is a palindrome" << endl;
}

int main() {
    cout << "Enter the number of elements in the linked list: ";
    int n;
    cin >> n;

    VSDnode* head = NULL;

    cout << "Enter the elements of the linked list:" << endl;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        add_tail(head, val);
    }

    cout << "Linked List:" << endl;
    display(head);

    /* Check if the linked list is a palindrome */
    is_palindrome(head);

    return 0;
}

Step-by-Step Explanation

Node Class Definition: The VSDnode class is defined with an initializer that accepts a data parameter. This class is used to create nodes for the linked list.
Adding Node to Head: The add_head function takes a head reference and a value as inputs. It creates a new node with the given value and adds it to the head of the linked list.
Adding Node to Tail: The add_tail function takes a head reference and a value as inputs. It creates a new node with the given value and adds it to the tail of the linked list.
Displaying the Linked List: The display function takes the head of the linked list as input and prints the linked list.
Reversing the Linked List: The reverse function takes the head of the linked list as input and returns the head of the reversed linked list.
Checking for Palindrome: The is_palindrome function takes the head of the linked list as input and checks if the linked list is a palindrome. It creates a reversed copy of the linked list and then compares each node in the original and reversed linked lists. If a node's data does not match, it prints "is not a palindrome" and returns. If it completes the iteration without finding a mismatch, it prints "is a palindrome".
Main Function: In the main function, an empty linked list is created, and nodes are added to the head and tail of the linked list using the add_head and add_tail functions. The linked list is displayed after each addition. The is_palindrome function is called to check if the linked list is a palindrome, and the result is printed.

Test Case 1 :Null Linked List

Input: user_input = "" (Empty string)
Output: "The linked list is a palindrome." (Since it's an empty list, it is considered a palindrome.)

Test Case 2

Input: user_input = "1 2 3 2 1"
Output: "The linked list is a palindrome." (The linked list contains a palindrome sequence.)

Test Case 3

Input: user_input = "1 2 3 4 5"
Output: "The linked list is not a palindrome." (The linked list is not a palindrome as the elements do not read the same backward as forward.)

Time And Space Complexity Analysis

For the Python solution, the time complexity of the checkpalindrome function is O(n), where n is the number of nodes in the linked list. This is because the function traverses the entire linked list twice: once to push the nodes' data onto the stack, and a second time to check for a palindrome. The space complexity is also O(n) due to the additional stack used to hold the nodes' data.
For the Java solution, the time complexity of the chechPalindrome function is also O(n) for the same reasons. The space complexity is also O(n) due to the additional stack used to hold the nodes' data.
The C++ solution has a slightly different approach. It creates a reversed copy of the linked list for the palindrome check, so the time complexity remains O(n). However, creating a reversed copy increases the space complexity to O(2n), which simplifies to O(n). Note that this is still considered linear space complexity, but it uses twice as much space as the Python and Java solutions.

Real-World Applications of Linked List Palindrome

Linked List Palindromes, while often seen as an academic or interview question, can have some practical applications in the real world.

Natural Language Processing: Palindromes are not limited to numbers or characters, they can also be sequences of words. For example, in natural language processing, or when building a language-based AI model, recognizing palindromes can be an interesting and challenging task. A linked list could be used to store a sequence of words, and then a palindrome algorithm could be used to check if the sequence is the same forwards and backwards.
Genome Sequences: In bioinformatics, palindromic sequences in DNA or RNA strands, which read the same from 5' to 3' on one strand as they do from 5' to 3' on the complementary strand, play an important role in the formation of various secondary structures in the DNA or RNA molecule. Linked list palindrome algorithms could potentially be adapted to handle this kind of analysis.
Data Transmission: In computer networks, certain data transmission protocols might involve the sending device appending a special sequence to the end of packets that is the reverse of a sequence at the start of the packets. The receiving device could then use a palindrome checking algorithm to verify that the packet has not been corrupted during transmission.
Error Detection and Correction: Palindrome properties are also used in error detection and correction techniques. For example, the Longitudinal Redundancy Check (LRC) is a form of parity check that groups bits into sequences, which should be palindromic. If these sequences are not palindromic, an error is detected.