INTRODUCTION OF TWO-WAY LINK LIST
A Two-Way Linked
List, also known as a Doubly Linked List, is a type of linked list where each
node contains a data element and two pointers.
Unlike a singly
linked list, a doubly linked list node has both a pointer to the next node
(next pointer) and a pointer to the previous node (prev pointer).
This bidirectional
connectivity enables traversal in both forward and backward directions.
The basic structure of
a node
The structure of a
node in a doubly linked list:
In this
representation:
- The "Prev"
field points to the previous node in the list.
- The "Data"
field holds the actual data or value of the node.
- The "Next"
field points to the next node in the list.
---------------------------------------------------------------------------------------------------
Structure of a
node in a doubly linked list: cpp
struct Node {
Node* prev;
// Pointer to the previous node
int data;
// Data or value of the node
Node* next;
// Pointer to the next node
};
In this structure:
- `prev` is a pointer
to the previous node.
- `data` holds the
value or data of the node.
- `next` is a
pointer to the next node.
Example:- python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class
DoublyLinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def display(self):
current = self.head
while current:
print(current.data, end="
")
current = current.next
print()
# Example usage:
dll =
DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()
# Output: 1 2 3
-------------------------------------------
Node creation:-
c++
#include
<iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) : data(value),
next(nullptr), prev(nullptr) {}
};
class
DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
void append(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
void display() {
Node* current = head;
while (current) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.append(1);
dll.append(2);
dll.append(3);
dll.display();
return 0;
}
// Output: 1 2 3
-----------------------------------------
Basic Operation of
Two-Way link list
Basic operations
on a Two-Way Linked List (Doubly Linked List) include insertion, deletion,
traversal, and searching.
Insertion
Insertion at the Beginning:
To insert a new
node at the beginning of a doubly linked list:
Algorithm
InsertAtBeginning(list, value):
1. Create a new node with the given value.
2. Set the "data" field of the
new node to the given value.
3. Set the "next" field of the
new node to the current head of the list.
4. Set the "prev" field of the
new node to null (since it's the new head).
5. If the current head is not null, set the
"prev" field of the current head to the new node.
6. Set the head of the list to the new
node.
Example:- ### C++
Example:
#include
<iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) : data(value),
next(nullptr), prev(nullptr) {}
};
class
DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
void insertAtBeginning(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
void display() {
Node* current = head;
while (current) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.insertAtBeginning(3);
dll.insertAtBeginning(2);
dll.insertAtBeginning(1);
dll.display(); //
return 0;
}
Output: 1 2 3
-----------------------------------
Python Example:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert_at_beginning(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
def display(self):
current = self.head
while current:
print(current.data, end="
")
current = current.next
print()
# Example usage in
Python:
dll =
DoublyLinkedList()
dll.insert_at_beginning(3)
dll.insert_at_beginning(2)
dll.insert_at_beginning(1)
dll.display()
# Output: 1 2 3
In both examples,
a new node is inserted at the beginning of the doubly linked list. The
`insertAtBeginning` method (C++) and `insert_at_beginning` method (Python)
handle the insertion process, updating the pointers accordingly. The `display`
method is used to print the elements in the list for verification.
------------------------------------------
Insertion at the End: To insert a new node
at the end of a doubly linked list:
Algorithm
InsertAtEnd(list, value):
1. Create a new node with the given value.
2. Set the "data" field of the
new node to the given value.
3. Set the "next" field of the
new node to null (since it's the new tail).
4. If the list is empty, set the head of
the list to the new node.
5. Otherwise, traverse to the current tail
of the list.
6. Set the "next" field of the
current tail to the new node.
7. Set the "prev" field of the
new node to the current tail.
8. Update the tail of the list to the new
node.
C++ Example: cpp
#include
<iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) : data(value), next(nullptr),
prev(nullptr) {}
};
class
DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
void display() {
Node* current = head;
while (current) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
dll.display();
return 0;
}
// Output: 1 2 3
---------------------------------------------
Python Example:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class
DoublyLinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
def display(self):
current = self.head
while current:
print(current.data, end="
")
current = current.next
print()
# Example usage in
Python:
dll =
DoublyLinkedList()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.display()
Output: 1 2 3
In both examples,
a new node is inserted at the end of the doubly linked list. The `insertAtEnd`
method (C++) and `insert_at_end` method (Python) handle the insertion process,
updating the pointers accordingly. The `display` method is used to print the
elements in the list for verification.
-------------------------------------------------------
At the specific node:-
C++ Example: cpp
#include
<iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) : data(value),
next(nullptr), prev(nullptr) {}
};
class
DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
// Insert a new node at a specific position
void insertAtPosition(int position, int
value) {
if (position < 1) {
std::cerr << "Invalid
position." << std::endl;
return;
}
Node* newNode = new Node(value);
if (position == 1 || !head) {
// Insert at the beginning
newNode->next = head;
if (head) {
head->prev = newNode;
}
head = newNode;
} else {
// Insert at a specific position
Node* current = head;
for (int i = 1; i < position - 1
&& current; ++i) {
current = current->next;
}
if (!current) {
std::cerr <<
"Position out of bounds." << std::endl;
delete newNode;
return;
}
newNode->next =
current->next;
newNode->prev = current;
current->next = newNode;
if (newNode->next) {
newNode->next->prev =
newNode;
}
}
}
void display() {
Node* current = head;
while (current) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.insertAtPosition(0, 1); // Invalid position
dll.insertAtPosition(1, 1);
dll.insertAtPosition(2, 3);
dll.insertAtPosition(2, 2);
dll.display(); // Output: 1 2 3
return 0;
}
// Output:
1 2 3
-------------------------------------------------------------
Python Example:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class
DoublyLinkedList:
def __init__(self):
self.head = None
# Insert a new node at a specific position
def insert_at_position(self, position,
data):
if position < 1:
print("Invalid
position.")
return
new_node = Node(data)
if position == 1 or not self.head:
# Insert at the beginning
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node
else:
# Insert at a specific position
current = self.head
for i in range(1, position - 1):
if not current:
print("Position out of
bounds.")
return
current = current.next
new_node.next = current.next
new_node.prev = current
current.next = new_node
if new_node.next:
new_node.next.prev = new_node
def display(self):
current = self.head
while current:
print(current.data, end="
")
current = current.next
print()
# Example usage in
Python:
dll =
DoublyLinkedList()
# Invalid position
dll.insert_at_position(0,
1)
dll.insert_at_position(1,
1)
dll.insert_at_position(2,
3)
dll.insert_at_position(2,
2)
dll.display()
# Output: 1
2 3
In both examples,
a new node is inserted at a specific position in the doubly linked list. The
`insertAtPosition` method (C++) and `insert_at_position` method (Python) handle
the insertion process, updating the pointers accordingly. The `display` method is
used to print the elements in the list for verification.
--------------------------------------------------------
Deletion:
To delete a node
from a doubly linked list:
Algorithm
DeleteNode(list, target):
1. If the list is empty, do nothing.
2. Traverse the list to find the node with
the target value.
3. If the target node is the head, update
the head to the next node.
4. If the target node is the tail, update
the tail to the previous node.
5. Update the "next" field of the
previous node to skip the target node.
6. Update the "prev" field of the
next node to skip the target node.
7. Delete the target node.
C++ Example: cpp
#include <iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) : data(value),
next(nullptr), prev(nullptr) {}
};
class
DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
// Delete a node with a specific value
void deleteNode(int value) {
Node* current = head;
// Find the node with the specified
value
while (current &&
current->data != value) {
current = current->next;
}
if (!current) {
std::cerr << "Node with
value " << value << " not found." <<
std::endl;
return;
}
if (current->prev) {
current->prev->next =
current->next;
} else {
head = current->next;
}
if (current->next) {
current->next->prev =
current->prev;
}
delete current;
}
void display() {
Node* current = head;
while (current) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.deleteNode(2); // Node not found
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
dll.deleteNode(2);
dll.display();
return 0;
}
Output: 1 3
-----------------------------------------------------------------------
Python Example:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class
DoublyLinkedList:
def __init__(self):
self.head = None
# Delete a node with a specific value
def delete_node(self, value):
current = self.head
# Find the node with the specified
value
while current and current.data !=
value:
current = current.next
if not current:
print(f"Node with value
{value} not found.")
return
if current.prev:
current.prev.next = current.next
else:
self.head = current.next
if current.next:
current.next.prev = current.prev
del current
def display(self):
current = self.head
while current:
print(current.data, end="
")
current = current.next
print()
# Example usage in
Python:
dll =
DoublyLinkedList()
# Node not found
dll.delete_node(2)
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.delete_node(2)
dll.display()
Output: 1 3
In both examples,
a node is deleted from the doubly linked list based on a specified value. The
`deleteNode` method (C++) and `delete_node` method (Python) handle the deletion
process, updating the pointers accordingly. The `display` method is used to print
the elements in the list for verification
-------------------------------------------------
Deletion from the head
node.
C++ Example:
#include
<iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) : data(value),
next(nullptr), prev(nullptr) {}
};
class
DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
// Delete the head node
void deleteHead() {
if (!head) {
std::cerr << "List is
empty. Cannot delete head." << std::endl;
return;
}
Node* temp = head;
head = head->next;
if (head) {
head->prev = nullptr;
}
delete temp;
}
void display() {
Node* current = head;
while (current) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.deleteHead(); // List is empty. Cannot
delete head.
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
dll.deleteHead();
dll.display();
return 0;
}
Output: 2 3
---------------------------------------------------
Python Example: python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class
DoublyLinkedList:
def __init__(self):
self.head = None
# Delete the head node
def delete_head(self):
if not self.head:
print("List is empty. Cannot
delete head.")
return
temp = self.head
self.head = self.head.next
if self.head:
self.head.prev = None
del temp
def display(self):
current = self.head
while current:
print(current.data, end="
")
current = current.next
print()
# Example usage in
Python:
dll =
DoublyLinkedList()
# List is empty.
Cannot delete head.
dll.delete_head()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.delete_head()
dll.display() # Output: 2 3
In both examples,
the head node is deleted from the doubly linked list. The `deleteHead` method
(C++) and `delete_head` method (Python) handle the deletion process, updating
the pointers accordingly. The `display` method is used to print the elements in
the list for verification.
-----------------------------------------------
After the deletion of the middle node.
Deleting a middle node from a doubly linked list typically involves
finding the middle node and then removing it.
C++ Example: cpp
#include <iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) : data(value),
next(nullptr), prev(nullptr) {}
};
class DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() :
head(nullptr) {}
// Find the middle node and
delete it
void deleteMiddle() {
if (!head ||
!head->next) {
std::cerr <<
"List is empty or has only one node. Cannot delete middle." <<
std::endl;
return;
}
Node* slow = head;
Node* fast = head;
while (fast &&
fast->next) {
slow = slow->next;
fast =
fast->next->next;
}
if (slow->prev) {
slow->prev->next
= slow->next;
} else {
head = slow->next;
}
if (slow->next) {
slow->next->prev
= slow->prev;
}
delete slow;
}
void display() {
Node* current = head;
while (current) {
std::cout <<
current->data << " ";
current =
current->next;
}
std::cout <<
std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.deleteMiddle(); // List is
empty or has only one node. Cannot delete middle.
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
dll.insertAtEnd(4);
dll.deleteMiddle();
dll.display();
return 0;
}
Output: 1 3 4
---------------------------------------------------------
Python Example:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
# Find the middle node and
delete it
def delete_middle(self):
if not self.head or not
self.head.next:
print("List is
empty or has only one node. Cannot delete middle.")
return
slow = self.head
fast = self.head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow.prev:
slow.prev.next =
slow.next
else:
self.head = slow.next
if slow.next:
slow.next.prev =
slow.prev
del slow
def display(self):
current = self.head
while current:
print(current.data,
end=" ")
current = current.next
print()
# Example usage in Python:
dll = DoublyLinkedList()
# List is empty or has only one node. Cannot delete middle.
dll.delete_middle()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.insert_at_end(4)
dll.delete_middle()
dll.display()
Output: 1 3 4
In both examples, the middle node is found and deleted from the doubly
linked list. The `deleteMiddle` method (C++) and `delete_middle` method
(Python) handle the deletion process, updating the pointers accordingly. The
`display` method is used to print the elements in the list for verification.
----------------------------------------------------------------------------------------
After the deletion of the last node.
Deleting the last
node from a doubly linked list involves updating pointers and freeing memory.
C++ Example:
#include <iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) : data(value),
next(nullptr), prev(nullptr) {}
};
class
DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
// Delete the last node
void deleteLast() {
if (!head) {
std::cerr << "List is
empty. Cannot delete last node." << std::endl;
return;
}
Node* last = head;
while (last->next) {
last = last->next;
}
if (last->prev) {
last->prev->next = nullptr;
} else {
// If the list has only one node
head = nullptr;
}
delete last;
}
void display() {
Node* current = head;
while (current) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.deleteLast(); // List is empty. Cannot
delete last node.
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
dll.deleteLast();
dll.display();
return 0;
}
Output: 1 2
------------------------------------------
Python Example:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class
DoublyLinkedList:
def __init__(self):
self.head = None
# Delete the last node
def delete_last(self):
if not self.head:
print("List is empty. Cannot
delete last node.")
return
last = self.head
while last.next:
last = last.next
if last.prev:
last.prev.next = None
else:
# If the list has only one node
self.head = None
del last
def display(self):
current = self.head
while current:
print(current.data, end="
")
current = current.next
print()
# Example usage in
Python:
dll =
DoublyLinkedList()
# List is empty.
Cannot delete last node.
dll.delete_last()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
dll.delete_last()
dll.display() # Output: 1 2
In both examples,
the last node is deleted from the doubly linked list. The `deleteLast` method
(C++) and `delete_last` method (Python) handle the deletion process, updating
the pointers accordingly. The `display` method is used to print the elements in
the list for verification.
----------------------------------------------------------------------
Traversal:
To traverse a
doubly linked list in both forward and backward directions:
Algorithm
Traverse(list):
1. Initialize a pointer current to the head
of the list.
2. Forward traversal:
a. While current is not null:
- Process the data in the current
node.
- Move current to the next node.
3. Backward traversal:
b. Initialize a pointer tail to the tail
of the list.
c. While tail is not null:
- Process the data in the tail node.
- Move tail to the previous node.
examples in C++
and Python to traverse a doubly linked list in both forward and backward
directions, along with sample outputs:
C++ Example:
#include
<iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) : data(value),
next(nullptr), prev(nullptr) {}
};
class
DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
// Traverse the list in forward direction
void traverseForward() {
Node* current = head;
while (current) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
// Traverse the list in backward direction
void traverseBackward() {
Node* current = head;
while (current->next) {
current = current->next;
}
while (current) {
std::cout << current->data
<< " ";
current = current->prev;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
std::cout << "Forward traversal:
";
dll.traverseForward(); // Output: 1 2 3
std::cout << "Backward
traversal: ";
dll.traverseBackward(); // Output: 3 2 1
return 0;
}
------------------------------------------------------------
Python Example:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class
DoublyLinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, value):
new_node = Node(value)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
# Traverse the list in forward direction
def traverse_forward(self):
current = self.head
while current:
print(current.data, end="
")
current = current.next
print()
# Traverse the list in backward direction
def traverse_backward(self):
current = self.head
while current.next:
current = current.next
while current:
print(current.data, end="
")
current = current.prev
print()
# Example usage in
Python:
dll =
DoublyLinkedList()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
print("Forward
traversal:", end=" ")
dll.traverse_forward() # Output: 1 2 3
print("Backward
traversal:", end=" ")
dll.traverse_backward() # Output: 3 2 1
In both examples,
a doubly linked list is created, elements are inserted, and then the list is
traversed in both forward and backward directions. The `traverseForward` method
(C++) and `traverse_forward` method (Python) print the elements in the forward direction,
while the `traverseBackward` method (C++) and `traverse_backward` method
(Python) print the elements in the backward direction.
-------------------------------------------
Searching:
To search for a
node with a specific value in a doubly linked list:
Algorithm
Search(list, value):
1. Initialize a pointer current to the head
of the list.
2. While current is not null:
- If the "data" field of the
current node is equal to the target value, return the current node.
- Move current to the next node.
3. If the loop completes and the target
value is not found, return null.
examples in C++
and Python to search for a node with a specific value in a doubly linked list,
along with sample outputs:
C++ Example:
#include
<iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) : data(value),
next(nullptr), prev(nullptr) {}
};
class
DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
// Search for a node with a specific value
Node* searchNode(int value) {
Node* current = head;
while (current) {
if (current->data == value) {
return current;
}
current = current->next;
}
return nullptr; // Node not found
}
void display() {
Node* current = head;
while (current) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
int searchValue = 2;
Node* foundNode =
dll.searchNode(searchValue);
if (foundNode) {
std::cout << "Node with
value " << searchValue << " found." <<
std::endl;
} else {
std::cout << "Node with
value " << searchValue << " not found." <<
std::endl;
}
return 0;
}
---------------------------------------------------------
Python Example:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, value):
new_node = Node(value)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
# Search for a node with a specific value
def search_node(self, value):
current = self.head
while current:
if current.data == value:
return current
current = current.next
return None # Node not found
def display(self):
current = self.head
while current:
print(current.data, end="
")
current = current.next
print()
# Example usage in
Python:
dll =
DoublyLinkedList()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
search_value = 2
found_node =
dll.search_node(search_value)
if found_node:
print(f"Node with value {search_value}
found.")
else:
print(f"Node with value {search_value}
not found.")
----------
In both examples,
a doubly linked list is created, elements are inserted, and then the list is
searched for a node with a specific value. The `searchNode` method (C++) and
`search_node` method (Python) return the found node or `nullptr`/`None` if the
node is not found. The result is then printed accordingly.
These algorithms
cover the basic operations on a Two-Way Linked List. It's essential to handle
edge cases and manage pointers carefully to maintain the integrity of the list
during these operations.
------------------------------------
To update for a
node with a specific value in a doubly linked list.
Updating Operation
Algorithm:
Algorithm
UpdateNode(list, target, newValue):
1. Initialize a pointer current to the head
of the list.
2. While current is not null:
a. If the "data" field of the
current node is equal to the target value:
- Update the "data" field
of the current node with the new value (newValue).
- Return, as the update is
complete.
b. Move current to the next node.
3. If the loop completes and the target
value is not found, print a message or handle accordingly.
examples in C++
and Python to update a node with a specific value in a doubly linked list,
along with sample outputs:
C++ Example:
#include
<iostream>
class Node {
public:
int data;
Node* next;
Node* prev;
Node(int value) : data(value),
next(nullptr), prev(nullptr) {}
};
class
DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
Node* current = head;
while (current->next) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
// Update a node with a specific value
void updateNode(int oldValue, int newValue)
{
Node* current = head;
while (current) {
if (current->data == oldValue) {
current->data = newValue;
return; // Update complete, exit the function
}
current = current->next;
}
std::cerr << "Node with
value " << oldValue << " not found. Update failed."
<< std::endl;
}
void display() {
Node* current = head;
while (current) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList dll;
dll.insertAtEnd(1);
dll.insertAtEnd(2);
dll.insertAtEnd(3);
std::cout << "Original list:
";
dll.display(); // Output: 1 2 3
int oldValue = 2;
int newValue = 4;
dll.updateNode(oldValue, newValue);
std::cout << "Updated list:
";
dll.display(); // Output: 1 4 3
return 0;
}
-------------------------------------------
Python Example:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class
DoublyLinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, value):
new_node = Node(value)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
# Update a node with a specific value
def update_node(self, old_value,
new_value):
current = self.head
while current:
if current.data == old_value:
current.data = new_value
return # Update complete, exit the function
current = current.next
print(f"Node with value
{old_value} not found. Update failed.")
def display(self):
current = self.head
while current:
print(current.data, end="
")
current = current.next
print()
# Example usage in
Python:
dll =
DoublyLinkedList()
dll.insert_at_end(1)
dll.insert_at_end(2)
dll.insert_at_end(3)
print("Original
list:", end=" ")
dll.display() # Output: 1 2 3
old_value = 2
new_value = 4
dll.update_node(old_value,
new_value)
print("Updated
list:", end=" ")
dll.display() # Output: 1 4 3
```
In both examples,
a doubly linked list is created, elements are inserted, and then the list is
updated by replacing a node with a specific value with a new value. The
`updateNode` method (C++) and `update_node` method (Python) handle the update
process, and the `display` method is used to print the elements in the list for
verification.
--------------------------------------------------------
Basic operation of
Two Way link list in C++ and python
examples of basic
operations on a Two-Way Linked List (Doubly Linked List) implemented in C++ and
Python. The operations include insertion at the beginning, insertion at the
end, deletion, traversal, and searching.
C++ Example:
#include
<iostream>
struct Node {
int data;
Node* prev;
Node* next;
};
// Function to
insert a new node at the beginning
void
insertAtBeginning(Node*& head, int value) {
Node* newNode = new Node{value, nullptr,
nullptr};
if (head != nullptr) {
newNode->next = head;
head->prev = newNode;
}
head = newNode;
}
// Function to
insert a new node at the end
void
insertAtEnd(Node*& head, int value) {
Node* newNode = new Node{value, nullptr,
nullptr};
if (head == nullptr) {
head = newNode;
return;
}
Node* tail = head;
while (tail->next != nullptr) {
tail = tail->next;
}
tail->next = newNode;
newNode->prev = tail;
}
// Function to
delete a node with a specific value
void deleteNode(Node*&
head, int target) {
if (head == nullptr) {
return;
}
Node* current = head;
while (current != nullptr &&
current->data != target) {
current = current->next;
}
if (current == nullptr) {
// Node with target value not found
return;
}
if (current->prev != nullptr) {
current->prev->next =
current->next;
} else {
head = current->next;
}
if (current->next != nullptr) {
current->next->prev =
current->prev;
}
delete current;
}
// Function to
traverse and print the list
void
traverse(Node* head) {
Node* current = head;
while (current != nullptr) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
// Function to
search for a node with a specific value
Node* search(Node*
head, int value) {
Node* current = head;
while (current != nullptr &&
current->data != value) {
current = current->next;
}
return current;
}
int main() {
Node* head = nullptr;
insertAtBeginning(head, 3);
insertAtBeginning(head, 2);
insertAtBeginning(head, 1);
std::cout << "Doubly Linked List
after insertAtBeginning: ";
traverse(head); // Output: 1 2 3
insertAtEnd(head, 4);
insertAtEnd(head, 5);
std::cout << "Doubly Linked List
after insertAtEnd: ";
traverse(head); // Output: 1 2 3 4 5
deleteNode(head, 3);
std::cout << "Doubly Linked List
after deleteNode(3): ";
traverse(head); // Output: 1 2 4 5
Node* searchResult = search(head, 2);
if (searchResult != nullptr) {
std::cout << "Node with
value 2 found." << std::endl;
} else {
std::cout << "Node with
value 2 not found." << std::endl;
}
return 0;
}
------------------------------------
Python Example:
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
# Function to
insert a new node at the beginning
def
insert_at_beginning(head, value):
new_node = Node(value)
new_node.next = head
if head:
head.prev = new_node
return new_node
# Function to
insert a new node at the end
def
insert_at_end(head, value):
new_node = Node(value)
if not head:
return new_node
tail = head
while tail.next:
tail = tail.next
tail.next = new_node
new_node.prev = tail
return head
# Function to
delete a node with a specific value
def
delete_node(head, target):
current = head
while current and current.data != target:
current = current.next
if not current:
# Node with target value not found
return head
if current.prev:
current.prev.next = current.next
else:
head = current.next
if current.next:
current.next.prev = current.prev
return head
# Function to
traverse and print the list
def
traverse(head):
current = head
while current:
print(current.data, end=" ")
current = current.next
print()
# Function to
search for a node with a specific value
def search(head,
value):
current = head
while current and current.data != value:
current = current.next
return current
# Example Usage
head = None
head =
insert_at_beginning(head, 1)
head =
insert_at_beginning(head, 2)
head =
insert_at_beginning(head, 3)
print("Doubly
Linked List after insert_at_beginning:", end=" ")
traverse(head) # Output: 3 2 1
head =
insert_at_end(head, 4)
head =
insert_at_end(head, 5)
print("Doubly
Linked List after insert_at_end:", end=" ")
traverse(head) # Output: 3 2 1 4 5
head =
delete_node(head, 3)
print("Doubly
Linked List after delete_node(3):", end=" ")
traverse(head) # Output: 2 1 4 5
search_result =
search(head, 2)
if search_result:
print("Node with value 2 found.")
else:
print("Node with value 2 not
found.")
output:-
Doubly Linked List
after insert_at_beginning: 3 2 1
Doubly Linked List
after insert_at_end: 3 2 1 4 5
Doubly Linked List
after delete_node(3): 2 1 4 5
Node with value 2
found.
These examples
demonstrate the basic operations on a Two-Way Linked List in both C++ and
Python.
----------------------------------------------------
Example: This algorithm
traverses the doubly linked list, searching for a node with the target value.
Once found, it updates the data field of that node with the new value.
C++ example:-
#include
<iostream>
struct Node {
int data;
Node* prev;
Node* next;
};
// Function to
update the value of a node in the doubly linked list
void
updateNodeValue(Node* head, int target, int newValue) {
Node* current = head;
while (current != nullptr) {
if (current->data == target) {
current->data = newValue;
std::cout << "Node with
value " << target << " updated to " <<
newValue << "." << std::endl;
return;
}
current = current->next;
}
std::cout << "Node with value
" << target << " not found." << std::endl;
}
// Function to
traverse and print the doubly linked list
void
traverse(Node* head) {
Node* current = head;
while (current != nullptr) {
std::cout << current->data
<< " ";
current = current->next;
}
std::cout << std::endl;
}
int main() {
Node* head = nullptr;
// Inserting nodes at the beginning
for (int i = 3; i >= 1; --i) {
Node* newNode = new Node{i, nullptr,
head};
if (head != nullptr) {
head->prev = newNode;
}
head = newNode;
}
std::cout << "Doubly Linked List
before update: ";
traverse(head); // Output: 1 2 3
// Updating the value of a node
int target = 2;
int newValue = 10;
updateNodeValue(head, target, newValue);
std::cout << "Doubly Linked List
after update: ";
traverse(head); // Output: 1 10 3
return 0;
}
-------------------------------------
Python Example:
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
# Function to
update the value of a node in the doubly linked list
def
update_node_value(head, target, new_value):
current = head
while current:
if current.data == target:
current.data = new_value
print(f"Node with value
{target} updated to {new_value}.")
return
current = current.next
print(f"Node with value {target} not
found.")
# Function to
traverse and print the doubly linked list
def
traverse(head):
current = head
while current:
print(current.data, end=" ")
current = current.next
print()
# Example Usage
head = None
# Inserting nodes
at the beginning
for i in range(3,
0, -1):
new_node = Node(i)
new_node.next = head
if head:
head.prev = new_node
head = new_node
print("Doubly
Linked List before update:", end=" ")
traverse(head) # Output: 1 2 3
# Updating the
value of a node
target = 2
new_value = 10
update_node_value(head,
target, new_value)
print("Doubly
Linked List after update:", end=" ")
traverse(head) # Output: 1 10 3
In these examples,
the updating operation is performed by traversing the doubly linked list and
modifying the data field of the node with the target value.
-----------------------------------------------------------------
Advantage of Two
Way link list
Two-Way Linked
Lists (Doubly Linked Lists) offer several advantages over their singly linked
counterparts. Here are some of the key advantages:
1. Bidirectional
Traversal:
- The bidirectional nature of the list
allows for easy traversal in both forward and backward directions. This makes
it more flexible than singly linked lists, where backward traversal is not
straightforward.
2. Efficient
Insertion and Deletion at Both Ends:
- Insertion and deletion operations at both
the beginning and end of the list are more efficient compared to singly linked
lists. This is because, in a doubly linked list, you have direct access to the
previous node, making these operations faster.
3. Ease of
Reversal:
- Reversing a doubly linked list is more
straightforward compared to a singly linked list. The bidirectional pointers
simplify the process of reversing the direction of the links.
4. Simplifies
Certain Algorithms:
- Algorithms that involve both forward and
backward traversal or require access to both adjacent nodes benefit from the
bidirectional nature of doubly linked lists. Examples include algorithms for
searching, sorting, and manipulation of data.
5. Support for
Tail-to-Head Traversal:
- In addition to forward and backward
traversal, doubly linked lists easily support tail-to-head traversal. This can
be useful in certain scenarios or algorithms.
6. Efficient
Deletion of a Node:
- Deleting a node in a doubly linked list is
more efficient compared to a singly linked list, especially when you have a
reference to the node being deleted. In a singly linked list, you would need to
traverse to the previous node to update its "next" pointer.
7. Simplifies
Implementation of Data Structures:
- Certain data structures, like stacks and
queues, can be implemented more efficiently using doubly linked lists. For
example, implementing a deque (double-ended queue) is natural with a doubly
linked list.
8. Memory
Utilization:
- Although doubly linked lists have a higher
memory overhead due to the additional "prev" pointers, they can
provide better memory utilization in certain scenarios where backward traversal
is essential.
9. Improved Error
Handling:
- The bidirectional links make it easier to
handle errors or special cases during traversal and manipulation. For example,
when deleting a node, checking for the presence of the previous and next nodes
is more straightforward.
10. Simplifies
Algorithms with Backtracking:
- Algorithms that involve backtracking,
such as undo operations or algorithms that need to traverse in reverse order,
can be more efficiently implemented using doubly linked lists.
-------------------------------------------------------------
Disadvantage of
Two Way link list
While Two-Way
Linked Lists (Doubly Linked Lists) offer several advantages, they also come
with certain disadvantages that need to be considered in specific scenarios.
Here are some of the disadvantages of Two-Way Linked Lists:
1. Increased
Memory Overhead:
- Doubly linked lists require additional
memory for the "prev" pointer in each node, effectively doubling the
storage requirements compared to singly linked lists. This increased memory
overhead can be a concern in memory-constrained environments.
2. Complexity in
Implementation:
- Implementing operations on doubly linked
lists is more complex than on singly linked lists. Managing two pointers (next
and prev) in each node adds complexity to insertion, deletion, and traversal
operations.
3. Higher Cost of
Storage:
- The additional pointers in doubly linked
lists result in a higher cost of storage per node. This can be a consideration
in applications where minimizing memory usage is crucial.
4. Increased
Initialization Overhead:
- Initializing a doubly linked list involves
setting both "next" and "prev" pointers. This increased
initialization overhead may be a concern in scenarios where rapid
initialization is required.
5. Additional
Maintenance of Pointers:
- The bidirectional nature of the list
requires careful maintenance of both "next" and "prev"
pointers during insertion, deletion, and other operations. Ensuring the
consistency of these pointers adds to the complexity of the code.
6. Slower
Traversal Speed:
- While doubly linked lists allow
bidirectional traversal, the speed of traversal can be slower compared to
singly linked lists due to the additional pointer manipulation. However, the
impact on traversal speed might not be significant in many cases.
7. Greater
Probability of Memory Fragmentation:
- The bidirectional nature and additional
pointers in doubly linked lists can increase the likelihood of memory
fragmentation, especially in scenarios with frequent insertion and deletion
operations.
8. Potential for
Pointer Corruption:
- Having two pointers in each node increases
the chances of pointer corruption or inconsistencies. Ensuring proper
synchronization and error handling becomes crucial to maintain the integrity of
the list.
9. Higher
Initialization Time:
- Initializing a doubly linked list,
especially when there are a large number of nodes, may take more time compared
to initializing a singly linked list due to the additional pointer assignments.
10. Overhead in
Simple Linear Traversal:
- In scenarios where simple linear
traversal in one direction is sufficient, the bidirectional pointers of doubly
linked lists introduce unnecessary overhead without providing additional
benefits.
---------------------------------------------------------------
Applications of
Two Way link list
Two-Way Linked
Lists, also known as Doubly Linked Lists, find applications in various
scenarios due to their bidirectional nature and advantages. Some common
applications include:
1. Text Editors:
- Doubly linked lists are often used in text
editors for implementing features like undo and redo operations. The
bidirectional traversal allows efficient navigation through the sequence of
edits.
2. Browser
History:
- Browser history functionality, where the
user can navigate forward and backward through visited web pages, can be
implemented using a doubly linked list.
3. Music Player
Playlist:
- Playlists in music players can be
implemented using doubly linked lists. Users can traverse the playlist in both
forward and backward directions, facilitating navigation and editing.
4. Undo/Redo
Mechanisms:
- Many applications, including graphic
design software and document editors, implement undo and redo functionalities
using doubly linked lists to keep track of changes.
5. File System
Operations:
- Doubly linked lists are used in file
systems to maintain a directory's structure efficiently. They facilitate
operations like navigation through directories and file manipulation.
6. Task Management
Systems:
- Task management applications often use
doubly linked lists to represent tasks. Users can traverse the list to view
tasks, mark them as complete, or reorder them.
7. Cache
Implementation:
- Doubly linked lists are used in the
implementation of caches. The bidirectional traversal allows for efficient
removal of the least recently used items.
8. Database
Management Systems:
- In database systems, doubly linked lists
can be used to represent certain data structures, aiding in efficient traversal
and manipulation of data records.
9. Symbol Tables
and Compilers:
- Symbol tables in compilers can be
implemented using doubly linked lists to efficiently manage identifiers and
their associated information during the compilation process.
10. Dynamic Memory
Allocation:
- Doubly linked lists are used in dynamic
memory allocation strategies, such as the implementation of free lists in
memory management systems.
11. Deque
(Double-Ended Queue):
- Doubly linked lists provide a natural
implementation for double-ended queues, allowing efficient insertion and
deletion at both ends.
12. Data
Structures for Algorithms:
- Doubly linked lists are used in the
implementation of certain advanced data structures, such as skip lists and some
types of advanced hash tables.
13. Graph
Algorithms:
- In graph algorithms, doubly linked lists
can be used to represent adjacency lists efficiently, facilitating operations
like depth-first and breadth-first traversals.
14. Simulation
Systems:
- Simulation systems often use doubly
linked lists to represent event queues, enabling efficient insertion and
removal of events in chronological order.
15. Dynamic Data
Structures:
- Doubly linked lists are versatile and can
be used in scenarios where dynamic data structures are required, and efficient
traversal in both directions is necessary.
===============================================================
0 Comments