Singly Linked List Program in C++ using class

Leave a Comment / c++, Linked List

In this article, we will be discussing Singly Linked List Program in C++ using class.

A Singly Linked List is unidirectional. Each node stores the reference to the next node. Since we are not storing the address of the previous node, we cannot traverse back, making it unidirectional.

Singly Linked List Program in C++ using class

The head pointer points to the first node of a Linked List.

We implement linked list using 2 classes:

  1. node class
  2. Linked List class

node class

class node{
	public:
		int v;
		node *next;
		node(){
			next = NULL;
		}
};

node class represents each node of the Linked List. It contains 2 public variables – v and next. v stores the data and next stores the address to the next node.

LinkedList class

class LinkedList{
	node *head;
	public:
		/* Member functions to perform
                   different operations on Linked List */
                void insert_at_beignning(int v);
                void insert_at_end(int v);
                void insert_at_given_position(int v, int p);
                void delete_at_beignning();
                void delete_at_end();
                void delete_at_given_position(int p);
                void print();
};

LinkedList class contains a pointer head that points to the first node of the linked list and public member functions which performs various operations on the Linked List.

Singly Linked List Opeartions

We are going to code and discuss the following operations on the linked list.

  1. Insert at Beginning.
  2. Inset at End.
  3. Insert in Mid.
  4. Delete at Beginning.
  5. Delete at End.
  6. Delete in Mid.
  7. Print Linked List

Insert at Beignning

void insert_at_beginning(int v){
	node *temp = new node();
	temp->v = v;
	temp->next = head;
	head = temp;
}

The function accepts 1 argument that is the data we want to insert.

  1. First, initialize a new node temp with value v.
  2. Set temp->next to the address of the first node of the linked list, that is head.
  3. Make temp the new head.

Insert at End

void insert_at_end(int v){
	node *temp = new node();
	temp->v = v;
	if (head == NULL){
		// if linked list is empty, that is head == NULL
		// Make temp the new head
		head = temp;
	}
	else{
		// if linked list is not empty
		// go to the last node of the linked list
		node *ptr = head;
		// the loop sets ptr to last node of the linked list
		while (ptr->next != NULL){
			ptr = ptr->next;
		}
		// ptr now points to the last node
		// store temp address in the next of ptr  
		ptr->next = temp;
	}
}
  1. Initialize a new node temp with value v.
  2. If the linked list is empty, simply make temp the new head.
  3. If the linked list is not empty, move to the last node of the linked list and set the next of the last node to temp.

Insert in Mid

void insert_at_given_position(int v, int p){
	node *temp = new node();
	temp->v = v;
	if (p == 0){
		// if p==0 then insert temp at beginning
		temp->next = head;
		head = temp;
	}
	else{
		node *ptr = head;
		// the loop sets ptr to (p-1)th node
		while(p>1) {
			ptr = ptr->next;
			--p;
		}
		// ptr now points to (p-1)th node
		// insert temp between (p-1)th and pth node
		temp->next = ptr->next;
		ptr->next = temp;
	}
}

The function accepts 2 arguments. v is the data we need to insert and p is the position where we want to insert v.

  1. Initialize a new node temp with value v.
  2. If p == 0, then simply insert temp at beginning of the linked list.
  3. If p > 0, move to the (p-1)th node and then insert temp between (p-1)th and pth node.

Delete at Beginning

void delete_at_beginning(){
	if (head == NULL){
		cout<<"List is Empty"<<endl;
	}
	else{
		cout<<"Element Deleted: "<<head->v<<endl;
		// if linked list is not empty
		// store address of first node in temp
		node *temp = head;
		// set second node as the new head of the linked list
		head = head->next;
		// free the old head
		delete(temp);
	}
}
  1. If the linked list is empty, do nothing.
  2. Otherwise, store the address of the first node of the linked list in temp. Then make the 2nd node of the linked list, that is head->next the new head. After that, free the old head ( that is temp ).

Delete at End

