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)

Three Steps: Beating the Problem

Writing computer programs can be as easy as 1-2-3 or as difficult as seeing the usefulness of understanding Einstein’s theory of relativity.

But any difficult problem always becomes easier when broken down into pieces. That way, you get to be able to see them as smaller problems and coding becomes easier from there.

General computer processes can usually be tackled with three steps: understand, specify and design. These three steps make higher programs become less.


First, it is important to understand the problem you are faced with. Your initial understanding need not be clear. However vague it may be doesn’t matter. The more important part is refining your understanding as you go along the entire coding process. Taking an inventory of the concepts in your problem helps a lot.

For example, if you are trying to build a chess program, you’ll want to begin with the notion of a “piece”, which could be the pawn, the rook, the knight, the bishop, the queen, or the king. Furthermore, note that each of these pieces have properties of “position” and “moves”.


Second, lay down how this problem can be converted to code.

In one part of the chess program, you can tackle player moves. This function can take a certain piece, its position on the board, and the new position to which it is being moved. The process of this program verifies whether the piece can be moved into the new position and outputs the result of the verification process – that is, moving the piece to the new position.

There are a few things to note when deciding a valid move:

  1. The type of the piece being moved. In chess, different pieces can only move in a certain manner. The rook can only move straight. The knight can only move in an L. The bishop can only move diagonally. There are limitations as to how a chess piece can move.
  2. The state of the new position. It can be so that the player is simply moving to a vacant square or the player can be trying to eliminate an opponent’s piece.
  3. The notion of promotion. Pawns that reach the other end can get promoted. Hence, it is important to note whether a certain piece have been moved to the opposite edge and whether promotion can happen.

These are some of the things you’ll want to consider when checking the validity of a move.

A similar specification process will work for other parts of the chess program.

You don’t have to think about it so hard in the initial phase. Things get improved as you go along your coding.


Finally, you design working code.

Now that you know about the types of data you are dealing with and the functions associated with them, you can move on to writing your code.

Design of computer programs can take entire university level courses if the intention is to delve in.

Anyway, this step is where you initially write code. In the process, you get to be able to refine your understanding of the problem. Also, it might turn out that your specifications have been insufficient. So, you get back to that step and improve your specifications.

Basically, writing computer programs, and problem-solving in general, is a continuous process of refining and improving. Even Google’s search engine continues to be refined to this day despite the fact that, in all the sense of the word, it is already a complete program. Besides that, millions are already using it. Quite possibly even billions.

Therefore, this three-step process is more of an iterative process which you loop again and again while continuously improving your solution.