Doubly-linked lists: Insert

Inserting Elements into a Doubly Linked List

Inserting an element into a doubly linked list requires updating both the prev and next pointers of the involved nodes. Depending on where the new element is added, the insertion steps will vary. Below, we outline the three main types of insertions: at the head, tail, and a specific position within the list.

Insert at the Head of the List

Inserting at the head of a doubly linked list involves adding the new node before the current head. This operation is efficient because you only need to update a few pointers. Here’s how you can do it:

Steps:

1. Create the new node:
   Allocate memory for the new node and assign the element value to it.

2. Set the new node’s next pointer:
   Point the next pointer of the new node to the current head of the list.

3. Update the current head’s prev pointer (if the list is not empty):
   If the list is non-empty, set the prev pointer of the current head to the new node.

4. Update the list’s head:
   Set the head pointer to the new node, making it the first element in the list.

Edge Case:

• If the list is empty, the new node becomes both the head and the tail of the list (its prev and next pointers will be nullptr).

Insert at the Tail of the List

Inserting at the tail involves adding the new node after the current tail of the list. This is also efficient because the tail pointer is usually maintained in doubly linked lists, allowing direct access to the last node.

Steps:

1. Create the new node:
   Allocate memory for the new node and set its value.

2. Set the new node’s prev pointer:
   Point the prev pointer of the new node to the current tail.

3. Update the current tail’s next pointer:
   Set the next pointer of the current tail to the new node.

4. Update the list’s tail:
   Set the tail pointer to the new node, making it the last element in the list.

Edge Case:

• If the list is empty, the new node becomes both the head and the tail of the list (its prev and next pointers will be nullptr).

Insert at a Specific Position in the List

Inserting at a specific position in the list requires traversing to the node before the desired position. Once there, you insert the new node by adjusting the next and prev pointers of the neighboring nodes.

Steps:

1. Traverse to the target position:
   Start at the head and traverse the list until you reach the node just before the target position.

2. Create the new node:
   Allocate memory for the new node and set its value.

3. Update pointers:

   • Set the new node’s next pointer to point to the node currently at the target position.

   • Set the new node’s prev pointer to point to the node before the target position.

   • Update the prev pointer of the node at the target position to point to the new node.

   • Update the next pointer of the node before the target position to point to the new node.

Edge Cases:

• Inserting at the beginning: If inserting at position 0, follow the steps for "Insert at the Head."

• Inserting at the end: If inserting at the last position (after the current tail), follow the steps for "Insert at the Tail."

• Out-of-bounds position: If the position exceeds the length of the list, the insertion should be disallowed or handled with an error message.

Key Points to Remember:

• Pointer Updates: When inserting into a doubly linked list, always ensure that the prev and next pointers of the new node and the neighboring nodes are updated correctly to maintain the integrity of the list.

• Efficiency: Inserting at the head or tail is efficient (O(1)) because no traversal is required. Inserting at a specific position may require traversing the list, making it O(n).

• Edge Cases: To avoid errors, always consider empty lists or boundary positions (beginning or end) when performing insertions.

Inserting elements into a doubly linked list can be done efficiently, whether at the head, tail, or a specific position. The key to correctly inserting nodes lies in properly updating the pointers to ensure the list remains linked in both directions. With careful pointer management, doubly linked lists provide a flexible and powerful way to manage dynamic collections of data.