Posted on by Kalkicode
Code Doubly linked list

Count frequency of given node in doubly linked list

The problem involves counting the frequency of a given node in a doubly linked list. A doubly linked list is a data structure in which each node contains a data element and two pointers, one pointing to the next node and another pointing to the previous node. The task is to determine how many times a specific data value appears in the list.

Count frequency of doubly linked list node

Problem Statement

Given a doubly linked list and a target data value, the objective is to count how many times the target value appears in the linked list.

Example

Consider the following doubly linked list:

7 <-> 2 <-> 3 <-> 4 <-> 5 <-> 3 <-> 7 <-> 3

If we want to count the frequency of the value 3, the result should be 3, since the value 3 appears three times in the list.

Idea to Solve

To solve this problem, you need to traverse the entire doubly linked list while maintaining a count of how many times the target value appears. During traversal, check if the data value of each node matches the target value. If it does, increment the count. After traversing the entire list, the count will represent the frequency of the target value in the linked list.

Pseudocode

function frequency(key):
    result = 0
    temp = head
    while temp is not null:
        if temp.data equals key:
            increment result by 1
        move temp to the next node
    print "Frequency of node " + key + " is : " + result

Algorithm Explanation

  1. Initialize a variable result to store the frequency count and set it to 0.
  2. Start traversing the doubly linked list from the head node using a temp pointer.
  3. While the temp pointer is not null:
    • Check if the data value of the current node (temp.data) equals the target value (key).
    • If they are equal, increment the result by 1.
    • Move the temp pointer to the next node in the linked list.
  4. After traversing the entire linked list, print the frequency count along with the target value.

Program Solution

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the doubly linked list. This is because, in the worst case, you need to traverse through all the nodes once to count the frequency of the given value.

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