Table of Contents

Vocabulary

Doubly Linked Lists Head Pointer Tail Pointer Data Next Pointer Previous Pointer Append Prepend Insert Remove

What Are Doubly Linked Lists?

<aside> 💡 Doubly Linked Lists are another type of data structure similar to linked lists that consist of nodes that are “linked” by pointers. Similar to a linked list. doubly linked lists contain a head, tail, and next pointer. However, they also contain a previous pointer that points to a previous node.

Just like linked lists, the last node’s next pointer will point to NULL to indicate the end of the list (since there are no nodes to refer to).

</aside>

Creating A Doubly Linked List

class Node {
	public:
		int data;
		Node* next;
}

class DoublyLinkedList {
	Node* head;
	Node* tail;
	Node* prev;
}

Doubly Linked List Operations

Appending

<aside> 💡 Appending in a doubly linked list (LL) requires the following:

1. Changing where the last node’s next pointer points to by having it point to the newly added node.
2. Having the new node’s previous pointer point to the old last node.
3. Changing where the tail points to by having it point to the new last node.

</aside>

append(Doubly LinkedList L, Node newNode) {
	if (L->head == NULL) {
		L->head = newNode;
		L->tail = newNode;
	} else {
		L->tail->next = newNode;
		newNode->prev = L->tail;
		L->tail = newNode;
	}
}

Prepending

<aside> 💡 Prepending an element to a doubly LL involves adding a node to the front of the list. This can be done by setting the head’s previous pointer to point to the new node. Then, setting the new node’s next pointer to point to the head of the doubly LL. And finally, setting the head equal to the new node.

</aside>

prepend(Doubly LinkedList L, Node newNode) {
		if (L->head == NULL) {
			L->head = newNode;
			L->tail = newNode;
		} else {
			L->head->prev = newNode;
			newNode->next = L->head;
			L->head = newNode;
		}
}

Inserting