How many null pointers exists in a doubly linked list

The singly linked list allows for direct access from a list node only to the next node in the list. A doubly linked list allows convenient access from a list node to the next node and also to the preceding node on the list. The doubly linked list node accomplishes this in the obvious way by storing two pointers: one to the node following it (as in the singly linked list), and a second pointer to the node preceding it.

Figure 9.6.1: A doubly linked list.

The most common reason to use a doubly linked list is because it is easier to implement than a singly linked list. While the code for the doubly linked implementation is a little longer than for the singly linked version, it tends to be a bit more “obvious” in its intention, and so easier to implement and debug. Whether a list implementation is doubly or singly linked should be hidden from the List class user.

Like our singly linked list implementation, the doubly linked list implementation makes use of a header node. We also add a tailer node to the end of the list. The tailer is similar to the header, in that it is a node that contains no value, and it always exists. When the doubly linked list is initialized, the header and tailer nodes are created. Data member head points to the header node, and tail points to the tailer node. The purpose of these nodes is to simplify the insert, append, and remove methods by eliminating all need for special-case code when the list is empty, or when we insert at the head or tail of the list.

In our implementation, curr will point to the current position (or to the trailer node if the current position is at the end of the list).

Here is the complete implementation for a Link class to be used with doubly linked lists. This code is a little longer than that for the singly linked list node implementation since the doubly linked list nodes have an extra data member.

The following slideshows illustrate the insert and append doubly linked list methods. The class declaration and the remaining member functions for the doubly linked list class are nearly identical to the singly linked list version. While the code for these methods might be a little longer than their singly linked list counterparts (since there is an extra pointer in each node to deal with), they tend to be easier to understand.

Settings

Resubmit

Settings

Resubmit

Settings

Resubmit

The only disadvantage of the doubly linked list as compared to the singly linked list is the additional space used. The doubly linked list requires two pointers per node, and so in the implementation presented it requires twice as much overhead as the singly linked list.

Todo

Need exercises for inserting to and deleting from doubly linked lists.

There is a space-saving technique that can be employed to eliminate the additional space requirement, though it will complicate the implementation and be somewhat slower. Thus, this is an example of a space/time tradeoff. It is based on observing that, if we store the sum of two values, then we can get either value back by subtracting the other. That is, if we store \(a + b\) in variable \(c\), then \(b = c - a\) and \(a = c - b\). Of course, to recover one of the values out of the stored summation, the other value must be supplied. A pointer to the first node in the list, along with the value of one of its two link fields, will allow access to all of the remaining nodes of the list in order. This is because the pointer to the node must be the same as the value of the following node’s prev pointer, as well as the previous node’s next pointer. It is possible to move down the list breaking apart the summed link fields as though you were opening a zipper.

The principle behind this technique is worth remembering, as it has many applications. The following code fragment will swap the contents of two variables without using a temporary variable (at the cost of three arithmetic operations).

a = a + b; b = a - b; // Now b contains original value of a a = a - b; // Now a contains original value of b

a = a + b; b = a - b; // Now b contains original value of a a = a - b; // Now a contains original value of b

A similar effect can be had by using the exclusive-or operator. This fact is widely used in computer graphics. A region of the computer screen can be highlighted by XORing the outline of a box around it. XORing the box outline a second time restores the original contents of the screen.

// A complete working Java program to demonstrate all

// Class for Doubly Linked List

public class DLL {

Node head; // head of list

/* Doubly Linked list Node*/

class Node {

int data;

Node prev;

Node next;

// Constructor to create a new node

// next and prev is by default initialized as null

Node[int d] { data = d; }

}

// Adding a node at the front of the list

public void push[int new_data]

{

/* 1. allocate node

* 2. put in the data */

Node new_Node = new Node[new_data];

/* 3. Make next of new node as head and previous as NULL */

new_Node.next = head;

new_Node.prev = null;

/* 4. change prev of head node to new node */

if [head != null]

head.prev = new_Node;

/* 5. move the head to point to the new node */

head = new_Node;

}

// Add a node before the given node

public void InsertBefore[Node next_node, int new_data]

{

/*Check if the given nx_node is NULL*/

if[next_node == null]

{

System.out.println["The given next node can not be NULL"];

return;

}

//Allocate node, put in the data

Node new_node = new Node[new_data];

//Making prev of new node as prev of next node

new_node.prev = next_node.prev;

//Making prev of next node as new node

next_node.prev = new_node;

//Making next of new node as next node

new_node.next = next_node;

//Check if new node is added as head

if[new_node.prev != null]

new_node.prev.next = new_node;

else

head = new_node;

}

/* Given a node as prev_node, insert

a new node after the given node */

public void InsertAfter[Node prev_Node, int new_data]

{

/*1. check if the given prev_node is NULL */

if [prev_Node == null] {

System.out.println["The given previous node cannot be NULL "];

return;

}

/* 2. allocate node

* 3. put in the data */

Node new_node = new Node[new_data];

/* 4. Make next of new node as next of prev_node */

new_node.next = prev_Node.next;

/* 5. Make the next of prev_node as new_node */

prev_Node.next = new_node;

/* 6. Make prev_node as previous of new_node */

new_node.prev = prev_Node;

/* 7. Change previous of new_node's next node */

if [new_node.next != null]

new_node.next.prev = new_node;

}

// Add a node at the end of the list

void append[int new_data]

{

/* 1. allocate node

* 2. put in the data */

Node new_node = new Node[new_data];

Node last = head; /* used in step 5*/

/* 3. This new node is going to be the last node, so

* make next of it as NULL*/

new_node.next = null;

/* 4. If the Linked List is empty, then make the new

* node as head */

if [head == null] {

new_node.prev = null;

head = new_node;

return;

}

/* 5. Else traverse till the last node */

while [last.next != null]

last = last.next;

/* 6. Change the next of last node */

last.next = new_node;

/* 7. Make last node as previous of new node */

new_node.prev = last;

}

// This function prints contents of

// linked list starting from the given node

public void printlist[Node node]

{

Node last = null;

System.out.println["Traversal in forward Direction"];

while [node != null] {

System.out.print[node.data + " "];

last = node;

node = node.next;

}

System.out.println[];

System.out.println["Traversal in reverse direction"];

while [last != null] {

System.out.print[last.data + " "];

last = last.prev;

}

}

/* Driver program to test above functions*/

public static void main[String[] args]

{

/* Start with the empty list */

DLL dll = new DLL[];

// Insert 6. So linked list becomes 6->NULL

dll.append[6];

// Insert 7 at the beginning. So

// linked list becomes 7->6->NULL

dll.push[7];

// Insert 1 at the beginning. So

// linked list becomes 1->7->6->NULL

dll.push[1];

// Insert 4 at the end. So linked

// list becomes 1->7->6->4->NULL

dll.append[4];

// Insert 8, after 7. So linked

// list becomes 1->7->8->6->4->NULL

dll.InsertAfter[dll.head.next, 8];

// Insert 5, before 8.So linked

// list becomes 1->7->5->8->6->4

dll.InsertBefore[dll.head.next.next, 5];

System.out.println["Created DLL is: "];

dll.printlist[dll.head];

}

}

// This code is contributed by Sumit Ghosh