# Singly Linked List

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2FyirAyItiM8lVjHjHKzyI%2Fsingly%20liked%20list.png?alt=media&#x26;token=b7a2bb4f-07ca-4225-869e-bc919b5925b0" alt=""><figcaption></figcaption></figure>

{% code title="SinglyLinkedList.h" overflow="wrap" lineNumbers="true" %}
```cpp
#include <iostream>
#pragma once

using namespace std;

class Node {
public:
	int data;
	Node* next;
	explicit Node(const int d) : data(d), next(nullptr) {}
};

class SinglyLL {

public:
	Node* head ;
	int elements;
	SinglyLL(): elements(0) {
		head = nullptr;
	}	

	SinglyLL(const SinglyLL& list);
	
	SinglyLL& operator=(const SinglyLL& rhs);
	
	void insert(const int val);
	
	void insertAtHead(const int val);
	
	bool search(const int val) const;
	
	bool remove(const int val);
	
	bool removeAtHead(int& headData);

	void reverse();
	
	void sort();

	friend ostream& operator<< (ostream& os, const SinglyLL& list);

	~SinglyLL();
};
// Copy Constructor
SinglyLL :: SinglyLL(const SinglyLL& list) {
	Node* curHead = list.head;

	Node* cur = new Node(curHead  -> data);
	curHead = curHead -> next;
	head = cur;

	while (curHead != nullptr) {
		Node* temp = new Node(curHead -> data);
		cur -> next = temp;
		cur = temp; 
		curHead = curHead -> next;
	}
	elements = list.elements;
}

// Assignment Operator
SinglyLL& SinglyLL :: operator= (const SinglyLL& rhs) {
	if(this == &rhs) return *this;

	while (head != nullptr) {
		Node* temp = head;
		head = head->next;
		delete temp;
	}
	
	elements = rhs.elements;

	Node* curHead = rhs.head;
	Node* cur = new Node(curHead -> data);
	curHead = curHead -> next;
	head = cur;

	while (curHead != nullptr) {
		Node* temp = new Node(curHead->data);
		cur -> next = temp; 
		cur = temp;
		curHead = curHead -> next;
	}
	return *this;
}

// destructor
SinglyLL :: ~SinglyLL() {
	while (head != nullptr) {
		Node* temp = head;
		head = head->next;
		delete temp;
	}
}

// Insert At Any Position
void SinglyLL :: insert(const int val) {
	if(elements == 0) {
		Node* newNode = new Node(val);
		head = newNode;
		elements++;
		return;
	}
	
	Node* newNode = new Node(val);
	Node* cur = head;
	
	while (cur -> next != nullptr) {
		cur = cur -> next;
	}

	cur -> next = newNode;
	elements++;
}

// Insert At Head
void SinglyLL :: insertAtHead(const int val) {
	if(elements == 0) {
		Node* newNode = new Node(val);
		head = newNode;
		elements++;
		return;
	}
	
	Node* newNode = new Node(val);
	newNode -> next = head;
	head = newNode;
	elements++;
}

// Search Element
bool SinglyLL :: search(const int val) const {
	if(elements == 0) return false;
	
	Node* temp = head;
	while (temp != nullptr) {
		if(temp -> data == val) return true;
		temp = temp -> next;
	}
	return false;
}
// Remove At Any Position
bool SinglyLL :: remove(const int val) {
	if(elements == 0) return false;

	// if only 1 element present
	if(elements == 1) {
		delete head;
		head = nullptr;
		elements--;
		return true;
	}
	
	if(head -> data == val) {
		Node* cur = head;
		head = head->next;
		delete cur;
		elements--;
		return true;
	}

	Node* cur = head;
	Node* prev = nullptr;

	while (cur != nullptr) {
		if(cur -> data == val) {
			prev -> next = cur -> next;
			delete cur;
			elements--;
			return true;
		}
		prev = cur;
		cur = cur -> next;
	}
	return false;
}

// Remove Head
bool SinglyLL :: removeAtHead(int& headData) {
	if(elements == 0) return false;

	if(elements == 1) {
		headData = head -> data;
		delete head;
		elements--;
		return true;
	}

	Node* cur = head;
	headData = cur -> data;
	head = head -> next;
	delete cur;
	elements--;
	return true;
}

// Print data
ostream& operator<< (ostream& os, const SinglyLL& list) {
	Node* cur = list.head;

	while (cur != nullptr) {
		os << cur -> data <<" ";
		cur = cur -> next;
	} os << endl;
	os << "Head: " << list.head -> data << endl;
	os << "ELements: " << list.elements<< endl;
	return os;
}

// Reverse List
void SinglyLL :: reverse() {
	Node* prev = nullptr;
	Node* cur = head;
	Node* nx = head -> next;

	while (cur != nullptr) {
		cur -> next = prev;
		prev = cur;
		cur = nx;

		if(cur != nullptr) nx = nx -> next;
	}
	head = prev;
}

// Sort List
void SinglyLL :: sort() {
	if(elements == 0 || elements == 1) return;

	for (int i = 1; i < elements; i++) {
		
		Node* prev = nullptr;
		Node* cur = head;
		Node* nxt = head -> next;
		bool isSorted = true;

		for (int j = 0; j < elements - i; j++) {
		
			if(cur -> data > nxt -> data) {
				cur -> next = nxt -> next;
				nxt -> next = cur;
				
				isSorted = false;

				if(prev != nullptr){
					prev -> next = nxt;
				}
				else
					head = nxt;
				
				cur = nxt;
				nxt = nxt -> next;
			}
			prev = cur; 
			cur = cur -> next;
			nxt = nxt -> next;
		}
		if(isSorted) return;
	}
}
```
{% endcode %}

