Define list. How can you use linked list to implement stack? Explain circular linked list.

A list is an ordered collection of elements of the same type, such as (10, 20, 30). It can be stored in an array (static list) or as a linked list, where each element (node) holds the data and a pointer to the next node, so the list can grow and shrink at run time.

Stack using a linked list

The head of the linked list is used as the top of the stack. Push inserts a node at the beginning and pop deletes the first node, so both take O(1) time and there is no overflow until memory runs out.

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

struct node {
    int data;
    struct node *next;
};
struct node *top = NULL;

void push(int x) {
    struct node *n = (struct node *)malloc(sizeof(struct node));
    n->data = x;
    n->next = top;        /* new node points to the old top */
    top = n;              /* new node becomes the top */
}

void pop(void) {
    struct node *t;
    if (top == NULL) {
        printf("Stack underflow\n");
        return;
    }
    t = top;
    printf("%d popped\n", t->data);
    top = top->next;
    free(t);
}

Circular linked list

In a circular linked list the last node points back to the first node instead of NULL, so the list forms a ring.

 +----+    +----+    +----+
 | 10 |--->| 20 |--->| 30 |---+
 +----+    +----+    +----+   |
   ^--------------------------+

• There is no NULL at the end. Traversal stops when it comes back to the starting node.
• Any node can be used as a starting point, and from the last node the first node is reached in one step.
• It is used in round-robin CPU scheduling, circular buffers and multiplayer turn-taking.

In a doubly circular linked list, the first node's previous pointer also points to the last node.