- 1Singly Linked List Introduction
- 2Singly Linked List – Create Operation
- 3Singly Linked List – Insert Operation
- 4Singly Linked List – Delete Operation
- 5Singly Linked List – Traversal Operation
- 6Singly Linked List – Search Operation
- 7Singly Linked List – Get Length Operation
- 8Singly Linked List – Reverse Operation
- 9Doubly Linked List Introduction
- 10Doubly Linked List – Create Operation
- 11Doubly Linked List – Insert Operation
- 12Doubly Linked List – Delete Operation
- 13Doubly Linked List – Traversal Operation
- 14Doubly Linked List – Search Operation
- 15Doubly Linked List – Get Length Operation
- 16Doubly Linked List – Reverse Operation
Doubly Linked List – Create Operation
Creating a Doubly Linked List
Creating a doubly linked list involves adding nodes one by one, where each node holds a value, a pointer to the next node, and a pointer to the previous node. This two-way linkage allows for traversal in both directions.
Just like singly linked lists, doubly linked lists grow dynamically, but offer more flexibility when it comes to insertion and deletion at both ends or in the middle of the list.
Visual Example
We will build a doubly linked list by inserting the following values one by one: [10, 20, 30, 40]
Initial Empty List
Step 1: Insert 10
- Create a new node with value
10. - Since the list is empty, this node becomes the
head.
Step 2: Insert 20
- Create a new node with value
20. - Set
20.prevto10and10.nextto20.
Step 3: Insert 30
- Create a new node with value
30. - Set
30.prevto20and20.nextto30.
Step 4: Insert 40
- Create a new node with value
40. - Set
40.prevto30and30.nextto40.
At this point, the doubly linked list has been created successfully with all nodes properly linked in both forward (next) and backward (prev) directions.
Complete Pseudocode: Create Doubly Linked List by Appending
This pseudocode builds a doubly linked list by appending each new node to the end and updating both prev and next links.
function createDoublyLinkedList():
head = null
tail = null
while input has values:
value = next input
node = new DllNode(value)
if head == null:
head = node
tail = node
else:
tail.next = node
node.prev = tail
tail = node
return headLet’s walk through each part of the code to understand what it does.
function createDoublyLinkedList():
head = null
tail = nullExplanation: We begin with an empty list. head will point to the first node, and tail will track the end for efficient appending.
while input has values:
value = next input
node = new DllNode(value)Explanation: We loop through the input (e.g., [10, 20, 30]) and create a new node for each value.
if head == null:
head = node
tail = nodeExplanation: For the very first value, both head and tail are set to the new node.
else:
tail.next = node
node.prev = tail
tail = nodeExplanation: For subsequent values, we update the current tail.next and the new node's prev, then move tail forward.
return headExplanation: The head node gives us access to the full doubly linked list, which we can now traverse in both directions.
Doubly Linked List Creation Examples
The following examples show how nodes are added one by one to build a doubly linked list dynamically. Each node maintains both prev and next pointers.
| Insert Sequence | Final Linked List | Explanation |
|---|---|---|
| [10, 20, 30] | null ← 10 ⇄ 20 ⇄ 30 → null | Three nodes are inserted sequentially. Each new node is linked to both the previous and the next node using prev and next pointers. |
| [5] | null ← 5 → null | Only one node is inserted. Its prev and next pointers are both null, making it both head and tail. |
| [] | null | No values are provided, so the list is empty and head = null. |
| [1, 2, 3, 4, 5] | null ← 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 → null | Five nodes are added to build a complete doubly linked list. Each node is connected to its neighbors with two-way links. |
Time Complexity of Doubly Linked List Create Operation
| Creation Case | Time Complexity | Explanation |
|---|---|---|
| Creating list by appending with tail pointer | O(n) | Each node is appended in O(1) time using the tail pointer. Creating n nodes takes linear time overall. |
| Creating list by inserting at head | O(n) | Each node is inserted at the beginning in constant time. Repeating this for n nodes results in O(n) time. |
| Creating list by traversing to insert at end (no tail) | O(n2) | Each insert at end requires a full traversal (O(n)), done n times. Leads to quadratic time overall. |
Space Complexity of Doubly Linked List Create Operation
| Creation Case | Space Complexity | Explanation |
|---|---|---|
| Creating a list of n nodes | O(n) | Each node requires space for its value, a pointer to the next node, and a pointer to the previous node. Thus, total space grows linearly with the number of nodes. |
Key Takeaways
- A Doubly Linked List (DLL) consists of nodes that store
data, anextpointer, and aprevpointer. - Each node is linked in both directions, enabling efficient forward and backward traversal.
- Creating a DLL involves inserting nodes and updating both
nextandprevreferences appropriately. - The head node’s
previs alwaysnull, and the tail node’snextis alwaysnull. - Space complexity is
O(n)since each of thennodes stores additional pointers. - DLLs are more flexible than singly linked lists but use slightly more memory per node due to the extra pointer.
Sign in with Google
Comments
Loading comments...