<jupyter_start><jupyter_text>Doubly Linked ListDoubly Linked List is just an extension of singly linked list. If you know how singly linked list works, you already know 90% of doubly linked list.So the difference between doubly linked list and a singly linked list is the way doubly linked list is defined. Doubly Linked List(DLL for short) has an extra node adress to point to the node previous to it. Sometime that previous node is present and sometimes there are no nodes infront of it. However, the other address denotes the address of the node next to it,similar to that of singly linked list. Let us see the implementation of the different functions to get a better feel of the implmentation of doubly linked list.<jupyter_code>%%writefile test.cpp

#include <iostream>
using namespace std;

/*The struct node has an extra node
to point to its previous node. A node
of DLL looks like follows: NULL<-10 ->NULL .
The first arrow represents previous node address,
the second array represent the next node address.*/

struct node {
	int data;
	node* next;
	node* prev;
};

/*This function is similar to that
of addValue of singly linked list.
The only difference is how the previous
node works*/

void addValue(node*& a, int data) {

	if (a == NULL) {
		a = new node;
		a->data = data;
		a->next = NULL;

		/*So when a new node is initialized
		and populated with data, its next
		address is NULL and its previous
		address is also NULL. It is something
		like the following: NULL<-12->NULL */

		a->prev = NULL;
	}

	else {
		node* current = a;
		while (current->next != NULL) {
			current = current->next;
		}

		/*The while loop above allows the current
		node to reach the node in the linked list,
		whose next node address is NULL. It is something
		like the following :

		NULL <-2-> <-4-> <-6-> <-8-> <-10-> NULL
		       0     1     2     3     4
		                             current

		If current node reaches such a node, a new
		node such as b is allocated and populated.*/

		node* b = new node;
		b->data = data;
		b->next = NULL;

		/* The next two lines works as such.
		The previous of node b is the current node,
		and the next node to the current node is
		the b node. The next node to the b node is NULL.

		NULL <-2-> <-4-> <-6-> <-8-> <-10-> <-b-> NULL
		       0     1     2     3     4
		                             current
		*/

		b->prev = current;
		current->next = b;
	}
}

/*This works similar to the insert value subroutine for
singly linked list.*/

void insertValue(node*& a, int data, int index) {
	if (index == 0) {
		node* b = new node;
		b->data = data;

		/*The following line helps to deal
		with null list and already filled list
		at the same time. If a null to be a null
		list then it  is not a problem, it is also
		not a problem if a is not a null list like
		the following:

		NULL <-b-> NULL ( if a is NULL)

		NULL <-b-> <-10-> <-20-> <-30-> NULL (if a is not null)

		*/

		b->next = a;
		b->prev = NULL;

		/*This is where we need an additional check if a
		is null or not. If a is NULL it can not have
		a previous node, since a is NULL. Consider this
		following example: NULL <-b-> NULL, since a is
		null ,there is no previous null. If a is not
		null, it should have a previous node. That
		previous node points to b*/

		if (a != NULL) a->prev = b;

		/*Node b becomes the head of the list*/

		a = b;
	}

	/*If we are looking for any index another than
	0 , this portion clicks on*/

	else {

		node* current = a;

		/*So it is similar to that of the last time

		NULL <-2-> <-4-> <-6-> <-8-> <-10-> NULL
		       0     1     2     3      4
		          current
		If we are looking to insert an element in index
		2, the current node will stop at index 1. The
		for loop below will illustrate that.
		*/

		for (int i = 0; i < index - 1; ++i) {
			current = current->next;
		}

		/*After reaching index 1, a new node c is being
		formed like so:*/

		node* c = new node;
		c->data = data;

		/*
		            |--c----|
		            |       |
		            v       v
		NULL <-2-> <-4-> <-6-> <-8-> <-10-> NULL
		       0     1     2     3      4
		          current
		*/

		c->next = current->next;
		c->prev = current;

		/*Coming back to the above example if the
		node current->next is not NULL, then the
		previous node of current's next node should
		point to the node c, something like the
		following:
		            |-----c-|
		            |     ^ |
		            v     | v
		NULL <-2-> <-4->  6-> <-8-> <-10-> NULL
		       0     1     2     3      4
		          current

		*/

		if (current->next != NULL) {
			current->next->prev = c;
		}

		/*And lastly this will happen when current's
		next node is going to be c:

		            |----c--|
		            | ^   ^ |
		            v |   | v
		 NULL <-2-> <-4  6-> <-8-> <-10-> NULL
		       0     1     2     3      4
		          current

		 which is ultimately this:

		 NULL <-2-> <-4-> <-c-> <-6-> <-8-> <-10-> NULL
		*/

		current->next = c;

	}
}

