Understanding Linked Lists
Linked lists are an ordered collection of objects. So what makes them different from normal lists? Linked lists differ from lists in the way that they store elements in memory. While lists use a contiguous memory block to store references to their data, linked lists store references as part of their own elements.
Performance Comparison: Lists vs Linked Lists
In most programming languages, there are clear differences in the way linked lists and arrays are stored in memory. In Python, however, lists are dynamic arrays. That means that the memory usage of both lists and linked lists is very similar.
Insertion and Deletion of Elements
In Python,
we can insert elements into a list using .insert() or .append().
For removing elements from a list, you can use their counterparts: .remove() and .pop().
The main difference between these methods is that you use .insert() and .remove() to insert or remove elements at a specific position in a list, but you use .append() and .pop() only to insert or remove elements at the end of a list.
Now, something you need to know about Python lists is that inserting or removing elements that are not at the end of the list requires some element shifting in the background, making the operation more complex in terms of time spent. You can read the article mentioned above on how lists are implemented in Python to better understand how the implementation of .insert(), .remove(), .append() and .pop() affects their performance.
Retrieval of Elements
When it comes to element lookup, lists perform much better than linked lists. When you know which element you want to access, lists can perform this operation in O(1) time. Trying to do the same with a linked list would take O(n) because you need to traverse the whole list to find the element.
When searching for a specific element, however, both lists and linked lists perform very similarly, with a time complexity of O(n). In both cases, you need to iterate through the entire list to find the element you’re looking for.
