How could we count the elements inside a doubly linked list (circular list), where we do not know the initial state nor where is head / tail‽

circular doubly linked list c++
circular doubly linked list java
a circular linked list can be used for stack or queue
circular doubly linked list deletion
circular doubly linked list python
circular linked list python
circular linked list java
queue using circular linked list

I am doing the following programming exercise: How many Wagons Are in the Train?. The statement is:

You are in a Train that is permanentely moving in a circle.The Train is looped: The head is connected with the tail and you can go from on to another directely.

Every Wagon has a light. The initial status of the lights is not known. You can switch it on or off if you wish.

Count the Number of Wagons!

You can move between wagons as you wish.

Contraints. After you count the Wagons, the lights in the train should be in the initial state. But at the end you dont need to be in the same Wagon where you started.

Use the implemented Train methods:

public boolean isLightOnInCurrentWagon()

public void switchLight()

public void goToNextWagon()

public void goToPreviousWagon()

Train notation "1 : 0 : 0" means that you have a train with three Wagon. The light is on in the first Wagon and off in the other two.

First I thought to keep three lists of Integers, original, switched and final. Original would store lights as they were at start. Switched would store original's complement (after switching each wagon's light). Final would have the lights as original (after switching back to the original state).

For example for train: 1:0:1

Original: {1,0,1}
Switched: {0,1,0}
Final: {1,0,1}

However the difficulty is, how we know where is the head / start of then train?

In addition I attempted some code for the base case, where the train has just one wagon:

import java.util.*;
public class Solution {
    public int howManyWagons/*🚂❔🤔*/(Train train){
      int haveWeEnded = 0, prev = 0, first = 0, next = 0;
      if(train.isLightOnInCurrentWagon()){
        first = 1;
      }
      System.out.println("first: "+first);
      train.switchLight();
      train.goToNextWagon();
      if(train.isLightOnInCurrentWagon()){
        next = 1;
      }
      System.out.println("next: "+next);
      train.switchLight();
      train.goToPreviousWagon();
      if(first != next){
        train.switchLight();
        train.goToPreviousWagon();
        if(train.isLightOnInCurrentWagon()){
          prev = 1;
        }
        System.out.println("prev: "+prev);
        train.switchLight();
      }
      return prev == next && first != prev && first != next ? 1 : 0;
    }
}

Being the test cases (taken from the challenge):

import org.junit.jupiter.api.Test;

import java.util.Random;

import static org.junit.jupiter.api.Assertions.*;

class SolutionTest extends Train {

    Solution sol = new Solution();
    Random rand = new Random();

    @Test
    void howManyWagonsCornerCases() {

        String repr;
        Train train;

        repr = "1";
        train = Train.fromRepr(repr);
        assertEquals(1, sol.howManyWagons(train), repr);

        repr = "1 : 0 : 1 : 0 : 0";
        train = Train.fromRepr(repr);
        assertEquals(5, sol.howManyWagons(train), repr);

        repr = "1 : 0 : 0";
        train = Train.fromRepr(repr);
        assertEquals(3, sol.howManyWagons(train), repr);

        repr = "1 : 1 : 0 : 0 : 1 : 1";
        train = Train.fromRepr(repr);
        assertEquals(6, sol.howManyWagons(train), repr);

        repr = "0 : 0 : 0 : 0 : 0";
        train = Train.fromRepr(repr);
        assertEquals(5, sol.howManyWagons(train), repr);

        repr = "1 : 1 : 1 : 1 : 1";
        train = Train.fromRepr(repr);
        assertEquals(5, sol.howManyWagons(train), repr);


        repr = "1 : 0 : 1 : 0 : 0 : 1 : 1 : 0 : 0";
        train = Train.fromRepr(repr);
        assertEquals(9, sol.howManyWagons(train), repr);
    }


}

So when there is just one wagon, it does count it. However how could we make this general? Because of if we have 5 wagons (second test), as: "1 : 0 : 1 : 0 : 0", the code outputs:

first: 1
next: 0
prev: 0

Because of it detects the same patterns as if it were just one wagon, s then it returns 1 instead of 5.

Plus, I have read:

