Google’s Udacity course on data structure and algorithms
I recently found this free course on Udacity and I think it’s a really beginner friendly way to be introduced algorithms. Everything is implemented in python and it’s mainly to practice the basic concepts. Today we will talk about linkedlist.
Linkedlist is different from a python list, in the sense that you have to traverse the entire list to get to the element you want. This is more inefficient than python’s list using indexed for look up, which is O(1). However, the major advantage of linkedlist is the insertion and deletion capabilities. With a traditional python list, any insertion or deletion requires a frame shift of all elements after the affected index.
This is where linkedlist come in. Since it uses pointers, it’s very easy to insert and remove just by redirecting the pointers. It would be extremely useful if the data is large and there needs much more writes than reads. I would like to emphasize that Element1.next is a pointer to the memory location where Element2.value is stored. So essentially they are the same thing.
For this simple linkedlist, you just need 4 methods, append,get_position,insert and delete. You can refer to the code below with comments for better understanding.
Happy coding!
