Abstract Data Types: Lists

What is a list?

A list is a sequential abstract data type where following rules have to be obeyed

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.
addToTail VALUE void Add value on bottom of 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.
emplace POSITION, VALUE void Inserts value at position, shifting existing elements to the right.
get POSITION VALUE Gets value by position.
set POSITION, VALUE void Sets value by position.
removeIndex POSITION void Removes value by position.
removeValue VALUE, COMPARATOR void Removes all values that match value by comparator.
isEmpty   BOOLEAN Checks if list is empty
size   ULONG Gets list size

What are the data structures that implement list?

Most common implementations of lists are:

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!


Share