Linked-List in Python

Python use List as a dynamic array to store data. List store data at contiguous memory location. Insertion and deletion of elements at the beginning in the list has O(n) complexity. Because these operations require the whole list of elements to move one location forward.

Algorithmic complexity of List:

Find by Index : O(1)
Find by Value : O(n)
Traversal : O(n)
Insert Element : O(n)
Delete Element : O(n)

To deal with this problem, there is an other linear data structure which is a Linked-list. Linked-list store the data at scattered location and use the reference pointer for pointing next element. Each node of a linked-list contain the data and reference to the next node. A head pointer is used to reference the first node. In case of empty linked-list, head pointer reference to null.

If we compare both linked-list has two main benefits over array.
1. You don’t need to pre-allocate the space.
2. Insertion/Deletion is easier

Algorithmic complexity of Linked-List:

Insert Element at Beginning : O(1)
Delete Element at Beginning : O(1)
Insert/Delete Element at End : O(n)
Traversal : O(n)
Access Element by Value : O(n)

Now, lets jump into the coding part and following operation are available in the code.

• Access the nth node
• Search element by value
• Insert at the beginning
• Insert at the end
• Insert at specified index
• Insert after specified index
• Insert after specified value
• Convert list to linked-list
• Get length of linked-list
• Remove element at specified index
• Remove by value

Linked-List has the following drawbacks:
1- Random access is not allowed and you need to traverse sequentially to access the element.
2- Extra memory space is required to store the next_node pointer.
3- Arrays have better cache locality and have high performance.