Iterables (Arrays, List, etc.)

Lists (not arrays) are one of the first thing we learn in data structure and algorithm books besides the preliminary mathematics. We also create lists in our everyday life. We write shopping lists, enumerate things we own, tasks to do, etc...

In mathematics, it is a similar concept to vectors. They can be written as single row matrix

In programming languages, it is usually similar

L: List = [e1, e2, ..., en]

List Operations

I recommend against using index to perform the operations although they are fast, it is bug prone and should only used when necessary.

Iterating the list

Notice that most languages passes iterables as reference, so any changes to it modifies the original ones.

Accessing an item

Some list structures support access by an index, but it is common that the position is unknown. In that case a finding function is need.

Insertion

The insertion varies because there are different conditions based on use case. Usually the fastest way is adding to the beginning of the list.

(element:elementList)

or if we want it based on some condition

insertElement :: a -> (a -> Bool) -> [a] -> [a]
insertElement element _ [] = [element]
insertElement newElement check (element:elementList) =
  if check element then
    (element:newElement:elementList)
  else
    (element:(insertElement newElement check elementList))

Element Update

One way is to reconstruct a new list and replace the element

updateElement :: (a -> a) -> (a -> Bool) -> [a] -> [a]
updateElement _ _ [] = []
updateElement update check (element:elementList) =
  if check element then
    ((update element):elementList)
  else
    (element:(updateElement update check elementList))

In some languages, we need to map function, it is slightly less efficient since maps elements that do not change.

Element Removal

Deletion is by filtering out the element

deleteElement :: (a -> Bool) -> [a] -> [a]
deleteElement _ [] = []
deleteElement check (element:elementList) =
  if check element then
    elementList
  else
    (element:deleteElement check elementList)

Many languages provide filter function that do the same thing.

Sorting

Take a look at algorithm books. In practice, we do not implement these ourselves but use what is provided in standard library of the language.

sort elementList

or if the elements are more complex we need to provide a key for it to sort

sortOn getKey elementList

We also may need to provide a custom condition, in that case use sortBy.