# Check if a linked list is a palindrome in Scala

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?

• What's a "padorom"? Commented Dec 4, 2016 at 7:14
• @200_success already modified to explain the padorom Commented Dec 4, 2016 at 7:19
• Yes, I know what a palindrome is, but what's a "padorom"? Commented Dec 4, 2016 at 7:20
• Sorry for mistaking the spelling, it should be palindorome :) Commented Dec 4, 2016 at 7:43
• What's a palindorome :) ? Commented Dec 4, 2016 at 8:01

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(n2), 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.

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

• What if one had both head and last references? It's possible and it's most probably done that way (not sure). Then list.last (pardon the alliteration) is an O(1) operation. Commented Dec 4, 2016 at 8:14
• @TamoghnaChowdhury As stated in the documentation: "List has O(1) prepend and head/tail access. Most other operations are O(n) on the number of elements in the list." Commented Dec 4, 2016 at 8:19
• Well, I wasn't sure, so thanks for enlightening me. I thought that Scala would have a more efficient list... Commented Dec 4, 2016 at 8:40