712534. Introduction to Doubly Linked List
Here is the Markdown blog post for the "Introduction to Doubly Linked List" problem:
Introduction to Doubly Linked List
Summary
Given a doubly linked list, write an algorithm to insert a new node at the beginning and end of the list. The key concepts involved are doubly linked lists, nodes, and pointers.
Detailed Explanation
Insertion at Beginning
To insert a new node at the beginning of the list, we first create a new node with the given data. Then, we update the prev pointer of the current head node to point to the new node. Finally, we set the next pointer of the new node to the current head node and update the head node to point to the new node.
Insertion at End
To insert a new node at the end of the list, we first find the last node in the list by traversing from the head node until we reach a node with next pointer set to NULL. Then, we create a new node and update its prev and next pointers. The prev pointer is set to point to the last node, and the next pointer is set to NULL.
Step-by-Step Breakdown
Here's a step-by-step breakdown of the solution:
- Create a new node with the given data.
- Update the
prevpointer of the current head node to point to the new node (insertion at beginning). - Set the
nextpointer of the new node to the current head node (insertion at beginning). - Update the head node to point to the new node (insertion at beginning).
- Find the last node in the list by traversing from the head node until we reach a node with
nextpointer set toNULL. - Create a new node and update its
prevandnextpointers. - Set the
prevpointer of the new node to point to the last node (insertion at end). - Set the
nextpointer of the new node toNULL(insertion at end).
Time Complexity Analysis
The time complexity for both insertion operations is O(1) because we only need to update a few pointers.
Space Complexity Analysis
The space complexity is O(1) because we are not using any additional space that scales with the input size.
Optimized Solutions
Java
public class DoublyLinkedList {
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head == null) {
head = tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
}
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (tail == null) {
head = tail = newNode;
} else {
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
}
}
}