Implement linked list
Implement a linked list
/*
* LinkedList.cpp
*
* Created on: Mar 31, 2012
* Author: Kiran Hegde
*/
#include <iostream>
using namespace std;
/**
* Node holding integer data
*/
struct Node {
int data;
Node *next;
};
/**
* A linked list
*/
class LinkedList {
public:
LinkedList() {
head = 0;
}
~LinkedList() {
Node *curr = head;
while (curr) {
Node *temp = curr->next;
delete curr;
curr = temp;
}
}
void insertBack(int n) {
Node *node = new Node();
node->data = n;
node->next = NULL;
if (head == NULL) {
head = node;
return;
}
Node *curr = head;
while (curr) {
if (curr->next == NULL) {
curr->next = node;
return;
}
curr = curr->next;
}
}
void insertFront(int n) {
Node *node = new Node();
node->data = n;
node->next = head;
head = node;
}
void removeBack() {
if (head == NULL)
return;
if (head->next == NULL) {
delete head;
head = NULL;
return;
}
Node *curr = head;
Node *prev = 0;
while (curr->next != NULL) {
prev = curr;
curr = curr->next;
}
prev->next = NULL;
delete curr;
}
void removeFront() {
if (head == 0)
return;
Node *temp = head;
head = head->next;
delete temp;
}
void remove(int n) {
Node *curr = head;
if (curr == 0)
return;
if (curr->data == n) {
head = head->next;
delete curr;
}
Node *prev = 0;
while (curr != 0) {
if (curr->data == n) {
break;
}
prev = curr;
curr = curr->next;
}
prev->next = curr->next;
delete curr;
}
Node *find(int n) {
if (head == NULL)
return NULL;
Node *curr = head;
while (curr != 0) {
if (curr->data == n) {
return curr;
}
curr = curr->next;
}
return NULL;
}
void insertAfter(int n, Node *node) {
if (node == 0) {
insertBack (n);
return;
}
Node *curr = head;
while (curr != 0) {
if (curr == node) {
Node *newNode = new Node();
newNode->data = n;
Node *temp = curr->next;
curr->next = newNode;
newNode->next = temp;
return;
}
curr = curr->next;
}
}
void print() {
Node *curr = head;
if (curr == 0) {
cout << "EMPTY" << endl;
} else {
while (curr) {
cout << curr->data << "-->";
curr = curr->next;
}
cout << "EMPTY" << endl;
}
}
void reverse() {
Node *curr = head;
Node *prev = 0;
while (curr) {
Node *temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
head = prev;
}
private:
Node *head;
};
/**
* Test the code
*/
int main() {
LinkedList ll;
ll.insertBack(1);
ll.insertBack(2);
ll.insertBack(5);
ll.insertBack(8);
ll.insertBack(10);
ll.insertBack(20);
ll.print();
ll.insertFront(11);
ll.insertFront(12);
ll.print();
ll.removeFront();
ll.removeBack();
ll.print();
ll.insertFront(21);
ll.insertFront(22);
ll.remove(5);
ll.remove(8);
ll.print();
Node* n = ll.find(1);
ll.insertAfter(100, n);
ll.print();
ll.reverse();
ll.print();
return 0;
}