linked list implementation to experiment with it in C++

linked_list.cpp

/*
Linked_list implementation for cracking the code
questions
*/
#include <iostream>
#include <stdlib.h>	/* srand, rand */
#include <map>

using namespace std;
template <typename dataType> 

class List{

private:
	struct Node{
		Node *next;
		dataType data;
	};

public:
	//constructer
	List();
	List(const List& aList); //copy constructer for deep copy
	List(Node *head);

	//destructor
	~List();

	//operations
	bool isEmpty();
	int getLength();
	void insert(int index, dataType data);
	void remove(int index);
	dataType retrieve(int index);
	dataType extract(int index); /*get the value and remove the node */ 
	void printList();
	void removeDuplicates();
	void randomIntFill(int item_num, int max);
	void removeNode(Node* node);
	Node* find(int index);
	Node* sumDigitsWithCarry(Node* head1, Node* head2); // given two list of digits sum those lists
							   // like they are natural numbers with given 1o's order
							   // 9 -> 5 + 9 -> 4 = 8 -> 0 -> 1 = 108

private:	
	int size;
	Node *head;
};


template <typename dataType>
List<dataType>::~List(){
	while(!isEmpty())
		remove(0);
}

template <typename dataType>
List<dataType>::List(){
	size = 0;
	head = NULL;
}

template <typename dataType>
List<dataType>::List(Node* aHead){
	size = 0;
	head = aHead;
	for(Node* cur = head; cur != NULL; cur = cur->next){
		// cout << cur -> data << endl;
		size++;
	}
}

template <typename dataType>
List<dataType>::List(const List& aList){
	size = aList.size;

	head = new Node;
	head -> data = aList.head->data;
	Node *cur = head;
	
	for(Node *cp_node = aList.head->next; cp_node != NULL ; cp_node = cp_node->next){
		cur -> next = new Node;
		cur = cur->next;
		cur -> data = cp_node -> data;
	}

	cur -> next = NULL;
}

template <typename dataType>
void List<dataType>::insert(int index, dataType data){
	if (index < 0){
		cout << "Negative index!!" << endl;
		return;
	}
	if (index > size){
		cout << "Extension is not supported!!" << endl;
		return;
	}
	//if insert head
	if(index == 0){
		Node *new_head = new Node;
		new_head -> next = head;
		new_head -> data = data;
		head = new_head;
	}//if insert into middle
	else{
		Node *prev = find(index-1);
		Node *node = new Node;
		node -> data = data;
		node -> next = prev -> next;
		prev -> next = node;
	}
	size ++;
}

template <typename dataType>
dataType List<dataType> :: extract(int index){
	if (index < 0 || index >= size){
		cout << "Wrong index value !!!" << endl;
		return 0;
	}
	Node* node = find(index);
	dataType ret_data = node -> data;
	remove(index);
	node = NULL;
	return ret_data;
}

template <typename dataType>
void List<dataType>::remove(int index){
	if(size == 0){
		cout << "No item to remove in list!!" << endl;
		return;
	}
	else if (index >= size || index < 0){
		cout << "No item with given index!!" << endl;
		return;
	}

	Node *cur;
	//if head ptr
	if(index ==  0){
		cur = head;
		head = head->next;
	}
	else{
		Node *prev = find(index-1);
		cur = prev->next;
		prev->next = cur->next;
	}
	cur->next = NULL;
	delete cur;
	cur = NULL;
	size --;
}

/*
REMOVE DUPLICATE ENTRIES INPLACE
*/
template <typename dataType>
void List<dataType> :: removeDuplicates(){
	if(size < 2)
		return;
	
	Node* ind = head;
	Node* temp = NULL;
	for(Node* cur = head->next; cur != NULL; cur = cur->next){
		dataType value = cur -> data; 
		temp = head;
		for(temp = head; temp != ind -> next; temp = temp->next ){
			if(value ==  temp -> data)
				break;
		}
		if (temp == ind->next){
			ind = ind->next;
			ind->data = value;
		}
	}
	// remove remaining list 
	while(ind->next != NULL){
		size --;
		Node* temp = ind->next;
		ind -> next = temp -> next;
		temp -> next = NULL;
		delete temp;
		temp = NULL;
	}
}

