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

a circular linked list can be used for stack or queue

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.

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.

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.

• I can see `goToNextWagon()` and `goToPreviousWagon()` in the interface. Counting steps is hardly a problem.