In this lesson, we are going to look at two different ways of creating an ordered list data structure to hold the following list [2 4 6 7]. First, we will create a list using an array of memory cells. Next, we will create the the same list using pointers. Finally, we will compare these two approaches to see the advantages and disadvantages.
One approach to creating a list is simply to reserve a block of adjacent memory cells large enough to hold the entire list. Such a block of memory is called an array. Of course, since we will want to add items to our list, we need to reserve more than just four memory cells. For now, we will make our array large enough to hold six numbers. The animation below shows a graphical representation of our array in memory with the list numbers. Follow the directions in the animation to learn how the list operations AddListItem and RemoveListItem work.
In the animation, you saw that there were two disadvantages to using an array to implement an ordered list. First, you saw that the elements in the list must be kept in sequence, that is, there must not be gaps in the list. If gaps are allowed, the computer will not be able to determine which items are part of the list and which items are not. For this reason, the ordered list structures that are implemented with arrays are known as sequential lists.
The second disadvantage that you saw was that arrays have a fixed size and therefore limit the number of items the list can contain. Of course we could try to increase the size of the array, but it may not always be the case that the adjacent memory cells in the computer are available. They could be in use by some other program. However, it is quite likely that the computer does have available memory at some other non-adjacent location. To take advantage of this memory, we need to design our list so that the list items do not have to be adjacent.
A second approach to creating a list is to link groups of memory cells together using pointers. Each group of memory cells is called a node. With this implementation every node contains a data item and a pointer to the next item in the list. You can picture this structure as a chain of nodes linked together by pointers. As long as we know where the chain begins, we can follow the links to reach any item in the list. Often this structure is called a linked list.
Notice that the last memory cell in our chain contains a symbol called "Null". This symbol is a special value that tells us we have reached the end of our list. You can think of this symbol as a pointer that points to nothing. Since we are using pointers to implement our list, the list operations AddListItem and RemoveListItem will work differently than they did for sequential lists. The animation below shows how these operations work and how they provide a solution for the two problems we had with arrays.
By implementing our list with pointers, we are able to avoid the two disadvantages we discovered with using sequential lists. However, this does not mean that linked lists are the perfect solution. Whenever we use indirection in building a data structure, it becomes much harder to find mistakes. For example, it is very easy to assign the wrong address to a pointer and "short circuit" our list. In general, sequential lists are simpler than linked lists but they are also more limited. Linked lists give us a great amount of flexibility but this comes at the cost of increased complexity.