How do you implement a stack using an Linked List?

A stack is represented using nodes of a linked list. Each node consists of two parts:

data - The data part of each node contains the assigned value
next (storing address of next node) - next points to the node containing the next item in the stack
top - refers to the topmost node in the stack.

Both the push() and pop() operations are carried out at the front/top of the linked list and hence take O(1) time.

One noticeable difference is that a stack can also be implemented using arrays but here we are going for the Linked List approach since arrays are of limited size and the size of the stack has to be predetermined whereas in a linked list implementation nodes can be added according to the userâ€™s requirements.

PSUEDO CODE: -

``````void push(int value) {
struct Node *newNode;
newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = value; // assign value to the node
if (top == NULL) {
newNode->next = NULL;
} else {
newNode->next = top; // Make the node as top
}
top = newNode; // top always points to the newly created node
printf("Node is Inserted\n\n");
}

int pop() {
if (top == NULL) {
printf("\nStack Underflow\n");
} else {
struct Node *temp = top;
int temp_data = top->data;
top = top->next;
free(temp);
return temp_data;
}
}

void display() {
// Display the elements of the stack
if (top == NULL) {
printf("\nStack Underflow\n");
} else {
printf("The stack is \n");
struct Node *temp = top;
while (temp->next != NULL) {
printf("%d--->", temp->data);
temp = temp->next;
}
printf("%d--->NULL\n\n", temp->data);
}
}
``````