Posted on by Kalkicode

# 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. ## 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
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.

## 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.

Categories
Relative Post