/*The last function is about removing a value
from the list. Pay close attention to how the
pointers work. The operations are similar to the
ones you have already seen.*/

void removeValue(node*& a, int value) {

	if (a == NULL) {
		return;
	}

	/*If you find the value you are looking for,
	move on to the next one, delete the one
	which contains the value you were looking for*/

	if (a->data == value) {
		node* x = a;
		a = a->next;

		/*And the value you will be moving to,
		if it is not null, set the previous of
		that value to NULL. This happens if
		a contains more than one node*/

		if (a != NULL) {a->prev = NULL;}

		//Reclaim the memory of x
		delete x;
	}


	/*If the value is not found in the first node,
	then try to find the value till the end is reached.*/

	else {
		node* current = a;

		/*The following linked list example will help to
		 visualize the working of the code.

		 NULL <-2-> <-4-> <-6-> <-8-> <-10-> NULL
		        0     1     2     3     4
		     current
		 Lets say we want to delete 4, then we have to check
		 whether a: Node next to current is not NULL and b: Node
		 next to current has a value of 4.

		 */

		while (current->next != NULL) {
			if (current->next->data == value) {
				node* x = current->next;

				/*
				So, to continue from the last comment,

				NULL <-2-> <-4-> <-6-> <-8-> <-10-> NULL
				       0     1     2     3     4
				    current
				if you want to remove 4 just skip over 4
				and connect 2 with 4 neighbor, something like
				the following:

				NULL <-2-> <-6-> <-8-> <-10-> NULL
				      0      1     2     3
				    current

				There is a chance that you might encounter something
				like the following linked list scenario:


				NULL <-2-> <-4->  NULL
				       0     1
				     current

				where current node's next next node is NULL, it is still
				not a problem , since it will result something like this:

				NULL <-2-> NULL

				after removing the node with value 4.
				*/

				current->next = current->next->next;

				/*Now, if it so happens that current->next is
				not NULL "AFTER" the update, something like
				the following:

				 NULL <-2-> <-6-> <-8-> <-10-> NULL
				      0      1     2     3
				    current

				which is the linked list after removing the node
				with value 4, you can say that the previous
				node of current's next node points to the current
				node.
				On the other hand, if this happens after removing
				node with value 4:

				NULL <-2-> NULL
				       0
				    current

				then it is safe to say that there is no previous
				node of current's next node, since current's
				next node is NULL.

				*/

				if (current->next != NULL) {
					current->next->prev = current;
				}
				delete x;
			}

			/*If you don't find any clue of the data
			that you are looking march along to look
			for more*/

			else {
				current = current->next;
			}
		}
	}
}

/*Display prints the linked list from  left to
right first following the next pointer. After
that it turns  around and prints from right to left*/

void display(node* h) {

	cout << "Printing the list" << endl;

	if (h == NULL) {
		cout << "Empty List" << endl;
		return;
	}
	node* current = h;
	while (current->next != NULL) {
		cout << current->data << " ";
		current = current->next;
	}

	cout << current->data << endl;

	while (current->prev != NULL) {
		cout << current->data << " ";
		current = current->prev;
	}
	cout << current->data << endl;
}

int main() {
	node* h = NULL;

	addValue(h, 4);
	addValue(h, 4);
	addValue(h, 34);
	addValue(h, 45);
	addValue(h, 425);
	addValue(h, 45);
	addValue(h, 145);

	display(h);

	//Insert value at a given index of the list
	/*
	node* g = NULL;
	insertValue(g, 13, 0);
	insertValue(g, 90, 1);
	insertValue(g, 12, 2);
	insertValue(g, 90, 3);
	display(g);
	*/

	//Remove the elements from the list

	cout << "\nAfter removal of values: " << endl;
	removeValue(h, 45);
	removeValue(h, 4);
	display(h);
	return 0;
}
%%script bash
g++ test.cpp -o test 
./test<jupyter_output>Printing the list
4 4 34 45 425 45 145
145 45 425 45 34 4 4

After removal of values: 
Printing the list
4 34 425 145
145 425 34 4
{'fraction_non_alphanumeric': 0.10599078341013825, 'fraction_numerical': 0.024467851656791748, 'mean_word_length': 2.0710916442048517, 'pattern_counts': {'":': 0, '<': 99, '<?xml version=': 0, '>': 117, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '313305', 'license': 'CC0-1.0', 'n_tokens_mistral': 3395, 'n_tokens_neox': 2777, 'n_words': 1361, 'path': 'cse203/code/CSE203Lecture7.ipynb', 'repo_name': 'mohammadmotiurrahman/mohammadmotiurrahman.github.io', 'size': '9114'}