Check if a linked list is a palindrome in Scala

Question

The problem: Palindrome: Implement a function to check if a linked list is a palindrome

If it's a palindrome, the list must be the same backwards and forwards

Below is the code I wrote:

  def isPalindrome[A](list:List[A]):Boolean= (list.head, list.last)match{
    case (a,b) if a==b&&list.size>2 => isPalindrome[A](list.tail.dropRight(1))
    case (a,b) if a==b&&list.size<=2 => true
    case (a,b) if a!=b =>false
  }

May I know is there any way to improve it?

Answer 1

What you do is very inefficient. You check if the elements of the list are similar from the outside in, and that too utilising both very unintuitive pattern matching and guard clauses.

Note: You do not need to specify the type parameter A in the recursive call to isPalindrome(), as the compiler can infer that.

Your code, on simple singly linked lists, is O(n²), thanks to the repeated O(n) calls to list.last. The code that I explain and provide below runs in O(n), as reversing a list is O(n) and subsequently checking for equality is also O(n).

What is the definition of a palindrome?

While what you have mentioned is absolutely correct, there's an easier way to think about it.

A sequence is a palindrome whenever it is equal in every way to a sequence that contains the elements of the first sequence in reverse order.

That is, a list is a palindrome if and only if it is equal to its reverse.

I think that as your code already uses enough library functions, why not try this:

def isPalindrome[A](list: List[A]) = list == list.reverse

Simple, succinct, and to the point.

I'm absolutely sure your code is overcomplicated for its intended purpose, and functional programming is not just about pattern matching and recursion, it's about being able to create greater functionality from pre-existing functions.

Answer 2

Finding list.last is an O(n) operation, so this entire function, with recursion, would be O(n²). It should be achievable in O(n).