Static List Implementations
A static list implementation uses a fixed-size array to store elements, meaning the maximum capacity of the list is determined at the time of creation and cannot be changed dynamically.
- Static lists are implemented using arrays, which are contiguous blocks of memory.
- This makes accessing elements by index very fast.
Static lists are ideal for scenarios where the number of elements is known in advance and does not change frequently.
- Fixed-size buffers in networking.
- Predefined datasets in embedded systems.
- Lookup tables in games or simulations.
Key Methods in Static Lists
- listEmpty: Checks if the list is empty.
- listFull: Checks if the list is full.
- addHead: Adds an element to the beginning of the list.
- addTail: Adds an element to the end of the list.
- insert: Inserts an element at a specified position.
- delete: Removes an element from a specified position.
Let's examine each method in detail.
For examples, we will use IB pseudocode with variables such as:
- MAX - maximum number of elements
- SIZE - how many elements are in the list currently
- LIST - array of length MAX
Checking List Status
listEmpty: This method checks if the list is empty by verifying that its size is zero.
method listEmpty()
return SIZE = 0
end methodlistFull: This method checks if the list is full by comparing the list's size to its maximum capacity.
method listFull
return SIZE = MAX
end methodAdding Elements
addHead
- To add an element to the head of a static list, you need to shift all existing elements one position to the right to make space at the beginning.
- This operation has a time complexity of O(n), where n is the number of elements in the list.
method addHead(VALUE)
if listFull() then
output "List is full"
return
end if
// Shift all elements to the right
I = SIZE - 2
loop while I >= 0
ARRAY[I + 1] = ARRAY[i]
I = I - 1
end loop
LIST[0] = VALUE
SIZE = SIZE + 1
method end
addTail
- Adding an element to the tail of a static list is straightforward.
- You simply place the new element at the next available position.
method addTail(VALUE)
if listFull() then
output "List is full"
return
end if
LIST[SIZE] = VALUE
SIZE = SIZE + 1
end procedure
insert: Inserting an element at a specific position requires shifting all elements from that position onwards one step to the right.
method insert(INDEX, VALUE) // assume INDEX is valid (<0 and >= size)
if listFull() then
output "List is full"
return
end if
// shift elements to the right from INDEX
I = SIZE - 2
loop while I >= INDEX
ARRAY[i + 1] = ARRAY[i]
end loop
LIST[INDEX] = VALUE
SIZE = SIZE + 1
end method
Deleting Elements
delete: Removing an element from a static list involves shifting all elements after the deleted element one position to the left.
method delete(INDEX) // assume index is valid
if listEmpty() then
output "List is empty"
return
end if
// shift elements to the left from INDEX + 1
I = INDEX
loop while I < SIZE - 1
LIST[I] = LIST[I+1]
I = I + 1
end loop
SIZE = SIZE - 1
end method
- What is the main difference between a static list and a dynamic list?
- Try implementing static lists in Java or Python.
