Difference between lists and arrays

Question

It seems a list in lisp can use push to add another element to it, while an array can use vector-push-extend to do the same thing (if you use :adjustable t, except add an element at the end. Similarly, pop removes the first item in a list, while vector-pop removes the last item from a vector.

So what is the difference between a list and a vector in lisp?

Answer 1

a list is made of cons cells and nil. One has to move sequential through the list to access an element. Adding and removing an element at the front is very cheap. Operations at other list positions are more costly. Lists may have a space overhead, since each element is stored in a cons cell.

a vector is a one-dimensional array of a certain length. If an array is adjustable, it might change its size, but possibly the elements have to be copied. Adding an element is costly, when the array has to be adjusted. Adjustable arrays have space overhead, since arrays are usually not adjusted by increments of one. One can access all elements directly via an index.

Answer 2

A vector is tangible thing, but the list you're thinking of is a name for a way to view several loosely-connected but separate things.

The vector is like an egg carton—it's a box with some fixed number of slots, each of which may or may not have a thing inside of it. By contrast, what you're thinking of a list is more like taking a few individual shoes and tying their laces together. The "list" is really a view of one cons cell that holds a value—like a slot in the egg carton—and points to another cons cell, which also holds a value and points to another cons cell, which holds a value and possibly points to nothing else, making it the end of the list. What you think of as a list is not really one thing there, but rather it's a relationship between several distinct cons cells.

You are correct that there are some operations you can perform on both structures, but their time complexity is different. For a list, pushing an item onto the front does not actually modify anything about the existing list; instead, it means making a new cons cell to represent the new head of the list, and pointing that cons cell at the existing list as the new tail. That's an O(1) operation; it doesn't matter how long the list was, as putting a new cell in front of it always takes the same amount of time. Similarly, popping an item off the front of the list doesn't change the existing list; it just means shifting your view one cell over from the current head to see what was the second item as the new head.

By contrast, with a vector, pushing a new item onto the front requires first moving all the existing items over by one space to leave an empty space at the beginning—assuming there's enough space in the vector to hold all the existing items and one more. This shifting over has time complexity O(n), meaning that the more items there are in the vector, the longer it takes to shift them over and make room for the new item. Similarly, popping from the front of a vector requires shifting all the existing items but the first one down toward the front, so that what was the second becomes the first, and what was the third becomes the second, and so on. Again, that's of time complexity O(n).

It's sometimes possible to fiddle with the bookkeeping in a vector so that popping an item off the front doesn't require shifting all the existing items over; instead, just change the record of which item counts as the first. You can imagine that doing so has many challenges: indices used to access items need to be adjusted, the vector's capacity is no longer simple to interpret, and reallocating space for the vector to accommodate new items will now need to consider where to leave the newly-available empty space after copying the existing data over to new storage. The "deque" structure addresses these concerns.

Choosing between a list and a vector requires thinking about what you intend to do with it, and how much you know in advance about the nature and size of the content. They each sing in different scenarios, despite the apparent overlap in their purpose.

---

At the time I wrote the answer above, the question was asking about pushing and popping elements from the front of both a vector and a list. Operating on the end of a vector as vector-push and vector-pop do is much more similar to manipulating the head of a list than the distinction made in my comparison above. Depending on whether the vector's capacity can accommodate another element without reallocating, pushing and popping elements at the end of a vector take constant (O(1)) time.