Page 39 - Data Structures Interactive Book

• At end: traverse to second-last node, set its pointer to NULL.

• At position: adjust pointers to skip the node being deleted.

4.3 Doubly Linked List

A doubly linked list extends the singly linked list by adding a pointer to the previous

node, allowing traversal in both directions.

4.3.1 Structure and Properties

Each node contains three fields: data, pointer to the next node, and pointer to the

previous node. This bidirectional structure enables more flexible operations.

4.3.2 Insertion and Deletion

Insertion and deletion are like singly linked lists but require updating both next and
prev pointers. This makes operations more complex but also more powerful.

4.3.3 Advantages over Singly Linked List

Doubly linked lists allow backward traversal and more efficient deletion when the

node to be removed is known. However, they consume more memory due to the additional
pointer.

4.4 Circular Linked List

In a circular linked list, the last node points back to the first node, forming a circle. This

structure can be implemented as singly or doubly circular.

4.4.1 Singly Circular Linked List

Each node points to the next, and the last node points back to the head. This allows

continuous traversal without encountering NULL.

39