Cpp Program for Doubly Linked List basics to algorithm part 4

C++ Program for Doubly Linked List

Basics to algorithm part 4

Doubly linked list as we have discussed earlier, in Linked List, Basics to algorithm part 1 is a data structure with link pointers pointing in both direction, previous as well as next. using doubly linked list we can achieve different algorithms which we will discuss later. Basically doubly linked list have an advantage of reverse traversal as well as forward traversal. 

We can make different methods or operations on doubly linked list like searching a node, making a node, inserting a node at required place, inserting a node at the beginning of the linked list, deleting the selected node, etc. 

Cpp code for doubly linked list :

	//
	// main.cpp
	// doublyLinkedList
	//
	// Created by Sarvesh Bhatnagar on 19/02/18.
	// Copyright © 2018 www.introtoalgo.com. All rights reserved.
	//
	#include <iostream>
	using namespace std;
	struct doublyLinkedList{
	int id;
	struct doublyLinkedList *next;
	struct doublyLinkedList *prev;
	};
	struct doublyLinkedList *first,*last,*temp,*a,*b;
	void displayAscending();
	void deleteNode(int x);
	void displayDescending();
	void searchDoublyLinkedList(int x);
	void makeDoublyLinkedList();
	void insertAtStart();
	void insertAt(int x);
	int main() {
	first = last = NULL;
	makeDoublyLinkedList();
	makeDoublyLinkedList();
	makeDoublyLinkedList();
	insertAtStart();
	insertAt(7);
	displayAscending();
	displayDescending();
	searchDoublyLinkedList(5);
	deleteNode(7);
	return 0;
	}
	void makeDoublyLinkedList(){
	temp = new doublyLinkedList();
	temp->prev = NULL;
	temp->next = NULL;
	if (first == NULL) {
	first = temp;
	}
	else{
	temp->prev = last;
	last->next = temp;
	}
	last = temp;
	cout<<"Enter id"<<endl;
	cin>>temp->id;
	}
	void displayAscending(){
	temp = first;
	while (temp!= NULL) {
	cout<<temp->id<<endl;
	temp = temp->next;
	}
	}
	void displayDescending(){
	temp = last;
	while (temp != NULL) {
	cout<<temp->id<<endl;
	temp = temp->prev;
	}
	}
	void searchDoublyLinkedList(int x){
	temp = first;
	bool isDataFound = false;
	while (temp != NULL) {
	if (temp->id == x) {
	isDataFound = true;
	break;
	}
	temp = temp->next;
	}
	if (isDataFound) {
	cout<<"Data Found"<<endl;
	}
	else{
	cout<<"Data Not Found"<<endl;
	}
	}
	void insertAtStart(){
	temp = new doublyLinkedList();
	if (first == NULL) {
	makeDoublyLinkedList();
	}
	else{
	first->prev = temp;
	temp->next = first;
	temp->prev = NULL;
	cout<<"Enter id"<<endl;
	cin>>temp->id;
	first = temp;
	}
	}
	void insertAt(int x){
	a = b = first;
	for (int i = 0; i<x; i++) {
	a = b;
	b = b->next;
	if (b == NULL) {
	break;
	}
	}
	if (a == NULL) {
	makeDoublyLinkedList();
	}
	else{
	temp = new doublyLinkedList();
	temp->next = NULL;
	temp->prev = NULL;
	cout<<"Enter id "<<endl;
	cin>>temp->id;
	a->next = temp;
	temp->prev = a;
	if (b != NULL) {
	b->prev = temp;
	temp->next = b;
	}
	else{
	last = temp;
	}
	}
	}
	void deleteNode(int x){
	a = b= first;
	for (int i = 0; i<x; i++) {
	a = b;
	b = b->next;
	if (b == NULL) {
	if (i == x-1) {
	}
	else{
	a = NULL;
	}
	break;
	}
	}
	if (a == NULL) {
	cout<<"NODE Does not exist"<<endl;
	}
	else{
	temp = a-> prev;
	temp->next = b;
	if (b != NULL) {
	b->prev = temp;
	}
	else{
	temp = last;
	}
	cout<<"NODE DELETED ID is "<<a->id<<endl;
	free(a);
	}
	}

view raw doublyLinkedList.cpp hosted with ❤ by GitHub

Written By, Sarvesh Bhatnagar

Download Learn Algorithms free