Keep a playlist in a doubly linked list, with a cursor on the song that is playing.
What to build
A doubly linked list with a current item, changed by commands.
Requirements
add xinsertsxjust after the current item and makes it current. In an empty list it becomes the only item.nextandprevmove the cursor one place, when there is an item in that direction.removedeletes the current item. The item after it becomes current, or the item before it if there is none after. It does nothing on an empty list.showprints the list from the first item, with the current item in square brackets, orempty.
Input
The first line has q. Each of the next q lines has one command.
Output
One line for each show.
Constraints
1 ≤ q ≤ 100.
Example
Input:
10
add 1
add 2
add 3
prev
add 9
show
remove
show
remove
show
Output:
1 2 [9] 3
1 2 [3]
1 [2]
Why it works
Inserting and removing next to a known node changes only the pointers around it, so each command is O(1). An array would have to shift every later song.
Examples
Example 1 · Input
10 add 1 add 2 add 3 prev add 9 show remove show remove show
Expected output
1 2 [9] 3 1 2 [3] 1 [2]
Example 2 · Input
4 show remove add 5 show
Expected output
empty [5]
Hints
Hint 1
Keep two pointers: head for the first item and cur for the current one.
Hint 2
To add after cur, set the new node's prev and next first, then fix the node after and cur->next.
Hint 3
When removing, decide the new current item before you free the node.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node {
int value;
struct node *prev, *next;
} Node;
Node *head = NULL, *cur = NULL;
void add(int value) {
Node *n = malloc(sizeof(Node));
n->value = value;
if (cur == NULL) {
n->prev = NULL;
n->next = NULL;
head = n;
} else {
n->prev = cur;
n->next = cur->next;
if (cur->next != NULL) cur->next->prev = n;
cur->next = n;
}
cur = n;
}
void remove_current(void) {
if (cur == NULL) return;
Node *n = cur;
if (n->prev != NULL) n->prev->next = n->next;
else head = n->next;
if (n->next != NULL) n->next->prev = n->prev;
cur = n->next != NULL ? n->next : n->prev;
free(n);
}
void show(void) {
if (head == NULL) printf("empty");
for (Node *p = head; p != NULL; p = p->next) {
if (p != head) printf(" ");
if (p == cur) printf("[%d]", p->value);
else printf("%d", p->value);
}
printf("\n");
}
int main(void) {
int q;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
char cmd[10];
scanf("%9s", cmd);
if (strcmp(cmd, "add") == 0) {
int x;
scanf("%d", &x);
add(x);
} else if (strcmp(cmd, "next") == 0) {
if (cur != NULL && cur->next != NULL) cur = cur->next;
} else if (strcmp(cmd, "prev") == 0) {
if (cur != NULL && cur->prev != NULL) cur = cur->prev;
} else if (strcmp(cmd, "remove") == 0) {
remove_current();
} else {
show();
}
}
while (head != NULL) {
Node *next = head->next;
free(head);
head = next;
}
return 0;
}