void delete_at_end(){
	if (head == NULL){
		cout<<"List is Empty"<<endl;
	}
	else if (head->next == NULL){
		// if there's only 1 element in the linked list
		// free head and set it to NULL
		cout<<"Element Deleted: "<<head->v<<endl;
		delete(head);
		head = NULL;
	}
	else{
		// if there's more than 1 element in the linked
		// traverse to 2nd last element of the linked list
		node *temp = head;
		while (temp->next->next != NULL) {
			temp = temp->next;
		}
		// temp now points to the 2nd last element of the linked list
		cout<<"Element Deleted: "<<temp->next->v<<endl;
		// delete last node
		delete(temp->next);
		// set the next of 2nd last element to NULL
		temp->next = NULL;
	}					

}
  1. If the list is empty, do nothing.
  2. If the linked list contains only 1 node, simply free the head and set head to NULL.
  3. Otherwise, if the linked list contains more than 1 element, move to the 2nd last element of the linked list. Free the memory of the last node and set the next of 2nd last element to NULL.

Delete in Mid

void delete_at_given_position(int p){
	if (head == NULL){
		// if list is empty do nothing
		cout<<"List is Empty"<<endl;
	}
	else{
		node *temp, *ptr;
		if (p == 0) {
			// if p==0, perform delete at beginning
			cout<<"Element Deleted: "<<head->v<<endl;
			ptr = head;
			head = head->next;
			delete(ptr);
		}
		else{
			// if p > 0
			// set ptr to pth node and temp to (p-1)th node
			temp = ptr = head;
			while(p>0){
				--p;
				temp = ptr;
				ptr = ptr->next;
			}
			cout<<"Element Deleted: "<<ptr->v<<endl;
			// set next of (p-1)th node to next of pth node
			temp->next = ptr->next;
			// free pth node
			free(ptr);
		}
	}

}

The function accepts 1 argument p, that is the position of node we want to delete.

  1. If the list is empty, do nothing.
  2. If p == 0, simply delete the first node.
  3. If p > 0,
    1. First set ptr to pth node and temp to (p-1)th node of the linked list.
    2. Set temp->next to ptr->next.
    3. Delete ptr.

Print Linked List

void print(){
	if (head == NULL){
		cout<<"List is empty"<<endl;
	}
	else{
		node *temp = head;
		cout<<"Linekd List: ";
		while (temp != NULL){
			cout<<temp->v<<"->";
			temp = temp->next;
		}
		cout<<"NULL"<<endl;
	}
}

Simply traverse though all the nodes from head and print the data.

Program of Singly Linked List in C++ using class

#include<iostream>
#include<vector>
using namespace std;

class node{
	public:
		int v;
		node *next;
		node(){
			next = NULL;
		}
};

class LinkedList{
	node *head;
	public:
		
		LinkedList(){
			head = NULL;
		}
		
		void insert_at_beginning(int v){
			node *temp = new node();
			temp->v = v;
			temp->next = head;
			head = temp;
		}
		
		void insert_at_end(int v){
			node *temp = new node();
			temp->v = v;
			if (head == NULL){
				// if linked list is empty
				// make temp the new head
				head = temp;
			}
			else{
				// if linked list is not empty
				// go to the last node of the linked list
				node *ptr = head;
				// the loop sets ptr to last node of the linked list
				while (ptr->next != NULL){
					ptr = ptr->next;
				}
				// ptr now points to the last node of the linked list
				// store temp in the next of ptr  
				ptr->next = temp;
			}
		}
		
		void insert_at_given_position(int v, int p){
			node *temp = new node();
			temp->v = v;
			if (p == 0){
				// if p==0 then insert temp at beginning
				temp->next = head;
				head = temp;
			}
			else{
				node *ptr = head;
				// the loop sets ptr to (p-1)th node
				while(p>1) {
					ptr = ptr->next;
					--p;
				}
				// ptr now points to (p-1)th node
				// insert temp between (p-1)th and pth node
				temp->next = ptr->next;
				ptr->next = temp;
			}
		}
		
		void delete_at_beginning(){
			if (head == NULL){
				cout<<"List is Empty"<<endl;
			}
			else{
				cout<<"Element Deleted: "<<head->v<<endl;
				// if linked list is not empty
				// store address of first node of the linked list in temp
				node *temp = head;
				// set second node as the new head of the linked list
				head = head->next;
				// free the old head
				delete(temp);
			}
		}
		
