Arrays vs Links: Which Makes for a Better List?

Lists are some of the most common programming problems a coder could encounter throughout an entire computing career. It’s so familiar and occurs naturally in the real world so often. Thus, its usefulness should never be understated.

People intuitively understand what a “list” actually means. For this to be implemented in a computing environment, it must be precisely defined. A list can be defined as a “finite, ordered sequence of data items known as elements”.1

There are only a few things that requires specification in lists. Some of them being: a list has elements, these elements have a certain position associated with them, a list has a notion of a length – which tells how many elements are currently present in the list, and the operations that can be done with the list – creating, inserting elements, removing elements, among others.

There are more ways to implementing lists than one. The most traditional being the array-based lists and the linked lists. The ease or complexity of implementing either of these two does not vary much. Complexity only increases depending on the requirements of the program.

However, like in every other thing where there is a choice, there are advantages and disadvantages to both of them. Here are some points which you might want to consider when choosing between arrays and links for implementation of a list:

One disadvantage of array-based lists is that their size must be predetermined before the array can be allocated.2 More to that, array-based lists cannot grow beyond this predetermined size. This predetermination of size can also be wasteful in resources especially when there are only a few slots in the array which gets filled. On the other hand, linked lists can grow and shrink depending on the data being put into the list. Hence, the list becomes more flexible and there will be less chance in resources being wasted.

However, a different space usage needs to be considered when analyzing the individual elements in the list. In this case, the converse happens compared to the case above since linked lists requires usage of extra space for pointers that give the notion of order to the elements in the list while data elements in an array have a notion of position in themselves. Thus, in cases where it is more likely that the list will be filled, array-based lists have an advantage since it doesn’t have the overhead required by the pointers in linked lists.

Generally, linked lists would be the better implementation for lists whose number of data elements varies widely or is unknown while array-based lists become more efficient when the user knows in advance about how large the list can grow.

Another important consideration for choosing how to implement a list structure is data access. In this case, array-based lists are faster for random access by position since each element has a notion of position in itself and traversal from a current element to a previous element can easily be done given the attached positions of the elements themselves. On the other hand, singly linked lists have a disadvantage because it will usually require marching down the entire list just to get from a current element to a previous element since there is no link from a current to a previous.3

Inserting and removing elements are vital operations to lists. These operations, if not handled properly, can threaten the order in a list no matter what kind of implementation is utilized.

For linked lists, given a pointer to a certain location, insertion and removing elements only takes little work. For insertion, the program need only create a new element, change the link of a previous element, then link it to the next element. Removal only takes breaking the link of a previous element from the element to be removed then relinking it to the element which the element that needs be removed links to. Garbage collection will attend to the removed data. In algorithm analysis, this is said to only take Θ(1) time.

For array-based lists, these operations take a bit much more since they will require the list to shift the remainder of the list up or down within the array in order to accommodate the new data or fill up the space vacated by the element which has been removed. This takes Θ(n) time.

A lot of applications make use of these operation a lot. More so than any other operations. Hence, the time they take to complete usually dominates the program. Which is why, in such cases, linked lists are often preferred to array-based lists.

Of course, it should be noted that there are workarounds to the aforementioned disadvantages. But even those workarounds have their own pros and cons. Hence, the decision as to which implementation to pick should still largely depend on the requirements of the overall program that is being developed.

“Ordered” in this definition means that each element has a position in the list. It does not necessarily mean that the list need be sorted.
2 A work-around to this problem is to make use of dynamic arrays but that requires, like Java’s Vector, but that’s an altogether different consideration.
3 This can, of course, be avoided by using doubly linked lists which has links to both a previous and a next element but that also comes with its own disadvantages. For example, a bigger space overhead.

From Clifford A. Shaffer’s A Practical Introduction to Data Structures and Algorithm Analysis Edition 3.1 (Java Version)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s