{% code title="main.cpp" overflow="wrap" lineNumbers="true" %}
```cpp
#include "SinglyLinkedList.h"

int main(){
	SinglyLL list;
	
	list.insert(5);
	list.insert(18);
	list.insertAtHead(13);
	list.insertAtHead(10);
	list.insertAtHead(19);
	list.insert(28);
	cout << list;
	
	SinglyLL list2(list), list3; // list2(list); copy constructor called
	
	list3.insert(8);
	list3 = list; // Assignment operator called
	
	cout << "Element is Present: " << boolalpha << list.search(20) << endl;
	
	if(list.remove(28)) 
		puts("Node Deleted!");
	else
		puts("Node -> Data is not present!");
	
	int x;
	cout << "Head Node Deleted: " << list.removeAtHead(x) << endl;
	cout << "Deleted Node Data: " << x << endl; 
	
	cout << "List: " << list;
	cout << "LL_2: " << list2;
	cout << "LL_3: " << list3; 


        // SinglyLL list;
	
	// list.insert(3);
	// list.insert(2);
	// list.insert(1);
	// list.insertAtHead(4);
	// list.insertAtHead(5);

	// cout << list << endl;

	// list.sort();
	// cout << "After Sort: "<< list << endl;

    // list.reverse();
	// cout << "After Reverse: "<< list;
}
```
{% endcode %}

{% code title="Using tail node" overflow="wrap" lineNumbers="true" %}
```cpp
#include<iostream>
using namespace std;

class Node{
public:
	int data;
	Node* next;
	
	explicit Node(const int d) : data(d), next(nullptr) {};	
};

class SinglyLL{
	Node* head;
	Node* tail;
	public:
		SinglyLL() : head(nullptr), tail(nullptr) {} ;
		
		SinglyLL(const SinglyLL& list);
		SinglyLL& operator= (const SinglyLL& list); 
		
		void insert(const int val);
		void insertAtHead(const int val);
		bool remove(const int val);
		bool removeHead(int& headData);
		bool search(const int val) const;
		friend ostream& operator << (ostream& os, const SinglyLL& list);
		
};
// copy constructor
SinglyLL :: SinglyLL(const SinglyLL& list) {
	Node* cur = list.head;
	Node* newNode = new Node(cur -> data);
	head = tail = newNode;
	
	cur = cur -> next;
	
	while(cur != nullptr) {
		Node* temp = new Node(cur -> data);
		tail -> next = temp;
		tail = temp;
		
		cur = cur->next;
	}
} 
//Assignment operator
SinglyLL& SinglyLL :: operator= (const SinglyLL& rhs) {
	if(this == &rhs) return *this;
	
	Node* curHead = head;
	while(curHead != nullptr) {
		head = head -> next;
		delete curHead;
		curHead = head;
	}
	head = tail = nullptr;
	
	Node* rhsHead = rhs.head;
	Node* newNode = new Node(rhsHead -> data);
	
	head = tail = newNode;
	
	rhsHead = rhsHead -> next;
	
	while(rhsHead != nullptr) {
		Node* temp = new Node(rhsHead -> data);
		tail -> next = temp;
		tail = temp;
		
		rhsHead = rhsHead -> next;
	}
	
	return *this;	
}

void SinglyLL :: insert(const int val) {
	Node* newNode = new Node(val);	
	if(head == nullptr) head = tail = newNode;
	
	else{
		tail -> next = newNode;
		tail = newNode;
	}
}

void SinglyLL :: insertAtHead(const int val) {
	Node* newNode = new Node(val);
	
	if(head == nullptr) head = tail = newNode;
	
	else {
		newNode -> next = head;
		head = newNode;
	}	
}

bool SinglyLL :: remove(int val) {
	if(head == nullptr) return false;

	if(head -> data == val) {
		removeHead(val);
		return true;
	}
	
	Node* cur = head;
	Node* prev = nullptr;
	
	while(cur -> next != nullptr) {
		if(cur -> data == val) {
			prev -> next = cur -> next;
			delete cur;
			return true;
		}
		prev = cur;
		cur = cur -> next;
	}
	// for deleting last node
	if(cur == tail) {
		tail = prev;
		tail -> next = nullptr;
		
		delete cur;
	}		
}

bool SinglyLL :: removeHead (int& headData) {
	if(head == nullptr) return false;
	
	headData = head -> data;
	if(head -> next == nullptr) {
		delete head;
		head = tail = nullptr;
	} 
	
	Node* cur = head;
	head = head -> next;
	delete cur;
	
	return true;
}

bool SinglyLL :: search (const int val) const {
	Node* cur = head;
	
	while(cur != nullptr) {
		if(cur -> data == val) return true;
		
		cur = cur -> next;
	}
	return false;
}

ostream& operator << (ostream& os, const SinglyLL& list) {
    Node* cur = list.head;
	while(cur != nullptr) {
		os << cur -> data << " ";
		cur = cur -> next;
	} os << endl;
	
	os << "Head: " << list.head -> data << endl;
	os << "Tail: " << list.tail -> data << endl;
	return os;
}

int main() {
	SinglyLL list, list3;
	
	list.insert(1);
	list.insertAtHead(2);
	list.insertAtHead(3);
	list.insert(4);
	list.insertAtHead(5);

	list3.insert(5); 
	list3 = list;
	
	SinglyLL list2(list);
	
	list.remove(5);
	list.remove(4);
	
	int temp;
	list.removeHead(temp);
	cout << temp << endl;
	
	cout << "List1: " << list  << endl;
	
	// list3 = list2 = list;

	cout << "List2: " << list2 << endl;	
	cout << "List3: " << list3 << endl; // line	181 
	return 0;
}
```
{% endcode %}
