470 Programming and Data Structures
As shown in Fig. 14.3, element 1 is at HEAD position (0th) and element 2 is at TAIL position (5th).
The element 5 is predecessor of the element 8 and 4 is successor. Every element can act as predecessor
excluding the first element because it is the first element of the list. The list has the following properties.
a) The list can be enlarged or reduced from the end.
b) The TAIL (ending) position of the list depends on how long the list is extended by the user.
c) Various operations such as transverse, insertion and deletion can be performed on the list.
d) The list can be implemented by applying static (array) or dynamic (pointer) implementation.
14.3 IMPLEMENTATION OF A LIST
There are two methods to implement the list: static and dynamic.
1) Static implementation: Static implementation can be achieved using arrays. Though it is a very
simple method, it has a few limitations. Once the size of an array is declared, its size cannot be
altered during program execution. In array declaration, memory is allocated equal to array size.
Thus, the program itself decides the amount of memory needed and it informs accordingly to the
compiler. Here memory requirement is determined in advance before compilation and the compiler
provides the required memory.
Static allocation of memory has a few disadvantages. It is an inefficient memory allocation
technique. It is because, in case we intend to store less arguments than declared, memory is wasted
and if we desire to store more elements than declared, array could not expand. Hence, in both
cases we find inefficient use of memory. It is suitable only when we exactly know the number of
elements to be stored.
2) Dynamic implementation: Pointers can also be used for implementation of a stack. The linked
list is an example of this implementation. The limitations noticed in static implementation can be
removed using dynamic implementation. The dynamic implementation is achieved using pointers.
Using pointer implementation at run time there is no restriction on number of elements. The
stack may be expanded. It is efficient in memory allocation because the program informs the
compiler its memory requirement at run time. Memory is allocated only after an element is pushed.
Both the above implementations are illustrated with suitable examples.
Recall that array name itself is a pointer. Pointer implementation of a stack is carried out in a
manner similar to array implementation. A stack is a particularly straightforward version of linked
lists. The implementation of array-like elements can be done using a pointer. Like an array, elements
can be stored in successive memory locations using a pointer. First, we learn a simple program to
create a stack—using a pointer instead of an array.
Both the above implementations are illustrated in this chapter with suitable examples.
14.4 TRAVERSAL OF A LIST
A simple list can be created using an array in which elements are stored in successive memory
locations. Consider the following program.
14.1 Write a program to create a simple list of elements. Display the list in original and reverse
order.
# include <stdio.h >
# include cconio.h>
main ()
{
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.