#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdbool.h>
/*
* A minimal doubly‑linked list node.
* It contains only pointers to the previous and next nodes.
* The actual data will be stored in a struct that embeds this node.
*/
struct DNode {
struct DNode *previous;
struct DNode *next;
};
/*
* A List contains two sentinel nodes:
* head — marks the beginning (does not store data)
* tail — marks the end (does not store data)
*
* These sentinels simplify insertion/removal logic because
* the list is never truly empty — the sentinels always exist.
*/
struct List {
struct DNode head; // sentinel head
struct DNode tail; // sentinel tail
};
typedef struct DNode *NODE;
typedef struct List *LIST;
/*
* Create and initialize an empty list.
* The head points forward to the tail.
* The tail points backward to the head.
*/
LIST newList(void) {
LIST l = malloc(sizeof(struct List));
if (!l) return NULL;
l->head.previous = NULL; // head has no previous
l->head.next = &l->tail; // head → tail
l->tail.previous = &l->head; // tail ← head
l->tail.next = NULL; // tail has no next
return l;
}
/*
* A list is empty when head.next points directly to tail.
*/
bool isEmpty(LIST l) {
return l->head.next == &l->tail;
}
/*
* Return the first real node (NULL if empty).
*/
NODE getHead(LIST l) {
return isEmpty(l) ? NULL : l->head.next;
}
/*
* Return the last real node (NULL if empty).
*/
NODE getTail(LIST l) {
return isEmpty(l) ? NULL : l->tail.previous;
}
/*
* Insert a node immediately after the head sentinel.
*/
NODE addHead(LIST l, NODE n) {
NODE first = l->head.next;
n->previous = &l->head;
n->next = first;
first->previous = n;
l->head.next = n;
return n;
}
/*
* Insert a node immediately before the tail sentinel.
*/
NODE addTail(LIST l, NODE n) {
NODE last = l->tail.previous;
n->previous = last;
n->next = &l->tail;
last->next = n;
l->tail.previous = n;
return n;
}
/*
* Remove and return the first real node.
*/
NODE removeHead(LIST l) {
if (isEmpty(l)) return NULL;
NODE n = l->head.next; // first real node
NODE next = n->next;
l->head.next = next;
next->previous = &l->head;
return n;
}
/*
* Remove and return the last real node.
*/
NODE removeTail(LIST l) {
if (isEmpty(l)) return NULL;
NODE n = l->tail.previous; // last real node
NODE prev = n->previous;
prev->next = &l->tail;
l->tail.previous = prev;
return n;
}
/*
* Insert node n after node r.
* Assumes r is already in the list.
*/
NODE insertAfter(LIST l, NODE r, NODE n) {
NODE s = r->next;
n->previous = r;
n->next = s;
s->previous = n;
r->next = n;
return n;
}
/*
* Remove a specific node from the list.
* Assumes n is in the list.
*/
NODE removeNode(LIST l, NODE n) {
NODE p = n->previous;
NODE s = n->next;
p->next = s;
s->previous = p;
return n;
}
/*
* A user-defined node that stores actual data.
* It embeds a DNode so it can be linked into the list.
*/
struct IntNode {
struct DNode node; // embedded list node
int data; // payload
};
/*
* Print list from head → tail.
*/
void printForward(LIST l) {
NODE n = l->head.next;
printf("Print Forward: ");
while (n != &l->tail) {
struct IntNode *m = (struct IntNode *)n;
printf("%d ", m->data);
n = n->next;
}
printf("\n");
}
/*
* Print list from tail → head.
*/
void printBackward(LIST l) {
NODE n = l->tail.previous;
printf("Print Backward: ");
while (n != &l->head) {
struct IntNode *m = (struct IntNode *)n;
printf("%d ", m->data);
n = n->previous;
}
printf("\n");
}
int main() {
srand((unsigned)time(NULL)); // seed random generator
LIST l = newList();
if (!l) return 1;
// Add 5 random nodes at tail
for (int i = 0; i < 5; i++) {
struct IntNode *n = malloc(sizeof(struct IntNode));
n->data = rand() % 100; // random number 0–99
addTail(l, (NODE)n);
}
puts("Add 5 nodes at tail");
printForward(l);
printBackward(l);
// Insert a node at head
struct IntNode *h = malloc(sizeof(struct IntNode));
h->data = 999;
addHead(l, (NODE)h);
puts("Insert 999 at head");
printForward(l);
// Remove head node
struct IntNode *rh = (struct IntNode *)removeHead(l);
printf("Removed head: %d\n", rh->data);
free(rh);
printForward(l);
// Remove all nodes from tail
while (!isEmpty(l)) {
struct IntNode *n = (struct IntNode *)removeTail(l);
printf("Removed tail: %d\n", n->data);
free(n);
}
free(l);
return 0;
}
/*
run:
Add 5 nodes at tail
Print Forward: 67 16 95 6 50
Print Backward: 50 6 95 16 67
Insert 999 at head
Print Forward: 999 67 16 95 6 50
Removed head: 999
Print Forward: 67 16 95 6 50
Removed tail: 50
Removed tail: 6
Removed tail: 95
Removed tail: 16
Removed tail: 67
*/
