Show me basic example of linked list impl in C++.
- User
Show me basic example of linked list impl in C++.
Assistant
Here's a basic implementation of a singly linked list in C++:
#include <iostream> using namespace std; // Node class to represent each element in the list class Node { public: int data; Node* next; Node(int value) { data = value; next = nullptr; } }; // LinkedList class class LinkedList { private: Node* head; public: // Constructor LinkedList() { head = nullptr; } // Destructor to free memory ~LinkedList() { Node* current = head; while (current != nullptr) { Node* temp = current; current = current->next; delete temp; } } // Insert at the beginning void insertAtBeginning(int value) { Node* newNode = new Node(value); newNode->next = head; head = newNode; } // Insert at the end void insertAtEnd(int value) { Node* newNode = new Node(value); if (head == nullptr) { head = newNode; return; } Node* current = head; while (current->next != nullptr) { current = current->next; } current->next = newNode; } // Delete a node with given value void deleteNode(int value) { if (head == nullptr) return; // If head needs to be deleted if (head->data == value) { Node* temp = head; head = head->next; delete temp; return; } // Search for the node to delete Node* current = head; while (current->next != nullptr && current->next->data != value) { current = current->next; } // If node was found if (current->next != nullptr) { Node* temp = current->next; current->next = current->next->next; delete temp; } } // Display the list void display() { if (head == nullptr) { cout << "List is empty" << endl; return; } Node* current = head; cout << "List: "; while (current != nullptr) { cout << current->data << " -> "; current = current->next; } cout << "NULL" << endl; } // Search for a value bool search(int value) { Node* current = head; while (current != nullptr) { if (current->data == value) { return true; } current = current->next; } return false; } }; // Example usage int main() { LinkedList list; // Insert some values list.insertAtEnd(10); list.insertAtEnd(20); list.insertAtEnd(30); list.insertAtBeginning(5); // Display the list list.display(); // Output: List: 5 -> 10 -> 20 -> 30 -> NULL // Delete a node list.deleteNode(20); list.display(); // Output: List: 5 -> 10 -> 30 -> NULL // Search for values cout << "Search for 10: " << (list.search(10) ? "Found" : "Not found") << endl; cout << "Search for 20: " << (list.search(20) ? "Found" : "Not found") << endl; return 0; }This implementation includes:
Key Components:
Nodeclass: Represents each element with data and a pointer to the next nodeLinkedListclass: Manages the list operations
Basic Operations:
insertAtBeginning(): O(1) - Adds element at the startinsertAtEnd(): O(n) - Adds element at the enddeleteNode(): O(n) - Removes first occurrence of a valuedisplay(): O(n) - Prints all elementssearch(): O(n) - Checks if a value exists
Memory Management:
- Constructor initializes head to nullptr
- Destructor properly deallocates all nodes to prevent memory leaks
- Uses
newanddeletefor dynamic memory allocation
This is a foundation you can extend with additional operations like inserting at a specific position, reversing the list, or finding the length.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.