Definition
A linked list is a linear data structure where each element (called a node) contains data and a pointer to the next node. Unlike arrays, linked lists allow efficient insertion and deletion of elements without reallocating or reorganizing the entire structure.
In C++, a singly linked list node can be defined as:
``cpp`
struct Node {
int data;
Node next;
};
Worked Example
Let's implement a simple singly linked list in C++ that supports insertion at the end and printing all elements.
`cpp
#include
using namespace std;
// Node definition
struct Node {
int data;
Node next;
};
// Insert at end
void insert(Node& head, int value) {
Node newNode = new Node{value, nullptr};
if (head == nullptr) {
head = newNode;
return;
}
Node temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
// Print list
void printList(Node head) {
Node temp = head;
while (temp != nullptr) {
cout data next;
}
cout << endl;
}
// Example usage
int main() {
Node head = nullptr;
insert(head, 10);
insert(head, 20);
insert(head, 30);
printList(head); // Output: 10 20 30
return 0;
}
``
Key Takeaways
- A linked list consists of nodes, each with data and a pointer to the next node.
- Linked lists allow efficient insertion and deletion, especially compared to arrays.
- In C++, use structs and pointers to implement linked lists.