How could we count the elements inside a doubly linked list (circular list), where we do not know the initial state nor where is head / tail‽

EDIT: Using @Chamika answer I tried to explain how is the thought process which creates the algorithm

import java.util.*;

public class Solution {
  public int howManyWagons/*🚂❔🤔*/(Train train){
    boolean end = false;
    int count = 1;
    while(!end){
      //💡 We save the light of the initial wagon to be able to reset it later
      boolean isFirstWagonLightOn = train.isLightOnInCurrentWagon();
      //🕳️ We turn off the light of the initial wagon, to mark ⛳ where we started this iteration
      if(train.isLightOnInCurrentWagon()){
        train.switchLight();
      }
      goForward(train,count);
      //If the light is on 🔆, we know we are not in the initial wagon, we go to the initial wagon and count it
      if(train.isLightOnInCurrentWagon()){
        goBack(train,count);
        count++;
      //When the light is off 🕳️, we may have go back to the initial position
      }else{
        //We switch the light 🔲,go back
        train.switchLight();
        goBack(train,count);
        //If after going back the wagon light is on 🔆, it means we stand inside the end wagon
        if(train.isLightOnInCurrentWagon()){
          end=true;
        }else{
          //If light is off 🕳️, we have not been in the end position yet
          goForward(train,count);
          train.switchLight();
          goBack(train,count);
          count++;
        }
      }
      //Reset end position light
      if(isFirstWagonLightOn != train.isLightOnInCurrentWagon()){
        train.switchLight();
      }
    }
  return count;
  }

  public static void goForward(Train train,int count){
    while(count > 0){
      train.goToNextWagon();
      count--;
    }
  }
  public static void goBack(Train train,int count){
    while(count > 0){
      train.goToPreviousWagon();
      count--;
    }
  }
}

Ole V.V. Have provided an excellent solution for this problem and I implemented that algorithm in java.

public int howManyWagons(Train train){

  boolean end = false;
  int count = 1;

  while(!end){ 

    //save the state of the first wagon
     boolean isFirstWgonLightOn = train.isLightOnInCurrentWagon();

    //light off in the first wagon
    if(train.isLightOnInCurrentWagon()){
      train.switchLight();
    }

    //go n forward
    goFoward(train,count);

    if(train.isLightOnInCurrentWagon()){
      goBack(train,count);
      count++;
    }else{

       train.switchLight();
       goBack(train,count);

       if(train.isLightOnInCurrentWagon()){
         end=true;
       }else{

         //we need to reset the ligt state
         goFoward(train,count);
         train.switchLight();
         goBack(train,count);
         count++;

       }
    }

    //we need to reset to the initial state
    if(isFirstWgonLightOn != train.isLightOnInCurrentWagon()){
     train.switchLight();
    }

  } 
   return count;

}

Doubly Circular Linked List, Following is representation of a Circular doubly linked list node in C/C++: Insertion at the end of list or in an empty list T node and at last don't forget to shift 'Start' pointer to this T node. Find node having value2 and next node of it List can be traversed from both the directions i.e. from head to tail or� Circular Doubly Linked List. Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node. Circular doubly linked list doesn't contain NULL in any of the node. The last node of the list contains the address of the first node of the list.

Record the state of the light in the current wagon. Then in a loop where candidateWagonCount goes from 1 to infinity (or to Integer.MAX_VALUE) see whether there are candidateWagonCount wagons in the train. This check proceeds as follows:

  1. Set light off.
  2. Move candidateWagonCount wagons forward. If the light is on, we know that there cannot be candidateWagonCount wagons in the train. Move candidateWagonCount back to your original position and go to the next iteration.
  3. If the light is off, we may have come back to our starting point. Now move candidateWagonCount wagons back to where we know we started. Set light on. Again move candidateWagonCount wagons forward. If the light is now on, we know that we have returned to the starting point. Hence there must be candidateWagonCount wagons in the train. Set the light to its original state (on or off) and exit. Otherwise move candidateWagonCount wagons back to your starting position.

Happy coding.

As I see it, the difficulty is not knowing where the start or end is, because there isn’t any since the train is circular. You may just as well decide to consider the position where you start the start of the train.

