JIYIK CN >

Doubly linked list is a linear data structure. It is a collection of objects defined as nodes. But unlike a linked list, the node has two pointers, one is the previous pointer and the other is the next pointer. Just like the linked list nodes are stored in random locations in the memory instead of being stored in consecutive locations.

Doubly Linked List vs Linked List

1. Doubly linked lists allow us to traverse the linked list in both forward and backward directions, but this comes prevat the cost of extra space required for pointers to each node.
2. Inserting an element in a doubly linked list is very easy as we do not have to maintain multiple pointers or traverse the linked list to find the previous pointer, but we have to modify more pointers compared to a linked list.

Doubly Linked List Traversal Algorithm

The way forward

Let headbe the first node of the linked list.

• Initializes a node currpointing to a linked list head.
• While currhas not yet reached the end of the list, i.e. curr! = NULL, do the following:
  • Prints the data stored in the current node.
  • curr=curr->next;
  • If it is the last node, it is stored tailas to facilitate backward traversal.

Likewise, we can traverse backwards by tailstarting at and currchanging to .curr->prev

Reverse direction

Let tailbe the last node of the linked list.

• Initializes a node currpointing to a linked list tail.
• While currhas not yet reached the head of the list, i.e. curr!= NULL, do the following:
  • Prints the data stored in the current node.
  • curr = curr->上一个

Doubly Linked List Insertion

4Doubly linked lists have situations when inserting elements , just like linked lists.

Insert the node at push()the beginning of the DLL

• Create a new node for with data xand . prevNULLtemp
• Set temp->nextto headand head->prevset to to insert tempbefore . headtemp
• Sets tempto the beginning of the linked list.

Append()Insert a node at the end of the DLL

• Create a new node tempwhose data is xand whose previs NULL.
• Initializes pointer headto tail.
• If the linked list is empty, tempsets to the linked list's headand then returns .
• Otherwise, iterate to the end of the linked list, making tail->next!= NULLso that you reach the last element
• Set tail->nextto temp, and temp->prevset to tail.

insertBefore()Inserts a node before the given node

• If next== NULL, then return;
• xCreate a new node with data curr.
• Set curr->prevto to add a new node before , and next->prevset to to establish a backward link. nextnext->prevcurr
• Set curr->nextto next, and finally check curr->prevwhether is NULL.
• If not NULL, curr->prev->nextset to to currcomplete the insertion, otherwise curris the first node of the linked list. Set headto curr.

insertAfter()Inserts a node after the given node

• If prev== NULL, then return;
• xCreate a new node with data curr.
• Set curr->nextto to add a new node after , and prev->nextset to to establish a forward link. prevprev->nextcurr
• Set curr->prevto prev, and finally check curr->nextif is NULL. If not NULL, curr->next->prevset to currto complete the insert.

Doubly Linked List Insertion Process

1. Insert the node at push()the beginning of the DLL
2. Append()Insert a node at the end of the DLL
3. insertBefore()Inserts a node before the given node
4. insertAfter()Insert a node after the given node

Doubly linked list traversal and insertion implementation

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node* prev;
};

void push(Node** head, int x)
{
    Node* curr = new Node();
    curr->data = x;
    curr->next = (*head);
    curr->prev = NULL;
    if ((*head) != NULL)
        (*head)->prev = curr;
    (*head) = curr;
}
void insertAfter(Node* prev, int x)
{
    if (prev == NULL)
    {
        cout << "the given previous node cannot be NULL";
        return;
    }

    Node* curr = new Node();
    curr->data = x;
    curr->next = prev->next;
    prev->next = curr;
    curr->prev = prev;
    if (curr->next != NULL)
        curr->next->prev = curr;
}

void insertBefore(struct Node** head, struct Node* next, int x)
{    if (next == NULL) {
        return;
    }

    Node* curr = new Node();
    curr->data = x;
    curr->prev = next->prev;
    next->prev = curr;
    curr->next = next;
    if (curr->prev != NULL)
        curr->prev->next = curr;
    else
        (*head) = curr;
}

void append(Node** head, int x)
{
    Node* curr = new Node();
    Node* tail = *head;
    curr->data = x;
    curr->next = NULL;
    if (*head == NULL)
    {
        curr->prev = NULL;
        *head = curr;
        return;
    }
    while (tail->next != NULL)
        tail = tail->next;
    tail->next = curr;
    curr->prev = tail;
    return;
}

void printList(Node* node)
{
    Node* tail = NULL;
    cout << "Forward Traversal:";
    while (node != NULL)
    {
        cout << " " << node->data << " ";
        tail = node;
        node = node->next;
    }

    cout << "\nReverse Traversal:";
    while (tail != NULL)
    {
        cout << " " << tail->data << " ";
        tail = tail->prev;
    }
    cout << "\n";
}

int main()
{

    Node* head = NULL;
    append(&head, 6);
    push(&head, 7);
    push(&head, 1);
    append(&head, 4);
    printList(head);
    insertAfter(head->next, 8);
    insertBefore(&head, head->next->next, 3);
    printList(head);
    return 0;
}

Complexity of Doubly Linked List Traversal and Insertion Algorithms

Traversal

• Average situation

To traverse the complete doubly linked list, we have to visit every node. Therefore, if it has nnodes, the average case time complexity of traversal is about O(n). The time complexity is about O(n).

• Best Case

The time complexity of the best case is O(n). It is the same as the time complexity of the average case.

• Worst case scenario

The worst case time complexity is O(n). It is the same as the best case time complexity.

The space complexity of the traversal algorithm is O(1), since currno space is required other than the pointer.

Insertion method

• Average situation

In all 4cases inserting an element requires at most 4link changes, so the time complexity of insertion is O(1).

• Best Case

The time complexity of the best case is O(1). It is the same as the time complexity of the average case.

• Worst case scenario

The worst case time complexity is O(1). It is the same as the best case time complexity.

For all 4insertion methods, the space complexity of the insertion algorithm is O(1).