Doubly Linked List Operations
Each node in a doubly linked list stores both prev and next. Insertion and deletion must repair the forward and backward links separately.
Inserting a Node
Head insertion updates head, tail insertion updates tail, and middle insertion connects both neighbors to the new node.
INTERACTIVE LAB
Doubly linked-list insertion
ACCESSPRO
PRO EXCLUSIVEGo further with Pro
Unlock Pro accessUnlock the complete interactive lab, deeper explanations, and curated reference answers.
C
singly_linked_list_t *singly_linked_list_insert(singly_linked_list_t *list, int index, T elem) {
if (list == NULL) {
return NULL;
}
if (index < 0 || index > list->size) {
fprintf(stderr, "Error: index out of bound.\n");
return list;
}
node_t *node = singly_linked_list_node_create(elem);
if (index == 0) {
node->next = list->head;
list->head = node;
if (list->tail == NULL) {
list->tail = node;
}
} else {
node_t *prev = list->head;
for (int i = 0; i < index - 1; i++) {
prev = prev->next;
}
node->next = prev->next;
prev->next = node;
if (node->next == NULL) {
list->tail = node;
}
}
list->size++;
return list;
}Deleting a Node
Deleting the head or tail updates the corresponding endpoint. Deleting a middle node connects its predecessor and successor directly in both directions.
INTERACTIVE LAB
Doubly linked-list deletion
ACCESSPRO
PRO EXCLUSIVEGo further with Pro
Unlock Pro accessUnlock the complete interactive lab, deeper explanations, and curated reference answers.
KNOWLEDGE QUIZ
QUESTION
In A ⇄ B ⇄ C, B is a middle node. Which assignments preserve both directions after deleting B?
C
T singly_linked_list_remove(singly_linked_list_t *list, int index) {
if (list == NULL || index < 0 || index >= list->size) {
exit(1);
}
node_t *node;
if (index == 0) {
node = list->head;
list->head = node->next;
if (list->tail == node) {
list->tail = NULL;
}
} else {
node_t *prev = list->head;
for (int i = 0; i < index - 1; i++) {
prev = prev->next;
}
node = prev->next;
prev->next = node->next;
if (list->tail == node) {
list->tail = prev;
}
}
T elem = node->data;
free(node);
list->size--;
return elem;
}