Example of how to implement a templated linked list in C++

// Example of how to implement a templated linked list

#include <iostream>

#include <string>

using namespace std;

class Cat {

public:

Cat(string name = "unnamed", int age = 0): name(name), age(age) { }

const string name;

int age;

friend ostream& operator<<(ostream& os, Cat* cat) {

os << "Cat: { name: "<< cat->name << ", age: " << cat->age << " }";

return os;

}

};

template<class T>

class LinkedList {

private:

class Node {

friend class LinkedList;

T data;

Node* next;

Node(T data, Node* next = NULL): data(data), next(next) { }

};

Node* head;

public:

LinkedList(): head(NULL) { }

~LinkedList() {

Node* currentNode = head;

Node* nextNode = NULL;

while (currentNode != NULL) {

nextNode = currentNode->next;

delete currentNode;

currentNode = nextNode;

}

}

void append(T data) {

Node* newNode = new Node(data);

if (head == NULL) {

head = newNode;

} else {

Node* currentNode = head;

while (currentNode->next != NULL) {

currentNode = currentNode->next;

}

currentNode->next = newNode;

}

}

void prepend(T data) {

Node* newNode = new Node(data, head);

head = newNode;

}

T getAtIndex(int index) const {

Node* currentNode = head;

while (currentNode != NULL) {

if (index == 0) {

return currentNode->data;

}

currentNode = currentNode->next;

index--;

}

return NULL;

}

void removeAtIndex(int index) {

if (index == 0) {

Node* newHead = head->next;

delete head;

head = newHead;

} else {

Node* prevNode = NULL;

Node* currentNode = head;

while (currentNode != NULL) {

if (index == 0) {

prevNode->next = currentNode->next;

delete currentNode;

}

prevNode = currentNode;

currentNode = currentNode->next;

index--;

}

}

}

friend ostream& operator<<(ostream& os, const LinkedList& linkedList) {

os << "[";

Node* currentNode = linkedList.head;

while (currentNode != NULL) {

os << currentNode->data << ((currentNode->next == NULL) ? "" : ", ");

currentNode = currentNode->next;

}

os << "]";

return os;

}

};

int main(int argc, const char * argv[]) {

LinkedList<int> intList = LinkedList<int>();

intList.append(3);

intList.append(4);

intList.append(5);

intList.append(6);

intList.append(100);

intList.prepend(1);

intList.removeAtIndex(5);

intList.removeAtIndex(0);

intList.removeAtIndex(2);

cout << intList << endl; // [3, 4, 6]

cout << "Number at index 1: " << intList.getAtIndex(1) << endl; // Number at index 1: 4

LinkedList<Cat*> catList = LinkedList<Cat*>();

catList.append(new Cat("Estabon", 2));

catList.append(new Cat("Cat-Man", 8));

cout << catList << endl; // [Cat: { name: Estabon, age: 2 }, Cat: { name: Cat-Man, age: 8 }]

return 0;

}