The challenge to me was how we could know when we had made a full circle. If we just move in one direction through the train, even when we recognize a pattern of lights that we had left earlier, we don’t know whether we have come back or we have come to a new series of wagons that happens to have the same pattern. The solution is to take the same steps both after leaving a certain light off and after leaving it on.

Write a function that counts the number of times a given int occurs in , C++ program to count occurrences in a linked list Given a reference (pointer to pointer) to the head Counts the no. of occurrences of a node Start with the empty list */ Check the count function */ given element k Your browser does not currently recognize any of the video formats available. Q #1) Can the Doubly Linked List be circular? Answer: Yes. It is a more complex data structure. In a circular doubly linked list, the previous pointer of the first node contains the address of the last node and the next pointer of the last node contains the address of the first node. Q #2) How do you create a Doubly Circular Linked List?

Start two pointers, p1 and p2, at the same wagon initially. Leave p1 at that wagon and move p2 through the train one wagon at a time, counting the steps. Stop when p2 returns to the same wagon that p1 is still pointing at.

When p2 moves, if the wagon light is different from the light at p1, then p2 is at a different wagon. If the lights are the same, then flip the light at p2. If the light at p1 is unchanged then p2 is at a different wagon. If the light at p1 changes when you flip p2 then the two pointers are back pointing at the same wagon. Check how far p2 has moved to see how long the train is.

ETA (thanks Mad Physicist): Declare two wagons instead of two pointers. Leave w1 (=p1) fixed and move w2 (=p2). Assuming they start at different points on the train move w2 until flipping w2's light shows it is at the same wagon as w1. Then follow the same idea as above.

Counting how far w2 moved will let you jump start counting the length of the train -- those wagons are known not to be w1.

Circular Linked List | Data Structure Tutorial, Array � Linear Linked List � Circular Linked List � Double Ended Queue � Stack In the circular linked list we can insert elements anywhere in the list whereas in the to the previous Head, whether it be NULL(in case of new List) or the pointer to If the Linked List is not empty then we find the last node, and make it' next to � The last node has a reference to null. In a linked list the entry point is called the head of the list. In Circular Doubly Linked List two consecutive elements are linked or connected by previous and next pointer and the last node points to first node by next pointer and the first node also points to last node by previous pointer. Algorithm

Python Linked Lists, Generally speaking, a list is a collection of single data elements that are connected via which you can find by following the pointers from one node to the next. A single-linked list can be traversed from head to tail whereas traversing the nodes in both directions at the same cost, no matter which node you start with. Given a circular linked list, count number of nodes in it. For example, the output is 5 for below list. Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Linked list, In computer science, a linked list is a linear collection of data elements whose order is not given Linked list are dynamic, so the length of list can increase or decrease as necessary. The 'head' of a list is its first node. The 'tail' In the case of a circular doubly linked list, the first node also points to the last node of the list. List can be traversed from both the directions i.e. from head to tail or from tail to head. Jumping from head to tail or from tail to head is done in constant time O(1). Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap .

[PDF] Linked List Problems, It's easy to find linked list algorithms that are complex, and pointer intensive. They are short to state, and Even if you do not succeed, you will think through the right issues in the attempt, and looking at the A single head pointer points to the first node in the list. struct node* tail = &dummy; // Start the tail at the dummy. Both Singly Linked List and Doubly Linked List can be made into a circular linked list. Singly Linked List as Circular. In singly linked list, the next pointer of the last node points to the first node. Doubly Linked List as Circular. In doubly linked list, the next pointer of the last node points to the first node and the previous pointer of

Comments
  • There are also CS.SE posts containing size+circular and length+circular.
  • Thanks, @greybeard, for the pointers. This question actually seems to answer the question asked here.
  • @greybeard I didn't downvote. I did wonder whether we should give full working code away, or the questioner would learn more or have greater pleasure from writing his or her own code. My guess would be that a similar thought was behind the downvote. This answer is accepted, which denies the concern in this particular case (I still think it is valid in general).
  • Very nice answer
  • The interface does not appear to support this.
  • (The interface being you moving from wagon to wagon, changing direction ad nauseam, losing count…)
  • I can see goToNextWagon() and goToPreviousWagon() in the interface. Counting steps is hardly a problem.