Essentially, a buffer is an array of object, in our case usually generic pointers so as to obtain uniform reference semantics. But buffers can also contain characters or arbitrary bytes of data.
For one thing, it takes up much less memory space. Assuming a system in which a pointer takes up 4 bytes, a cell for a simply linked list takes up 8 bytes for the two pointer fields, and another 4 or 8 bytes for the invisible header used by malloc. Thus, for each element that needs to be stored, a simply linked list uses 16 bytes, and a doubly linked list uses 24 bytes. A buffer, on the other hand, uses only 4 bytes per element stored, plus possibly some wasted empty space of at most 4 more bytes. On the average, a good buffer implementation should use around 6 bytes per elements stored.
Another great advantage of buffers is evident in systems with a garbage collector. A linked list will have another object (the cell) created for each element stored. That object must be traced, and perhaps copied by the garbage collector. Since no such extra objects are introduced by a buffer, the garbage collector runs much faster on buffers than on lists.
Finally, buffers are usually faster. Traversing linked lists requires more and costlier operations than the corresponding operations on a buffer.
It is costly and impractical to have the buffer be the exact size required to hold the number of elements. Thus, the buffer is most of the time slightly larger, the rest of the space being wasted.
Buffers have a fixed size at any point in time. When the buffer is full, it must be reallocated with a larger size and its elements must be moved. Similarly, when the number of valid elements in the buffer is significantly smaller than its size, the buffer must be reallocated with a smaller size and elements be moved, so as to avoid too much waste.
These disadvantages complicate programming a great deal compared to the equivalent programs with linked lists. However, if the abstract data types are to be reused in many different situations, it is well worth the effort.
However, a block returned from malloc cannot just be expanded or shrunk. Instead one must
One may perhaps do somewhat better if instead of adding a single element at a time, one adds (say) 20 elements or so. But the complexity remains the same, only with a different constant factor. What then can be done?
The solution to the problem is to expand not by a constant amount, but by a constant factor. Here, we are going to use a factor 2. So, if we start with a single element, we will get 2, 4, 8, etc. The reader can easily verify with the same type of reasoning as above, that the cost of copying elements is not proportional to the sum of a geometric series, and that sum is proportional to n. In other words, the cost is proportional to n for a sequence of n push operations, or constant per operation.
But when do we shrink the buffer? In the previous section, we decided to double the size of the buffer whenever it overflows. Thus, for a sequence of push operations, the buffer is at least half full. It may be tempting to shrink the buffer whenever it is less than half full, but that would be an error.
Consider a sequence of alternating push, and pop operations such that the first push overflows the buffer. With a policy of shrinking the buffer whenever it is half full, we will move n elements for every operation in the sequence. Similar sequences can be found for policies of shrinking when the buffer is half full minus some constant number of elements. Again, we have to go geometric. We are going to shrink the buffer whenever it is less than one fourth full. We shall also use a minimum size of the buffer, below which it is not worth the trouble to shrink anymore. We shall use 4 for that limit.