A single linked list is a data structure that contains a sequence of nodes. Each node contains two fields:
data
: Contains the data for the node.next
: Contains a pointer to the next node in the list.The first node in the list is called the head
node, and the last node in the list is called the tail
node.
To create a single linked list, we need to create a head
node and a tail
node. The head
node will point to the first node in the list, and the tail
node will point to the last node in the list.
We can create a single linked list in C++ like this:
// Create a head node.
Node* head = new Node();
// Create a tail node.
Node* tail = new Node();
// Set the head node's "next" field to point to the tail node.
head->next = tail;
To add a node to a single linked list, we need to do two things:
next
field of the last node in the list to point to the new node.We can add a node to a single linked list in C++ like this:
// Create a new node.
Node* newNode = new Node();
// Set the "next" field of the last node in the list to point to the new node.
tail->next = newNode;
// Set the new node as the new tail node.
tail = newNode;
To delete a node from a single linked list, we need to do two things:
next
field of the node before the node to be deleted to point to the node after the node to be deleted.We can delete a node from a single linked list in C++ like this:
// Set the "next" field of the node before the node to be deleted to point to the node after the node to be deleted.
nodeBefore->next = nodeToDelete->next;
// Delete the node.
delete nodeToDelete;
To traverse a single linked list, we need to start at the head
node and follow the next
pointers until we reach the tail
node.
We can traverse a single linked list in C++ like this:
// Start at the head node.
Node* currentNode = head;
// Follow the "next" pointers until we reach the tail node.
while (currentNode != tail)
{
// Do something with the data in the node.
// Move to the next node.
currentNode = currentNode->next;
}