How to structure a Predictive Keyboard project similar to GBoard
Markov Chains are great for putting out nonsense based on statistical data. However, a predictive keyboard that outputs nonsense isn't very useful. It needs much more context than a Markov Chain can produce. Such a program would base its next output entirely on the most recent entry. 

That said, a project to do something like the Mark V. Shaney program might be fun in an Introduction to Data Structures course. However, it is unlikely that students would have previously seen Markov Chains at that point in their studies so some background in that would also need to be incorporated. Markov Chains might be taught in a Discrete Math course, but that usually comes later. Some schools might teach these two courses in tandem, however, making it a bit more feasible. 

Such a project would, however, also have the advantage that the statistical basis (the Dictionary) used could introduce concepts of Big Data and how to process it. 

You are correct that a predictive keyboard uses past data, but I'm pretty sure that it is based on a much more complex predictive model than could be provided by a Markov Chain. "Predictive Keyboard based on Markov Chains" is probably an oxymoron, though. You can do either or, but likely not both together.