Singly Linked List Operations
Updating a Node
If the process of finding the node is not considered, updating a linked list is as simple as updating an array: replace the old data directly with the new data.
singly_linked_list_t *singly_linked_list_set(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 = list->head;
for (int i = 0; i < index; i++) {
node = node->next;
}
node->data = elem;
return list;
}Inserting a Node
There are three cases when inserting a node into a linked list:
-
Tail Insertion
Point the last node's
nextpointer to the newly inserted node. -
Middle Insertion
First point the new node's
nextpointer to the node at the insertion position, then point the preceding node'snextpointer to the new node. -
Head Insertion
First point the new node's
nextpointer to the original head node, then make the new node the head of the list.
Singly linked-list insertion
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
KNOWLEDGE QUIZ
As long as memory is available, an unlimited number of elements can be inserted into a linked list, without considering expansion as an array must. If the search before insertion is excluded and only the insertion itself is considered, the time complexity is .
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
Linked-list deletion also has three cases:
-
Tail Deletion
Point the second-to-last node's
nextpointer to null. -
Middle Deletion
Point the preceding node's
nextpointer to the node after the node being deleted. -
Head Deletion
Set the head of the list to the original head node's
nextpointer.
Singly linked-list deletion
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
Many high-level languages, such as Java, provide automatic garbage collection. A deleted node does not need to be released explicitly; it will be reclaimed when no external reference points to it.
If the search before deletion is excluded and only the deletion itself is considered, the time complexity is .
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;
}Reversing a Linked List
Reversing a linked list requires changing the direction of its pointers.
Recursive reversal starts from the tail node and proceeds backward, changing each node's pointer so that it points to the preceding node.
Iterative reversal starts at the first node, traverses to the tail, and changes each visited node's pointer so that it points to the preceding node.
Reverse a singly linked list
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
static node_t *__singly_linked_list_reverse_recursive(node_t *node) {
if (node == NULL || node->next == NULL) {
return node;
}
node_t *new_head = __singly_linked_list_reverse_recursive(node->next);
node->next->next = node;
node->next = NULL;
return new_head;
}
singly_linked_list_t *singly_linked_list_reverse(singly_linked_list_t *list) {
node_t *prev = NULL;
node_t *current = list->head;
while (current != NULL) {
node_t *next = current->next;
current->next = prev;
prev = current;
current = next;
}
list->tail = list->head;
list->head = prev;
return list;
}