Vectors vs. Lists in Clojure

In Clojure, two fundamental data structures, lists, and vectors, present developers with distinct capabilities and applications. While superficially similar, they serve unique purposes within Clojure's functional paradigm. We'll discuss the disparities between lists and vectors, providing clarity on their respective strengths and best practices for implementation.

Lists: Agile and immutable

Lists are implemented as linked lists, where each element points to the next. While lists sacrifice random access for immutability and efficiency in certain operations, they excel in scenarios where sequential processing or structural sharing is crucial.

Syntax

Lists are enclosed within parenthesis. For example:

Staple methods

• Access: Accessing an element by index requires traversing the list from the beginning until the desired index is reached. The time complexity of this method is $O(n)$, where $n$ is the number of elements in the list.

• Insertion: Vectors are immutable by default, so modifying a vector involves creating a new vector with the desired changes.

  • Append: We traverse the list from the beginning, till the last node. Next, we insert the new element after the last node. The time complexity of this method is $O(n)$, where $n$ is the number of elements in the list.

  • Prepend: We create a new node and point it to the current head. The time complexity of this method is $O(1)$.

  • Insert at a specified index: We traverse the list to the specified index before performing the insertion. The time complexity of this method is $O(i)$, where $i$ is the specified index.

• Deletion:

  • Delete from the end: We traverse the list to find the second-to-last node. Next, we update the next pointer of this node to NULL. The time complexity of this method is $O(n)$.

  • Delete from the start: We update the head pointer to point to the next node. The time complexoty of this method is $O(1)$.

  • Delete at a specified index: Similar to insertion at a specified index, we need to traverse the list to the specified index before performing the deletion. The time complexity of this method is $O(i)$.

Code example

Here's an example of using the methods described above:

Explanation

• Lines 2–4: The access-element function takes two arguments, lst (a list) and index (an integer). It prints the index and the element at that index in the list lst using the nth function.

• Lines 7–9: The insert-at-end function takes a list lst and an element elem to be inserted at the end of the list. It prints the list after inserting elem at the end using the concat function to combine the original list and a list containing the new element.

• Lines 12–14: The insert-at-head function takes a list lst and an element elem to be inserted at the beginning of the list. It prints the list after inserting elem at the head using the cons function.

• Lines 17–22: The insert-at-index function takes a list lst, an index index, and an element elem to be inserted at the specified index. It prints the list after inserting elem at the specified index by splitting the original list into two parts (before and after) at the index and then concatenating them with the new element inserted in between.

• Lines 25–27: The delete-from-end function takes a list lst and prints the list after deleting the last element using the butlast function.

• Lines 30–32: The delete-at-head function takes a list lst and prints the list after deleting the first element using the rest function.

• Lines 35–39: The delete-at-index function takes a list lst and an index index and prints the list after deleting the element at the specified index. It achieves this by splitting the list into two parts (before and after) at the specified index and then concatenating them together, effectively skipping the element at the specified index.

Vectors: Dynamic and indexed containers

Vectors, characterized by their dynamic and indexed nature, excel in scenarios demanding efficient random access and mutable operations. They are implemented as arrays, which allows for efficient random access and fast append/prepend operations. Vectors maintain order and are indexed by integer keys.

Syntax

Vectors are enclosed within square brackets. For example:

Staple methods

• Access: Accessing elements by index takes $O(1)$ time, as vectors use direct addressing.

• Insertion: Vectors are immutable by default, so modifying a vector involves creating a new vector with the desired changes.

  • Append: Appending elements to a vector (using the conj function) typically has an amortized constant time complexity of $O(1)$. This means that, on average, appending an element to the end of a vector is a very fast operation and does not depend on the size of the vector.

  • Prepend: We create a new vector with the elements in the desired order. We typically reverse the elements, prepend them one by one, and then reverse the resulting vector to restore the original order. The time complexity of this approach approach is $O(n)$, where $n$ is the size of the original vector.

  • Insert at a specified index: We create a new vector with the desired element inserted at the specified index. The time complexity of this method is $O(n - i)$, where $i$ is the position at which the element is being inserted.

• Deletion:

  • Delete from the start: We create a new vector that excludes the first element. The overall time complexity of this approach is $O(n)$.

  • Delete from the end: We create a new vector that excludes the last element. The overall time complexity of this approach is $O(n)$.

  • Delete at a specified index: We create a new vector that excludes the element at the specified index. The overall time complexity of this approach is $O(i)$.

Code example

Here's an example of using the methods described above:

Explanation

• Lines 2–3: The access-element function takes a vector v and an index index as arguments. It prints the index and the element at that index in the vector using the nth function.

• Lines 6–7: This function accepts a vector v and an element elem. It prints the vector after inserting the element at the end using the conj function.

• Lines 10–12: The insert-at-head function takes a vector v and an element elem. It prints the vector after inserting the element at the head by first reversing the vector, then using conj to add the element, and finally converting it back into a vector.

• Lines 15–17: The insert-at-index function accepts a vector v, an index index, and an element elem. It prints the vector after inserting the element at the specified index by splitting the vector into prefix and suffix using subvec, inserting the element in between, and then converting it back into a vector.

• Lines 20–22: The delete-from-end function takes a vector v as an argument. It prints the vector after deleting the last element using subvec to exclude the last element.

• Lines 25–27: The delete-at-head function accepts a vector v as input. It prints the vector after deleting the first element using subvec to exclude the first element.

• Lines 30–32: The delete-at-index function takes a vector v and an index index. It prints the vector after deleting the element at the specified index by concatenating the prefix and suffix of the vector without the element at the index and converting it back into a vector.

Use cases

Vectors are prefered in the following cases:

1. Accessing elements by index: If your code frequently accesses elements by index, vectors would be preferred due to their efficient indexed access. For example, if you're implementing a matrix or a grid where you need to access elements by row and column indices, vectors would be a better choice.

2. Efficient updates: If your code requires frequent updates to individual elements, vectors are more efficient due to their mutability at specific indices.

Lists are prefered in the following cases:

1. Functional transformations: Lists are preferred when you're applying functional transformations like map, filter, or reduce to sequences. Lists' persistent nature allows for efficient creation of modified versions of the original list without mutating it.

2. Immutable collections: Lists are immutable and persistent, making them suitable for functional programming paradigms where immutability is emphasized. They're particularly useful when you want to avoid unexpected side effects that can arise from mutable data structures.

3. Sequential processing: If your code primarily involves sequential processing or traversal of elements from start to end, lists are preferable due to their efficient sequential access.

Conclusion

Vectors, with their dynamic and mutable attributes, are well-suited for scenarios necessitating rapid access and mutable operations. Conversely, lists, with their immutable and sequential characteristics, thrive in scenarios demanding structural sharing and immutable data manipulation. By understanding their nuances, developers can use these data structures to optimize data manipulation tasks effectively.