Singly-linked list. Addition (insertion) operation.
Insertion into a singly-linked list has two special cases. It's insertion a new node before the head (to the very beginning of the list) and after the tail (to the very end of the list). In any other case, new node is inserted in the middle of the list and so, has a predecessor and successor in the list. There is a description of all these cases below.
Empty list case
When list is empty, which is indicated by (head == NULL)condition, the insertion is quite simple. Algorithm sets both head and tail to point to the new node.
Add first
In this case, new node is inserted right before the current head node.
- Update the next link of a new node, to point to the current head node.
- Update head link to point to the new node.
Add last
In this case, new node is inserted right after the current tail node.
It can be done in two steps:
- Update the next link of the current tail node, to point to the new node.
- Update tail link to point to the new node.
General case
In general case, new node is always inserted between two nodes, which are already in the list. Head and tail links are not updated in this case.
Such an insert can be done in two steps:
- Update link of the "previous" node, to point to the new node.
- Update link of the new node, to point to the "next" node.
Code snippets
All cases, shown above, can be implemented in one function with two arguments, which are node to insert after and a new node. For add first operation, the arguments are (NULL, newNode). For add last operation, the arguments are (tail, newNode). Though, this specific operations (add first and add last) can be implemented separately, in order to avoid unnecessary checks.
Java implementation
public class SinglyLinkedList {
…
public void addLast(SinglyLinkedListNode newNode) {
if (newNode == null)
return;
else {
newNode.next = null;
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
}
}
public void addFirst(SinglyLinkedListNode newNode) {
if (newNode == null)
return;
else {
if (head == null) {
newNode.next = null;
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head = newNode;
}
}
}
public void insertAfter(SinglyLinkedListNode previous,
SinglyLinkedListNode newNode) {
if (newNode == null)
return;
else {
if (previous == null)
addFirst(newNode);
else if (previous == tail)
addLast(newNode);
else {
SinglyLinkedListNode next = previous.next;
previous.next = newNode;
newNode.next = next;
}
}
}
}
C++ implementation
void SinglyLinkedList::addLast(SinglyLinkedListNode *newNode) {
if (newNode == NULL)
return;
else {
newNode->next = NULL;
if (head == NULL) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
}
void SinglyLinkedList::addFirst(SinglyLinkedListNode *newNode) {
if (newNode == NULL)
return;
else {
if (head == NULL) {
newNode->next = NULL;
head = newNode;
tail = newNode;
} else {
newNode->next = head;
head = newNode;
}
}
}
void SinglyLinkedList::insertAfter(SinglyLinkedListNode *previous,
SinglyLinkedListNode *newNode) {
if (newNode == NULL)
return;
else {
if (previous == NULL)
addFirst(newNode);
else if (previous == tail)
addLast(newNode);
else {
SinglyLinkedListNode *next = previous->next;
previous->next = newNode;
newNode->next = next;
}
}
}
Recommended books
- Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
- Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
- Robert Lafore. Data Structures and Algorithms in Java. (Practice)
- Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)
| Previous: Singly-linked list traversal | Next: Removing a node from slist |
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!