why are there questions and algorithms for implementing stack using a linked list ?

Question

Array is best data structure, ain't it ?

As always deletion and insertion in top,

then also many papers and books write on implementing stack using linked list.

Size of array aint no limit, as can be kept very big, array implementation only seems logical

Answer 1

No, because if you use array for stack the size of stack will be constant and you cant dynamically change the stack's size



insertion and deletion in top, because it is the properties of stack and if you change these properties it will not remain stack..



using linked list is very good thing because the size will be dynamically..

Answer 2

Array isn't the best structure, since the size is indeed a limit, no matter how big that limit is.



The array may be suitable for certain implementations where the size of the stack is guaranteed to be limited and the limit is small enough that permanently reserving space for it doesn't make a negative impact on the performance of the program.



But it isn't the "best" for all cases where a stack is used.

Answer 3

An array was orriginally a linked (or unlinked) structure



struct name

{

int

char[10]

etc

}



With sizeof(name) you can have an array of many 'name' structs and simply jump up and down the list, ut only if your data area was created as one continuous data area, you have to know how much memory you need before you need it.



myPointer += sizeof(name)

With pre-checks to ensure you don't go out of bounds, nip up and down your data array.



struct

{

next equals the physical address of the next record

prevt equals the physical address of the previous record

}



These records could be scattered around in memory, each created with a malloc (call for system memory). The problem is that as you are storing these pointers in the array so you must lock those memory locations. The system can not move them to make room for other things.



These days nearly all memory is referenced, so that the operating system can manipulate the memory area in various ways, and your program does not need to care where that memory is located physically. So we now access the data by index, or reference.



Arrays are ok, the problem but as you are learning avoid using it's functions that aid stack creation, instead do it yourself.



A first in first out stack only requires you to add data to the end of the stack, and only read from the end of the stack, checking that you are not going to attempt a read at index '-1'. All you need to do is check that there is more than zero data items before you read one. Remembering to remove each item as you read it.



A last in first out stack you can add data to the end and only read data from index zero, Remembering to check there is data and removing Array[0] after you have read it.



A stack as a linked list has several uses, you sometimes have a few mini-stacks in data, so that the basic stack system is no use to your application but also a full lone stack is not needed. In this case items can relate to other items, not necessarily added to the stack in order. If you ever write a compiler you may find yourself writing such a stack as this.



StackItem

{

index of next item

index of previous item

marker as a stating point for each mini stack

}