After Arrays another common way to store sequential data is using linked lists. This is a drawing representing a linked list structure. Each of this circle is called a node. It contains a value and a pointer to the next node.

As it has only one pointer pointing to a next value it's called a singly linked list.

Similarly for a doubly linked list each node will have pointers to both the next node and the previous node.

As we don't know where an element is situated for the worst case we have to traverse through the entire list so finding an unknown or a known element is always linear time. Unlike an array it doesn't provide constant time access to a particular index. This means if you want to see element at nth index you need to iterate through 'n' elements.

The benefit of a linked list is that we can add as many element as we want at the beginning of the list in a constant time.

But as we don't know what is the last element, adding element at the end is linear time. This can be solved by adding a pointer at the end of the list at the time of creating the list.

Deleting a node from a linked list is fairly straightforward. Given a node n, we find the previous node prev and set prev.next equal to n.next.

If the list is a doubly linked list we must also update the list accordingly.

Remember if you are using like C, you should always deallocate the memory for the deleted node otherwise you are not deleting the node you are just removing the reference of the node from the list. In Python you don't need to worry about this.

Previously discussed. Refer back to the 2nd video.

It's an interesting problem really. Here you need to run 2 pointers simultaneously one pointer runs faster and other one runs slower. Now imagine that the fast pointer meets the second pointer at some future time, this means there really is some circular part in the list.

It's a classic linked list problem, try this yourself using a three pointer solution, after that watch the video.