INTRODUCTION OF TWO-WAY LINK LIST

 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.

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

------------------------------------------

 

 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

-------------------------------------------------------

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

--------------------------------------------------------

 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

-------------------------------------------------

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

-----------------------------------------------

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 the 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 the 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

----------------------------------------------------------------------------------------

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

----------------------------------------------------------------------

 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:

 

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 the forward direction

    void traverseForward() {

        Node* current = head;

        while (current) {

            std::cout << current->data << " ";

            current = current->next;

        }

        std::cout << std::endl;

    }

 

    // Traverse the list in the 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 the forward direction

    def traverse_forward(self):

        current = self.head

        while current:

            print(current.data, end=" ")

            current = current.next

        print()

 

    # Traverse the list in a 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

 

-------------------------------------------

 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.")

------------------------------------

 

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 it 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

--------------------------------------------------------

 

The basic operation of Two Way link list in C++ and python

 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

 

-----------------------------------------------------------------

Advantage of The 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.

**************************************************************************

 

Post a Comment

0 Comments