12. Double Linked List in C++

Introduction to Double Linked List

A Double Linked List is a type of linked list in which each node contains a data part and two addresses, one for the previous node and one for the next node. It allows traversal in both the forward and backward directions.

Key Points:

• Each node contains an element of data.

• Each node also contains a link to the previous and next node in the list.

• The first node (known as the head) has a null previous link and the last node has a null next link.

Node in Double Linked List

A node in a double linked list primarily contains three elements:

• Data: It holds the information.

• Prev: It holds the address of the previous node in the list.

• Next: It holds the address of the next node in the list.

struct Node {
    int data;
    Node* prev;
    Node* next;
};

Operations in Double Linked List

pushlast() function

The pushlast() function is used to insert a new node at the end of the double linked list. The time complexity of this operation is O(1) as it does the insertion in constant time, regardless of the size of the list.

Example:

void pushlast(Node** head_ref, int new_data)
{
    Node* new_node = new Node();
    Node* last = *head_ref;

    new_node->data = new_data;
    new_node->next = NULL;

    if (*head_ref == NULL) {
        new_node->prev = NULL;
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL)
        last = last->next;

    last->next = new_node;
    new_node->prev = last;
}

pushfirst() function

The pushfirst() function is used to add a new node at the beginning of the double linked list. The time complexity of this operation is O(1), as it adds a new node in constant time.

Example:

void pushfirst(Node** head_ref, int new_data)
{
    Node* new_node = new Node();

    new_node->data = new_data;
    new_node->next = (*head_ref);
    new_node->prev = NULL;

    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;

    *head_ref = new_node;
}

To conclude, a double linked list is a more sophisticated type of linked list that allows for more efficient and flexible manipulations of data structures. It's especially useful in implementations where data needs to be accessed or manipulated in a non-linear sequence.

Reference

The content in this document is based on the original notes provided in Azerbaijani. For further details, you can refer to the original document using the following link:

Original Note - Azerbaijani Version