Page 105 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes nn = (node *)malloc(sizeof(node));
nn->age = tmp;
nn->next = NULL;
return nn;
}
It shows the following output:

7.2.2 Doubly Linked List

If a node also stores a reference to the previous node it can move in both directions, forth and
back; this is obviously called a doubly linked list, which is shown below. A doubly linked list is
a list that has two references, one to the next node and another to previous node. Doubly linked
list also starts from head node, but provide access both ways. That is one can traverse forward or
backward from any node.

Figure 7.6: Doubly Linked List

Notes In comparison to singly-linked list, doubly-linked list requires handling of more
pointers but less information is required as one can use the previous links to observe the
preceding element. It has a dynamic size, which can be determined only at run time.

The advantage of a doubly linked list (also called two-way linked list) is given a node in the list, we
can navigate in both directions. A node in a singly linked list cannot be removed unless we have
the pointer to its predecessor. But in doubly linked list we can delete a node even if we don’t
have previous nodes address (since, each node has left pointer pointing to previous node and
can move backward).

98 LOVELY PROFESSIONAL UNIVERSITY