Lists

From

---

Revision as of 23:36, 25 March 2009

Among the simplest data structures is the list. What is a list? A list is an unordered sequence of homogeneous data. The normal operations that are performed on lists are: insert(), remove(), and inList() (membership).

To move from an ADT to a data structure, we need to consider an implementation. First consider an array based implementation. Memory for an array is allocated sequentially. So consider two pointers, one to front of the list and one to the end of the list. Suppose I called them front and back. If I always add an item to the list at the slot that back points to, and remove an item from the slot that front points to, then my list is empty when front and back point to the same slot. To add an item to the list requires that I place the item in the slot where back points to and then increment back. To remove an item from the list means to remove an item from the slot that front points to and then increment front.

Each of these two operations require a certain amount of time, but that time does not depend on the size of the list. These two operations take constant time or O( 1 ).

Since an array implementation requires that I declare the size ahead of time, how would I know when my list is full? If the size of the list is N and the array takes slots 0 … N – 1, then when back is equal to N, the list is full. But notice what happens when I add some items and delete some items. After a while, my list might become full, because back is equal to N, but it is possible that most of the array is actually empty. What shall I do? I could periodically copy my list to a new list that always starts from the first empty position. How much time does this take? Copying depends on the size of the list, so it is O( N ). Another question is when should I perform the copy? Certainly every time I do an add is too often, because then adding is no longer a constant operation. Perhaps I can use a count operation that specifies a copy operation when there are a set number of empty spaces in the front of the array?

Circular Lists

Suppose I allocate 5 slots for a list and they are numbered 0 … 4. Now suppose I set up the following operations. A new list has front set to 0 and back set to 4. Adding an item to a list means to set back = (back + 1) mod 5 then add the item at that slot. Removing an item means to remove the item from the slot pointed to by front and then to set front = (front + 1) mod 5. When is a list full? When front == (back + 2 ) mod 5. When is a list empty? When front == (back + 1) mod 5. Note that this method wastes a slot, but for a large list, this is of little consequence.

What if I now want to be able to insert an item into the middle of my list? This will be O(N) because I need to move half the list to make room in the middle for the added item. A solution to this problem is to use linked representation.