Impression of the week 7 --- Linked Lists

This week we studied linked lists, which is similar to a ''unary'' (base one) Tree where each node has one or no child.  In linked list, each node is directed to the next node in a 'list' of nodes as well as its own value.  And the very first node of linked list is like the root node in a tree, which carries the entire structure, yet it only has direct reference to the next node.

What makes linked list special is its way of inserting new elements to the middle. In normal lists, each element has an index, if we want to insert new item into a certain position of the list, then we will have to move all the elements after that position one index forward to make space for the new item, which will involve lots of unnecessary steps. Where as in linked list, we simply make the two adjacent nodes in that position which used to reference each other, now reference to the new item inserted; and the rest are left untouched.   

However, we do need to loop through the linked list in order to find out the two node which we need to change their linkage according to the index where we desire to insert the item. But intuitively, the worst case of this is in O(n) while the conventional lists insertion is in O(n^2), where n is the length of the list.