Data-structures and Algorithms using Python: Programming Series 101–3

In the past post, we discussed stacks and queues as data structures, their major operations along with time and space complexity. To implement them we used list /array using python. If you don’t have any idea about stacks and queue, here is a link to the articles. Link1 Link2

Arrays are used in scenarios where memory utilization of the resources is continuous. But in cases where memory allocation can’t be continuous or the chance of insertion /removal of elements from the middle of the list is frequent, this might lead to shuffling of the elements or increased time of operation.

To overcome some of the challenges with the use of fixed linear data structure like the inability to efficiently insert or remove elements in the constant time since the memory allocation is continuous, we would today learn a new data structure linked list.

LinkedList:

This data structure allows constant time insertion and deletion from the list and dynamic allocation of the pointers avoiding the need for continuous memory space to store elements and hence avoiding fragmentation.

Source:Internet

The best way to visualize a linked list data structure is a train.

Node: Like the coaches of a train node can store data and has a next pointer which either points nowhere or to the next node.

Linked List: Consider this a train with a head pointer (similar to the engine of a train).

Based on the implementation we can also have a tail pointer but for our case, we will always refer to the linked list using the head pointer.

We will also implement some of the operations /functions for the linked list.

1. print_list(): O(n) time | O(1) space : This function will iteratively print elements of the linked list.
2. append(): O(n) time | O(1) space : This function will append data at the end of the lined list.
3. prepend(): O(1) time | O(1) space: Add the element at the beginning of the linked list.
4. insert_after_node(): O(n) time | O(1) space: insert the element after specified element
5. delete_node(): O(n) time | O(1) space: delete the element from the linked list.
6. delete_node_at_pos(): O(n) time | O(1) space: delete the element from a position.
7. len_iterative(): O(n) time | O(1) space: find the length of the linked list iteratively.
8. len_recursive(): O(n) time | O(n) space: find the length of the linked list recursively.

The use of tail pointer could have helped in having constant time complexity in some cases like the append function, but for the scope of this post, we will focus more on implementation without considering the tail pointer.

There are various pros and cons of using the linked list :

Pros:

1. Dynamic memory allocation: Grows as new elements are added, no need to initialize with a fixed size in contrast to arrays.
2. Efficiently memory usage.
3. Easy to insert and remove elements when compared with continuous size data structures like arrays.

Cons:

1. Requires more space to implement and reside in comparison to arrays.
2. Random access to the elements is not available, unlike arrays that can be accessed using indexes.
3. The memory is allocated at run time rather than compiled time, as a result, the performance may marginally suffer against an array, but that’s insignificant due to computational power these days.

Applications in the real world:

Any computer application that requires sequential access of the data/ work will internally use a linked list data structure due to the dynamic nature of the application. A simple example you can create is a calendar note app where each day note is displayed back in sequential order back to the user.

In the next post, we will discuss certain variations of a linked list that can help us overcome some of the traversal limitations of the linked lists.

I hope you enjoyed this post. Let me know your thoughts if you have any queries or suggestions, would love to hear more from you.

You can follow me for tutorials on AI/machine learning, programming, data analytics, and BI. You can connect with me on LinkedIn.