[Data Structure] Array–Based Lists (ADT)

Array–Based List

 

An array-based list is a list ADT implemented using an array. An array-based list supports the common list ADT operations, such as append, prepend, insert after, remove, and search.

In many programming languages, arrays have a fixed size. An array-based list implementation will dynamically allocate the array as needed as the number of elements changes. Initially, the array-based list implementation allocates a fixed size array and uses a length variable to keep track of how many array elements are in use. The list starts with a default allocation size, greater than or equal to 1. A default size of 1 to 10 is common.

 

 

Append Operation

Given a new element, the append operation for an array-based list of length X inserts the new element at the end of the list, or at index X.

Before Appending

After Appending

 

 

Resize Operation

As mentioned above, an array has a fixed size, so we need to dynamically resize it if an item is added when the allocation size equals the length. 

Obviously, new array is allocated with a length greater than the existing array. One common approach is to use twice the length of the eisting one. 

The existing array elements are then copied to the new array, which becomes the list's new storage array. 

 

 

Prepend and Inset After Opeartion

The Prepend operation for an array-based list inserts a new item at the start of the list.

First, if the allocation size equals the list length, the array is resized. Then all existing array elements are moved up by 1 position, and the new item is inserted at the list start, or index 0. Because all existing array elements must be moved up by 1, the prepend operation has a runtime complexity of O(N).

 

The InsertAfter operation for an array-based list inserts a new item after a specified index.
(Ex: If the contents of numbersList is: 5, 8, 2, ArrayListInsertAfter(numbersList, 1, 7) produces: 5, 8, 7, 2.)

First, if the allocation size equals the list length, the array is resized. Next, all elements in the array residing after the specified index are moved up by 1 position. Then, the new item is inserted at index (specified index + 1) in the list's array. The InsertAfter operation has a best case runtime complexity of O(1) and a worst case runtime complexity of O(N).

 

 

Search and Removal Operation

Given a key, the search operation returns the index for the first element whose data matches that key, or -1 if not found.

Given the index of an item in an array-based list, the remove-at operation removes the item at that index. When removing an item at index X, each item after index X is moved down by 1 position.

Both the search and remove operations have a worst case runtime complexity of O(N).

 

The best case for searching would be when the matching element is at index = 0, and the worst case is when there is no matching element. 

The best case for removing is when removing element is at the last index, and the worst case is when it's at the first index. 

Notice neither of them will resize the given array. 

 

 

---

Python Implementation

 

We start from defining the ArrayList Class:

class ArrayList:
    def __init__(self, initial_allocation_size=10):
        self.allocation_size = initial_allocation_size
        self.length = 0
        self.array = [None] * initial_allocation_size

 

Then, append and resize methods can be implemented like following code:

def append(self, new_item):
    # resize() when the array is full
    if self.allocation_size == self.length:
        self.resize(self.length * 2)

    # insert new item at index = self.length
    self.array[self.length] = new_item

    # increment the array's length by 1
    self.length += 1

def resize(self, new_size):
    # Create a new array
    new_array = [None] * new_size

    # Copy items into new array
    for i in range(self.length):
        new_array[i] = self.array[i]

    # Assign new array to self.array
    self.array = new_array

    # Update the allocation size
    self.allocation_size = new_size

 

prepend and insert_after methods are easy to understand once you understand the shifting. 

Prepend method shifts every single elements in the array–based list, starting from the right end, reversely traversing through the list. 

insert_after method shifts starting from the right end, reversely traversing up to [inserting_index + 2].

(So the final shifting is: self.array[index + 2] = self.array[index + 1]) 

def prepend(self, new_item):
    # resize() when the array is full
    if self.allocation_size == self.length:
        self.resize(self.length * 2)

    # Shift all array items to the right, starting from the tail to head
    for i in range(self.length, 0, -1):
        self.array[i] = self.array[i - 1]

    # Prepend
    self.array[0] = new_item

    # Update length
    self.length += 1

def insert_after(self, index, new_item):
    # resize() when the array is full
    if self.allocation_size == self.length:
        self.resize(self.length * 2)

    # Shift all array items to the right, starting from the tail until the inserting index + 1
    for i in range(self.length, index + 1, -1):
        self.array[i] = self.array[i - 1]

    # Insert new item
    self.array[index + 1] = new_item

    # Update
    self.length += 1

 

 

Lastly, search and remove_at methods are very simple. 

def search(self, item):
    # Iterate through the entire array
    for i in range(self.length):
        if self.array[i] == item:
            return i

    # Not found
    return -1

def remove_at(self, index):
    if index >= 0 and self.length > index:  # If valid
        # Shift all elements at the right
        for i in range(index, self.length - 1):
            self.array[i] = self.array[i + 1]

    # Update
    self.length -= 1