You’re studying to become an excellent Software Engineer, you understand data structures are important in your day-to-day, but where do you start? Most likely, with a Linked List. Linked Lists are a data structure that allows you to manage data you give them, in a dynamic way. If you’re already confused by that, let me rephrase. A Linked List, will add more space if you need it, in order to add another item to the list.
Here’s an example: Imagine you’re asked to program a list of your groceries, you’re allowed to use an Array or Linked List. Your grocery list can have any number of items in it. If you were programming this list, how would you size the Array automatically if you didn’t know the size of the list?
You may be familiar with languages such as C++, and Java that are strictly typed. Meaning, you need to identify the data type, and size among other things to create objects.
Specific to arrays, the programmer must pre-define the maximum size of an array to initialize it. This would mean that trying to dynamically create an array would cost your program time and performance. Why? Because you would have to copy over elements of an old array to a newly sized array you might have doubled because it was too small originally. Copying over elements could take a long time if you had 1000 elements.
How Do I Create Efficient Lists?
Let’s go back to our grocery list. We know that the list can be as big or as little as we’d like it to be. So, this is where a Linked List would be useful. Linked Lists provide the benefit of having a dynamically allocated storage size, that would be suitable for when you — The programmer — have no idea how big a list can get.
The basic operations of a Linked List are:
- Adding to the list
- Removing from the list
- Getting the size of the list
- Search for a value in the list
To start, we need to understand the concept of a node. Think about a chain that has multiple links to it to create an even longer chain. A node is essentially the chain link. Our node will have 2 things: data, and a link to the next node in the chain. This link actually points to a memory address for the next node.
The Linked-Lists Performance
When we create a list like this one, we make it easy for us to continually use it. Given that we don’t have to know how big the list will be. This makes it great to use for a large list of elements. However, there are some issues with using a Linked list to solve your problems.
|* Dynamically add elements to a list.|
* Easier to insert/delete items, because we don’t have to shift.
* Optimizes memory usage.
* Easy to Implement
|* Takes up more memory.|
* Takes longer to search in the list.
* Searching for an element is O(n) time. Compared to an arrays O(1) time.
In the next article, we’ll go over the implementation of a Linked List using python. We’ll explain how adding, removing, searching, and getting the size works. Subscribe to our Newsletter to stay tuned for the next post.