Since I am not able to sleep, I started thinking about “incorrect” interview questions.

One of the question that popped in my mind was “Implement a linked list in python”.

If the employers is into “web apps”, why are they asking about linked list.

This is “invalid” question, since linked list is a low level construct, suitable for language like “C”. Python is a higher level language and developer need not bother herself with lower level constructs. (To be honest, if you need finer control, you should choose other language.)

I suppose they want to check if you know the “concepts” of linked list, and just for the sake of coding want you to use any language (like python)

In my opinion, if that is the case, you should choose C (or like) language not python.

If you chose python cause you do not know C be upfront about it.

end rant

Note: python lists are internally implemented as “Arrays with over-estimated memory allocation”.

Coming back to linked list operations, typically interviewers ask to show append, prepend, insert in-between (and probably remove from start, end and in between)

Let us look at each:

Append an element at the end

1
2
3
4

>>> lst = [10, 20]
>>> lst.append(21)
>>> lst
[10, 20, 21]

Insert an element somewhere in the middle

1
2
3
4
5

>>> lst
[10, 20, 21]
>>> lst.insert(1, 15)
>>> lst
[10, 15, 20, 21]

Insert an element at the beginning

It is a variation of the above (Note: Python has zero based counting)

1
2
3
4
5

>>> lst
[10, 15, 20, 21]
>>> lst.insert(0, 5)
>>> lst
[5, 10, 15, 20, 21]

Removing an element

remove method does not take an index (like insert), instead it takes the actual element that you wish to remove.

  • If the element is not part of the list, you will get a ValueError exception.
  • If the element appears more than once, only the fist occurrence is removed.
1
2
3
4
5

>>> lst
[5, 10, 15, 20, 21]
>>> lst.remove(15)
>>> lst
[5, 10, 20, 21]

Bonus

There are several additional “built-in” functions for python list, which are not usually “asked” to be done on a linked list (May be count is sometime asked, but that is really about traversing the linked list)

  • count() : Returns number of times an element appears in the list
  • reverse()
  • sort()
  • clear() : Remove all the elements of the list (Sometimes useful.)
  • extend() : Append another list (unlike single item in append) to an existing list. (in actual linked list, this would be just changing one pointer)

Beside these List specific functions, several “built-in” functions also work on list “object” like len, min, max, sum, filter, map, reduce