/*
	REMOVE DUBLICATES USING A MAP FOR BOOKING
*/
// template <typename dataType>
// void List<dataType> :: removeDuplicates(){
// 	if(size < 2)
// 		return;
// 	map<dataType, bool> booking;
// 	int cur_index = 0;
// 	for(Node* cur = head; cur != NULL; cur = cur->next){
// 		dataType value = cur -> data;
// 		if(!booking[value]){
// 			remove(cur_index);
//			size--;
// 		}
// 		else{
// 			booking[value] = true;
// 		}
// 	}	
// }

/*
	REMOVE GIVEN NODE FROM THE LIST
*/
template <typename dataType>
void List<dataType>::removeNode(Node *node){
	if(size == 0){
		cout << "List is empty!!" << endl;
		return;
	}
	if(node -> next == NULL){ // if node is the tail
		remove(getLength()-1);
	}else{
		Node * next_node = node -> next;
	    node -> data = next_node -> data;
	    // remove next_node
	    node -> next = next_node -> next;
	    next_node -> next = NULL;
	    delete next_node;
	    next_node = NULL;
	}
    size--;
}

/*
	Two list should have same size
*/
template <typename dataType>
typename List<dataType>::Node* List<dataType> :: sumDigitsWithCarry(Node* num1,Node* num2){
    Node* newHead = new Node;
    Node* newCur = newHead;
    int carry = 0;
    for(Node * cur1 = num1, *cur2 = num2; cur1 != NULL && cur2 != NULL; cur1 = cur1 -> next, cur2 = cur2 -> next){
	    int val1 = cur1 -> data ;
	    int val2 = cur2 -> data;
	    int sum = val1 + val2;
	    int newDig = (sum % 10) + carry;

		newCur -> data = newDig;
		newCur -> next = new Node;
		newCur = newCur -> next;

		carry = (sum / 10) ? 1 : 0;
	}

	if(carry == 1){
		newCur -> data = 1;
		newCur -> next = NULL;
	}

	newCur = NULL;
	return newHead;
}


/*
Enter random int values in the range [0, max] to the begining
of the linked list
*/
template <typename dataType>
void List<dataType> :: randomIntFill(int item_num, int max){
	for(int i = 0; i < item_num; i ++){
		int next_val = rand() % max;
		insert(0,next_val);
	}
}

template <typename dataType>
dataType List<dataType>::retrieve(int index){
	if(index > size || index < 0){
		cout << "Wrong index value!!!" << endl;
		return;
	}
	Node *ptr = find(index);
	return ptr->data;
}

template <typename dataType>
typename List<dataType>::Node* List<dataType>::find(int index){
	Node *cur = head;
	for(int i = 0; i < index; i++){
		cur = cur->next;
	}
	return cur;
}

template <typename dataType>
void List<dataType>::printList(){
	for(Node *cur = head; cur != NULL; cur = cur->next){
		cout << cur->data << ' ';
	}
	cout << endl;
}

template <typename dataType>
bool List<dataType>::isEmpty(){
	return (size == 0) ? true : false;
}

template <typename dataType>
int List<dataType>::getLength(){
	return size;
}


int main(int argc, char **argv){
	List<int> list;
	list.insert(0,4);
	list.insert(1,5);
	list.insert(0,6);
	// list.insert(0,6);
	// list.insert(3,6);
	// list.insert(0,4);
	// list.insert(1,5);
	// list.insert(3,6);
	// list.insert(0,4);
	// list.insert(1,5);
	// list.insert(0,6);
	// list.insert(3,6);
	list.printList();
	cout <<  "List size : " << list.getLength() << endl;
	cout <<  "extracted item " << list.extract(0) << endl;

	list.printList();
	cout <<  "List size : " << list.getLength() << endl;

	// list.removeDuplicates();
	// list.printList();
	// cout <<  "List size : " << list.getLength() << endl;

	// list.removeNode(list.find(list.getLength()-1));
	// list.printList();

/* here we have segmentation fault */
	// List<int> list2(list.find(0));
	// list2.printList();

	//List<int> list2;
	// List<int> list2(list.find(0));
	// list2.printList();
	// List<int> list3(list2.sumDigitsWithCarry(list2.find(0), list.find(0)));
	// list3.printList();
	// cout <<  "List2 size : " << list2.getLength() << endl;
	// cout <<  "List3 size : " << list3.getLength() << endl;

	// list.randomIntFill(100,100);
	// list.printList();

	// list.remove(0);
	// list.remove(2);
	// list.printList();
	// cout <<  "List size : " << list.getLength() << endl;

	// List<int> list2(list);
	// cout <<  "List2 size : " << list2.getLength() << endl;
	return 0;
}