Skip to main content

Print node in forward and backward direction in doubly linked list

The problem addressed here involves printing the nodes of a doubly linked list in both forward and backward directions. A doubly linked list is a data structure where each node contains a value and two pointers, one pointing to the next node (in the forward direction) and another pointing to the previous node (in the backward direction). The objective is to traverse and print the linked list's nodes in both directions.

Problem Statement

Given a doubly linked list, the task is to print the nodes in two directions:

  1. Forward Direction: Print the nodes in the order they appear in the list, from the first node to the last node.
  2. Backward Direction: Print the nodes in the reverse order, starting from the last node and going towards the first node.

Idea to Solve

To solve this problem, the code needs to iterate through the linked list in both forward and backward directions. For each direction, the code will start from the respective end of the list (front for forward direction and rear for backward direction) and traverse the list using the next pointer for forward and the back pointer for backward.

Pseudocode

Here's the pseudocode that outlines the algorithm to print nodes in both forward and backward directions in a doubly linked list:

class LinkNode:
    int key
    LinkNode next
    LinkNode back

class DoublyLL:
    LinkNode front
    LinkNode rear

    function addNode(value):
        Create a new node with the given value
        If front is null:
            Set front to the new node
        Else:
            Set new node's back to rear
            Set rear's next to the new node
        Set rear to the new node

    function forwardDirection():
        If front is null:
            Print "Empty linked list"
            Return
        Print "Forward Direction Nodes"
        Initialize a temp node with front
        While temp is not null:
            Print temp's key
            Move temp to temp's next

    function backwardDirection():
        If rear is null:
            Print "Empty linked list"
            Return
        Print "Backward Direction Nodes"
        Initialize a temp node with rear
        While temp is not null:
            Print temp's key
            Move temp to temp's back

Create a DoublyLL object
Add nodes to the object
Call forwardDirection function
Call backwardDirection function

Algorithm Explanation

  • The addNode function adds a new node to the end of the linked list. If the list is empty, it updates both the front and rear pointers.
  • The forwardDirection function traverses the linked list from front to rear using the next pointer and prints the node values.
  • The backwardDirection function traverses the linked list from rear to front using the back pointer and prints the node values.

Program List

Time Complexity

  • Adding a node at the end of the linked list takes O(1) time.
  • Printing nodes in either direction requires traversing all nodes, taking O(N) time, where N is the number of nodes in the list.




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment