What is the benefit of using a stack-linked list?

Answer 1

The basic advantage of the Link list is when you have to store the data dynamically and the number of data to be stored is not known in advance.

Example: The word document stores all the data(words) in form on link list. In this scenario you never know how many words will a document contain initally.

Answer 2

There is no actual benefit in implementing a stack with a linked-list. Although a linked-list implementation does have some advantages over an array implementation, those advantages don't apply specifically to a stack. The main advantage of a linked-list is that we can perform insertions and extractions anywhere within the list without having to move any of the existing elements around in memory. However, we never use this feature when implementing a stack. All insertions and extractions occur at the top of the stack, so the movement of existing elements is redundant.

When we consider access times to the top of the stack, we need to know the address where the data resides. In the case of a linked-list, that data will reside at the address pointed to by the head node pointer. That pointer actually refers to a node however the node's data structure typically allocates the data member first (before all other node members), so the data should reside at the same address as the node. Conversely, the top of the stack is at the end of the array (before the unused elements), so we need to use pointer arithmetic to determine the offset address from the start of the array. Thus a list has a small but not insignificant advantage over an array when it comes to accessing the top element. However, that advantage is far outweighed by other factors.

Consider the time it takes to allocate and release memory. Allocating memory is an expensive operation (in terms of performance), but a list allocates memory upon every insertion whereas an array reserves memory in advance and therefore incurs far fewer allocations (by several orders of magnitude). The downside is that an array may occasionally have to re-allocate the array to new memory, which means every used element must be copied to that new location which is a linear time operation. Whilst it is an expensive operation, we can adjust the expansion rate (typically between 160% and 200%) and the initial reserve in order to minimise the need to re-allocate. With an optimal implementation, the cost or re-allocation is more the compensated for by the reduced number of allocations.

An array really comes into its own when releasing memory because we never release an array's elements while it is in use. That is; we never shrink the array, we only expand it. When the array is no longer required, all memory can be released at once. If the elements are pointers, then we must obviously release the memory they point to upon each extraction, however we'd have to do the same every time we extract a node from a list. The difference is that the list nodes themselves must also be released upon every extraction; the release of array elements can be postponed until we're actually done with the array.

So in terms of performance alone, an array will typically perform much better than a list. The occasional blips of a re-allocation mean that the performance isn't quite as consistent as that of a list, but performance is usually about overall speed, not consistency. If you want both speed and consistency (a time-critical application), then you have to sacrifice memory to achieve it.

Memory consumption isn't as easy to compare because although a list does not need to reserve memory in advance, each node consumes more memory than an array element (at least one word of memory extra per node). Thus we can fit more elements into an array than we could in a list of the same size (in bytes). However, if we want to optimise an array's memory consumption to minimise the number of unused elements kept in reserve, then we must sacrifice performance to do so. On today's machines, memory consumption is much less of an issue than it once was, however in a non-time-critical application where consistent performance isn't the overriding factor, we should try to maintain a reasonable balance between performance and memory consumption. In these cases, a linked-list implementation may well offer a reasonable compromise. However, when performance is the overriding factor, an array is easily the better choice.

Answer 3

The usage of linked lists is simply to overcome some of the problems associated with arrays.

Although arrays can be variable length, changing the size of an array in order to accommodate a new element can be a costly operation if there is insufficient free memory to expand into. The entire array must be re-allocated to new memory of sufficient size, which means every element must be moved to that new memory. In order to reduce the performance cost associated with re-allocation, each time we need to re-allocate we must allocate more elements than are actually required, typically in the region of 80-100% more memory. Thus when we re-allocate a large array, we end up consuming a lot of memory that may or may not actually be used. We can recover that memory at minimal cost simply by shrinking the array, however it's best to avoid doing so until such times as we can be sure there will be no more additions to the array. This also means we must keep track of how many unused elements are available at the end of the array, in addition to the total number of elements that are currently allocated to the array.

In addition to the re-allocation issues, arrays are only suitable for insertion at the end of the array. Inserting anywhere else requires that all elements from the insertion point onwards be moved one position forward to create a gap in the sequence for the new element. We have the same problem when extracting elements from anywhere but the end of the array; all elements must be moved one position backwards to remove the gap.

Moving primitive values from one memory address to another has minimal cost (most CPUs are optimised to read contiguous array addresses), however moving complex objects that must be copy constructed can have a serious impact on performance. Move constructors can help reduce the cost of moving a complex object substantially, however move operations are themselves implemented via primitive copy construction, so while they are more efficient, there is still a cost involved.

Linked lists address both these problems by allocating elements non-contiguously. When we need to insert a new element, we simply allocate memory for that new element, there is no need to move elements to fresh memory. However, because elements are allocated non-contiguously, the address of each element cannot be used to determine the order of the sequence. That is, given the address of the first element, there is no way to tell where the next element is allocated; it could be in the next available address or it could be several hundred bytes away. It might even be allocated in a lower address. Thus in order to maintain the order of elements, each element holds a pointer or reference to the address of the next element in the sequence. This is achieved through a node, where the node holds both the element and a pointer to the next node. A doubly-linked list is the same except the node also holds a pointer to the previous node in the sequence. In order to locate any node in the sequence, we simply need to maintain a link to the first node in the sequence, and traverse through the node links. A doubly-linked list also maintains a link to the last node in the sequence, thus we can traverse the list in either direction.

While lists address some of the problems associated with arrays, they aren't a silver-bullet. The main advantage of an array is that we can address any element in the array from its zero-based offset. This makes it possible to achieve constant-time random access to any element in the array. That is, it costs exactly the same to access the last element as it does to access the middle element. But in a list, accessing any element other than the first (or last) takes linear time; the further into the list the element resides, the longer it will take to traverse to it.

The first and last elements of a list are also known as the head and tail nodes. A forward list only maintains a link to the head element and does not maintain a count of its elements. If we need a count, then we must either traverse the entire list or keep track of all insertions and extractions to maintain a count. This is deemed unnecessary in a forward list and helps improve its efficiency.

A forward list is ideally suited to implementing stacks, where all insertions and extractions occur at the head of the list. By encapsulating the list, we can prevent public traversal of the underlying list and also provide a simple mutators to push and pop elements from the head of the stack. We can also provide a simple accessor to determine if the list is empty or not (we don't need to know how many elements there are, so a count is not necessary).

With a simple adaption, we can also modify a stack so that it may be used to implement a queue. This is achieved by maintaining an extra link to the tail node. This does not allow bi-directional traversal, but it does allow efficient insertions (push operations) at the end of the list. Extractions (pop operations) still occur at the head as per a stack.

Doubly-linked lists are ideally suited to applications where an unknown number of insertions or extractions are likely to occur and where the cost of linear traversal is deemed acceptable. Arrays offer the most compact storage of any data container, but the need to re-allocate often means using more memory than might otherwise be consumed by a list. Nevertheless, your choice of container is often a compromise between performance and memory consumption because there is no single container that can address every application and every situation. For instance, a sparse array (an array where the majority of elements hold no actual data), is often best implemented using interwoven linked lists, where every node points left, right, up and down. While each node consumes more memory than an individual array element would, you are saving more memory because nodes that hold no data do not need to be allocated. In an array, empty elements are simply used as placeholders, but in a list you do not need placeholders because nothing needs to point at them. Every node simply points to the four nearest neighbours that actually hold data.

Nodes also have practical applications in trees and graphs. Strictly speaking these container types are not lists, but the concept of one node linking to another is a pervasive one and allows us to create highly-complex data structures that would otherwise be difficult if not impossible to achieve with arrays alone.