#### Stack using an array - drawback

If we implement the stack using an array, we need to specify the array size at the beginning(at compile time).

We can't change the size of an array at runtime. So, it will only work for a fixed number of elements.

#### Solution

We can implement the stack using the linked list.

In the linked list, we can change its size at runtime.

## Let's implement the stack using linked list

If you are not familiar with linked list and stack, kindly visit the below links before we get started.

Inserting a node at the beginning of a linked list
Stack using array

#### Node structure for stack

```struct node
{
int data;
struct node *next;
};
```

#### To point the last inserted node

```struct node *head = NULL;
```

head = NULL indicates the empty stack.

## Push function

We should create the linked in reverse order. So that the head node will always point the last inserted data.

Using this method, we can access the last inserted element in constant time.

Like,

#### Push function Algorithm

2. Create a new node with given data.

3. Make the new node points to the head node.

4. Now make the new node as the head node.

```void push(int val)
{
//create new node
struct node *newNode = malloc(sizeof(struct node));
newNode->data = val;

//make the new node points to the head node

//make the new node as head node
//so that head will always point the last inserted data
}
```

#### insert 30

If we create linked in normal order.

Like,

We need to iterate the linked list to access the last inserted element.

## Pop function

1.Check whether the head node is NULL

The stack is empty. we can't pop the element.

3.Otherwise,

```void pop()
{
//temp is used to free the head node
struct node *temp;

printf("Stack is Empty\n");
else
{

//make the head node points to the next node.
//logically removing the node

//free the poped element's memory
free(temp);
}
}
```

## Implementation of stack using linked list

```/*
* Program  : stack using linked list
* Language : c
*/

#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *next;
};

void push(int val)
{
//create new node
struct node *newNode = malloc(sizeof(struct node));
newNode->data = val;

//make the new node points to the head node

//make the new node as head node
//so that head will always point the last inserted data
}

void pop()
{
//temp is used to free the head node
struct node *temp;

printf("Stack is Empty\n");
else
{

//make the head node points to the next node.
//logically removing the node

//free the poped element's memory
free(temp);
}
}

void printList()
{

//iterate the entire linked list and print the data
while(temp != NULL)
{
printf("%d->", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main()
{
push(10);
push(20);
push(30);
printList();
pop();
printf("After the pop, the new linked list\n");
printList();
pop();
printf("After the pop, the new linked list\n");
printList();

return 0;
}
```