Doubly Linked List

What is doubly linked list?

“This is the linked list whose nodes have both previous and next pointers, but next field of the last node and previous field of the first node are set to NULL.”

Why next and previous fields of doubly linked list node are NULL?

• If we don’t let the next field of the last node to by NULL, it will lead to an inappropriate area of the memory, which is unacceptable and will give error.
• Same is the case of first node having previous field not NULL, when it’ll try to point to the previous node (which doesn’t exist in this case), this’ll result error caused by inappropriate access.

Why do we need doubly linked list?

As the definition highlights its property of having two pointers, one towards previous and the other towards next node. The problem in singly linked list is that we can just move forward, but can’t move back, as it has only next pointer.

So, doubly linked list fills this gap and provide ease for accessing nodes by going back and forth.

Following image represents the doubly linked list more vividly;

The complexity of adding and removing nodes increases due to the increase in the number of pointers (2, previous and next) in a doubly linked list.

NOTE: don’t get confused of the term “node”, it’s the object constructed by class “Node” (factory) that take cares of setting and getting value, previous address, and next address of the node (product).

class Node {
	private:
	int object;
	Node* nextNode;
	Node* prevNode;

	public:
	int get() { return object; }
	void set(int object) { this->object = object; }
	
	Node* getNext() { return nextNode; }
	void setNext(Node* nextNode) { this->nextNode = nextNode; }
	
	Node* getPrev() { return prevNode; }
	void setPrev(Node* prevNode) { this->prevNode = prevNode; }  
}

Insertion of node in doubly linked list

Step 1: We assign the address of the node with value 8 to the “nextNode” of the “newNode”.

newNode->setNext(current->getNext());

Step 2: Point the “prevNode” of the “newNode” to the node with value 6.

newNode->setPrev(current);

Step 3: Set the previous node with value 8 to point to the newNode.

(current->getNext())->setPrev(newNode);

Step 4 (last): The nextNode of the node with value 6 is pointing to the newNode i.e. the node with value 9. Point the current to the newNode and add one to the size of the list.

current->setNext(newNode);
current = newNode;
size++;

REFERENCE: CS301 Handouts (page 37 to 40)