		void delete_at_end(){
			if (head == NULL){
				cout<<"List is Empty"<<endl;
			}
			else if (head->next == NULL){
				// if there's only 1 node in the linked list
				// free head and set it to NULL
				cout<<"Element Deleted: "<<head->v<<endl;
				delete(head);
				head = NULL;
			}
			else{
				// if there's more than 1 node in the linked
				// traverse to 2nd last node of the linked list
				node *temp = head;
				// the loop sets temp to 2nd last node of the linked list
				while (temp->next->next != NULL) {
					temp = temp->next;
				}
				// temp now points to the 2nd last node of the linked list
				cout<<"Element Deleted: "<<temp->next->v<<endl;
				// delete last node
				delete(temp->next);
				// set the next of 2nd last node to NULL
				temp->next = NULL;
			}					
		
		}
		
		void delete_at_given_position(int p){
			if (head == NULL){
				// if list is empty do nothing
				cout<<"List is Empty"<<endl;
			}
			else{
				node *temp, *ptr;
				if (p == 0) {
					// if p==0, perform delete at beginning
					cout<<"Element Deleted: "<<head->v<<endl;
					ptr = head;
					head = head->next;
					delete(ptr);
				}
				else{
					// if p > 0
					// set ptr to pth node and temp to (p-1)th node
					temp = ptr = head;
					while(p>0){
						--p;
						temp = ptr;
						ptr = ptr->next;
					}
					cout<<"Element Deleted: "<<ptr->v<<endl;
					// set next of (p-1)th node to next of pth node
					temp->next = ptr->next;
					// free pth node
					free(ptr);
				}
			}
		
		}
		
		void print(){
			if (head == NULL){
				cout<<"List is empty"<<endl;
			}
			else{
				node *temp = head;
				cout<<"Linked List: ";
				while (temp != NULL){
					cout<<temp->v<<"->";
					temp = temp->next;
				}
				cout<<"NULL"<<endl;
			}
		}	
			
};


int main() {
	
	printf("1 to Insert at the beginning");
	printf("\n2 to Insert at the end");
	printf("\n3 to Insert at mid");
	printf("\n4 to Delete from beginning");
	printf("\n5 to Delete from the end");
	printf("\n6 to Delete from mid");
	printf("\n7 to Display");
	printf("\n0 to Exit");
	
	int choice,v,p;
	LinkedList ll;
	do {
		cout<<"\nEnter Your Choice: ";
		cin>>choice;
		switch (choice)
		{
			case 1:
				cout<<"Enter Element: ";
				cin>>v;
				ll.insert_at_beginning(v);
				break;
				
			case 2:
				cout<<"Enter Element: ";
				cin>>v;
				ll.insert_at_end(v);
				break;
				
			case 3:
				cout<<"Enter Element: ";
				cin>>v;
				cout<<"Enter Position ( zero-indexed ): ";
				cin>>p;
				ll.insert_at_given_position(v,p);
				break;
				
			case 4:
				ll.delete_at_beginning();
				break;
				
			case 5:
				ll.delete_at_end();
				break;
				
			case 6:
				cout<<"Enter Position ( zero-indexed ): ";
				cin>>p;
				ll.delete_at_given_position(p);
				break;
				
			case 7:
				ll.print();
				break;
				
		}
	} while (choice != 0);
	
}
1 to Insert at the beginning
2 to Insert at the end
3 to Insert at mid
4 to Delete from beginning
5 to Delete from the end
6 to Delete from mid
7 to Display
0 to Exit
Enter Your Choice: 1
Enter Element: 10

Enter Your Choice: 1
Enter Element: 9

Enter Your Choice: 2
Enter Element: 11

Enter Your Choice: 7
Linked List: 9->10->11->NULL

Enter Your Choice: 3
Enter Element: 20
Enter Position ( zero-indexed ): 2

Enter Your Choice: 7
Linked List: 9->10->20->11->NULL

Enter Your Choice: 3
Enter Element: 30
Enter Position ( zero-indexed ): 1

Enter Your Choice: 7
Linked List: 9->30->10->20->11->NULL

Enter Your Choice: 2
Enter Element: 40

Enter Your Choice: 7
Linked List: 9->30->10->20->11->40->NULL

Enter Your Choice: 4
Element Deleted: 9

Enter Your Choice: 4
Element Deleted: 30

Enter Your Choice: 5
Element Deleted: 40

Enter Your Choice: 7
Linked List: 10->20->11->NULL

Enter Your Choice: 6
Enter Position ( zero-indexed ): 1
Element Deleted: 20

Enter Your Choice: 7
Linked List: 10->11->NULL

Enter Your Choice: 0

References

Singly Linked List

Leave a Comment

Your email address will not be published. Required fields are marked *