Linked List and how dynamic collection of data is handled in modern languages

During programming, we often need to use collection of data. Collection of data can be handled in an array or in a linked list. Lets see the advantages and disadvantages for both.

Arrays

Arrays are probably the most commonly used data structures. They are fixed length data structure. That means when you create an array, the language compiler will allocate a fixed length of memory for you to use. You can add elements till that length. If you need to add more, you will have to create a new array. One advantage of an array is that we can access any element in the array if we know the index. This is one of the reason why they are the most common data structure. So in short

• Arrays has limited size allocated to them
• If we know the index, it is very easy to access the element of the array.

Linked List

Often times we don't really know the size of the collection that we use. We might need to add elements to the collection to satisfy our use case. This is where Linked List come into use. Linked List is a collection of data where each data is linked to each other. Depending on the type of linked list each of your data might know the details of its next value in the collection (singly linked list) or it might know both the next and previous value in the collection (doubly linked list). They don't need to have a fixed length and it is possible to add new data to the a linked list. So to summarize

• Linked list is a collection of data where each data knows about its adjacent data
• The length of a linked list is dynamic. We can easily add data to a linked list.

Singly Linked List

Doubly Linked List

Solutions offered by modern languages

As I said, arrays are probably the most used data structures. On the others hand linked list are almost never used. Even though we find that in many scenarios we don't really know the length of the collection of data. Still we use arrays most of the time. This is possible because of two reasons

• Most languages offer simple solution to add data by abstracting the creation of new array and providing simple methods to add data

For example C# provides List collection for handling collection of data whose length is not fixed.

Internally when we create a new List object, the compiler assign creates and array with double the size of the given length. It adds data to the same array when we use the List.Add method. When the length exceeds the initial allocated memory, the compiler then creates a new array with increased size and allocates all the data to this array.

// The c# compiler creates an array of length 2 * given length
var a = new List<int> {1,2,3,4};  // creates an array of length 8
a.Add(5);
a.Add(6);
a.Add(7);
a.Add(8); // all the allocated memory of array is filled
a.Add(9); // this now creates a new array with the increased length

If there is no way to figure out the initial length, then the compiler creates an array of length 4.

var a = new List<int>(); //this creates an array of length 4

This is the reason, we are not allowed to access the length property for a c# List object. Instead we are given a Count property which gives us the count of data stored in the array instead of the length of the array.

• Most of the languages are now garbage collected, so the unused array is removed with very little loss of memory.

We might end up having to create large number of new arrays by using the inbuilt language methods. It would not be efficient and might take huge space if those memories locations are not freed. Fortunately, most of the modern languages comes with garbage collector. The garbage collectors takes up the responsibility of freeing up the unused memory. So we don't have to worry about clearing the memory manually, which might become a tedious process.

Conclusion

While creating a new array for each element added might take a bit more processing power, its usually always compensated by the ease which arrays allows us to access its elements. This makes arrays the most popular data structures and almost always more efficient to use then the linked list. While linked list might not see much use, understanding the working of linked list will help us understand other data structures more easily.