The difference between lists and arrays

It seems that a list from lisp can use push to add another element to it, while an array can use vector-push-extend to perform the same action (if you use :adjustable t , except for adding an element to end. Similarly , pop removes the first element in the list, and vector-pop removes the last element from the vector.

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

+4
source share
2 answers

A vector is a tangible thing, but the list you are thinking of is the name for a way to view several unrelated but separate things.

A vector is like a box with an egg - it is a box with some fixed number of slots, each of which may or may not have a thing inside it. On the contrary, what you think of the list is more like taking a few individual shoes and tying their shoelaces together. A โ€œlistโ€ is really an idea of โ€‹โ€‹one cons cell that contains a value, for example, a slot in an egg box and points to another cons cell that also contains a value and points to another cons cell that contains a value and may not indicate nothing else, making it the end of the list. What you consider a list is actually not one, but rather the relationship between several individual cons cells.

You are right that there are some operations that you can perform on both structures, but their time complexity is different. For a list, pushing an element to the front does not actually change anything with respect to the existing list; instead, it means creating a new cons cell to represent the new chapter of the list, and indicating that the cons cell in the existing list is the new tail. This is operation O (1); it doesnโ€™t matter how long the list has been, since putting a new cell in front of it always takes the same amount of time. Similarly, if you remove an item from a list, it does not modify the existing list; it just means shifting your gaze one cell from the current head to see what was the second element as a new chapter.

Unlike a vector, pressing a new element on the front requires first to transfer all existing elements to one space in order to leave empty space at the beginning. Assuming that the vector has enough space to store all existing elements and one more. This shift has a time complexity of O (n), which means that the more elements there are in the vector, the more time it takes to move them and make room for a new element. Similarly, jumping out from the front of a vector requires shifting all existing elements, but the first one down towards the front, so the second was the first, and the third the second, and so on. Again, the time complexity is O (n).

Sometimes you can sometimes play with accounting in the vector, so pushing an element from the front does not require shifting all existing elements; instead, just change the entry of which element is considered first. You can imagine that this has a lot of problems: the indices used to access the elements must be adjusted, the vector capacity is no longer easy to interpret, and the redistribution of space for the vector to accommodate new elements will now need to consider where to leave the newly-made-available empty space after copying existing data to the new storage. The deque structure fixes these problems.

The choice between a list and a vector requires reflection on what you intend to do with it, and how much you know in advance about the nature and size of the content. Each of them sings in different scenarios, despite the apparent coincidence in their purpose.


While I wrote the answer above, the question asked about pushing and popping elements from the front of both the vector and the list. Working at the end of a vector like vector-push and vector-pop do is much more like manipulating a list title than the difference made in my comparison above. Depending on whether the vector capacity can accommodate another element without redistributing, pressing and popping the elements at the end of the vector take a constant (O (1)) time.

+7
source

the list consists of cons cells and nil. To access an item, you need to move it sequentially through the list. Adding and removing an item on the front panel is very cheap. Operations at other positions on the list are more expensive. Lists can have spatial overhead as each item is stored in a cons cell.

the vector is a one-dimensional array of a certain length. If the array is customizable, it can resize it, but perhaps the elements should be copied. Adding an item is expensive when the array needs to be adjusted. Custom arrays have overhead since arrays are usually not adjusted in increments of one. You can access all elements directly through the index.

+12
source

All Articles