Abstract Data Types: Lists
Home >
List Abstract Data Type
What is a list?
A list is a sequential abstract data type where following rules have to be obeyed
- all values are stored sequentially from head to tail without empty gaps
- any value is accessible by its position in sequence
- a single value can exist at multiple positions
- a single position can only hold a single value
How values are added to list tail:
What are the operations a list requires?
Although, as an abstract data type, list comes with no implementation, it requires from data structures that implement it to provide support
for a minimal set of operations:
| Operation |
Arguments |
Returns |
Description |
| addToHead |
VALUE |
void |
Add value on top of list.
This means inserting another entry at position 0, shifting all existing entries one step (position) right |
| addToTail |
VALUE |
void |
Add value on bottom of list.
This means inserting another entry after last existing entry in list |
| clear |
|
void |
Clears list of all values. |
| containsIndex |
POSITION |
BOOLEAN |
Checks if position exists in list. |
| containsValue |
VALUE, COMPARATOR |
BOOLEAN |
Checks if value exists in list by comparator.
This potentially requires iterating the whole list and applying comparator to see if value matches. AVOID unless list is small! |
| emplace |
POSITION, VALUE |
void |
Inserts value at position
This means inserting an entry at given position, shifting remaining entries one step (position) right |
| get |
POSITION |
VALUE |
Gets value by position. |
| set |
POSITION, VALUE |
void |
Sets value by position. |
| removeIndex |
POSITION |
void |
Removes value by position.
This means removing entry at given position, shifting remaining entries one step (position) left |
| removeValue |
VALUE, COMPARATOR |
void |
Removes all values that match value by comparator.
This potentially requires iterating the whole list, applying comparator to see if value matches and, every time it matches, shifting remaining entries one step (position) left. AVOID unless list is very small! |
| isEmpty |
|
BOOLEAN |
Checks if list is empty |
| size |
|
ULONG |
Gets number of elements in list |
Where:
- VALUE: value of a list entry
- POSITION: position in list entry should be found at
- COMPARATOR: function with signature compare(source, destination): BOOLEAN able to compare values in list
What are the data structures that implement list?
Most common implementations of lists are:
- Dynamic Array
- Strengths:
- By far the fastest in accessing element by random position: because it only involves navigating through the C array it wraps.
- By far the fastest in adding element to bottom of list: because it only requires incrementing count and adding value to next position in already preallocated (unless an expand is pending) block
- By far the fastest in removing element from bottom of list: because it only requires decrementing count value.
- Smallest in memory consumption: because nothing but elements themselves plus remaining empty slots in preallocated block are stored
- Weaknesses:
- By far the slowest in deleting element at random position: because it involves padding all entries after position one step left.
- By far the slowest in adding element at random position: because it involves padding all entries after position one step right.
- Growth is somewhat costly because if realloc cannot expand block, it creates a new one and moves entries to that location. When size of list is already known, it's MUCH faster to use a reserved size.
- Because of the mechanism of growth, it allocates more space than it actually uses. When size of list is already known, it's MUCH more optimal to use a reserved size so no space is wasted.
- Linked List
- Strengths:
- fast in deleting element on top position: because it only requires swapping head element with the next.
- fast in adding element on top of list: because it only involves switching head position with the new one and next position with the old head.
- fast in adding element on bottom of list: if it keeps track of list tail.
- fast in accessing/inserting/deleting element on next position: if it keeps track of last element accessed/inserted/deleted.
- Weaknesses:
What are the data structures that implement list
- relatively slow in traversal: because it needs to move from random memory position to the other.
- slow at deleting/accessing/inserting element on random position: because it needs to traverse all entries in list until position if last element accessed is none or grater than position or from last position accessed to current position if latter is smaller.
- slow at deleting element on bottom: because it needs to traverse the whole list.
- higher in memory consumption: because every element needs to store a pointer to the next
- Doubly Linked List
- Strengths:
- fast in deleting element on top position: because it only requires swapping head element with the next.
- fast in adding element on top of list: because it only involves switching head position with the new one and next position with the old head.
- fast in deleting element on bottom position: because it only requires swapping tail element with the previous.
- fast in adding element on bottom of list: because it keeps track of list tail.
- fast in accessing/inserting/deleting element on next position: if it keeps track of last element accessed/inserted/deleted.
- fast in accessing/inserting/deleting element on previous position: if it keeps track of last element accessed/inserted/deleted.
- Weaknesses:
- relatively slow in traversal: because it needs to move from random memory position to the other.
- slow at deleting/accessing/inserting element on random position: because it needs to traverse all entries from previous position to current position or from tail/head to current position depending on .
- slow at deleting element on bottom: because it needs to traverse the whole list.
- highest in memory consumption: because every element needs to store a pointer to the an another to previous elements
This time complexity table using Big O Notation
shows advantages and disadvantages of each data structure chosen for each list operation:
| Method |
Dynamic Array |
Linked List |
Doubly Linked List |
| addToHead |
O(N*2) |
O(1) |
O(1) |
| addToTail |
O(1) |
O(1) |
O(1) |
| clear |
O(2) |
O(N) |
O(N) |
| containsIndex |
O(1) |
O(1) |
O(1) |
| containsValue |
O(N) |
O(N) |
O(N) |
| emplace |
O(N*2) |
O(N) |
O(N) |
| get |
O(1) |
O(N) |
O(N) |
| set |
O(1) |
O(N) |
O(N) |
| removeIndex |
O(N*2) |
O(N) |
O(N) |
| removeValue |
O(N*2) |
O(N) |
O(N) |
| isEmpty |
O(1) |
O(1) |
O(1) |
| size |
O(1) |
O(1) |
O(1) |
Conclusion: whenever random position deletes/inserts are not needed, for memory & speed efficiency reasons, Dynamic Array should be solution of choice!
