Java – I need a data structure for a card game

algorithmsdata structuresjava

I am programming a card game in java, and unsure what data structure I should use for the player's hand.

I considered using an array, with one integer to traverse the array and another integer to increment and decrement the size of the player's hand. However, if a player removes a card from the middle of the array, then the array will have a hole in it.

I could shift the position of every subsequent card towards the 1 element of the array and decrement the integer that keeps track of the players hand — but this seems insufficient. I also considered a linked list.

Does anyone have a better suggestion for a data structure or insight about the two ideas that I have?

Best Answer

There are a couple things to think about here - the structure of a card and the structure of the collection of cards... and all the while keeping in mind that this is Java and should be written with proper attention to object oriented principles.

A card is a thing. Representing it entirely as a bit in a BitSet, or worse... doing your own bit manipulation and passing around a long really takes you away from those object oriented principles. You're instead dealing with "I've got bit 23 thats a jack of hearts" makes for some ugly coding. Iterating over a bitset or bits set in a long isn't at all fun either. So, lets put that to rest - a bit isn't a card isn't a thing.

There are approaches based on this that aren't wrong for Java. It is not unreasonable to stick all of the cards in an enum:

public enum Card {
  ACE_OF_HEARTS,
  TWO_OF_HEARTS,
  ...
  KING_OF_SPADES
}

You could then use an EnumSet as the collection. Yes, its backed by a BitSet when you dig into it, but it's a nice collection to deal with. It's actually a Collection (a BitSet isn't) and so you get the iterators and contains and the like. A BitSet, you're doing your iteration by hand calling nextSetBit(5) to find out what the index of the next set bit.

I won't say that the enum with all the cards in it is wrong, but it isn't right either. If you read the tutorial on enums from Oracle, you even find...

import java.util.*;

public class Card {
    public enum Rank { DEUCE, THREE, FOUR, FIVE, SIX,
        SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE }

    public enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES }

    private final Rank rank;
    private final Suit suit;
    private Card(Rank rank, Suit suit) {
        this.rank = rank;
        this.suit = suit;
    }

    public Rank rank() { return rank; }
    public Suit suit() { return suit; }
    public String toString() { return rank + " of " + suit; }

    private static final List<Card> protoDeck = new ArrayList<Card>();

    // Initialize prototype deck
    static {
        for (Suit suit : Suit.values())
            for (Rank rank : Rank.values())
                protoDeck.add(new Card(rank, suit));
    }

    public static ArrayList<Card> newDeck() {
        return new ArrayList<Card>(protoDeck); // Return copy of prototype deck
    }
}

And you've got a deck backed by the ArrayList.

Here's a thing to think about though. You can't have two jack of hearts in your hand... well, some games you might, but most games you don't. This means a collection of cards is a Set. This gives you a few options for how to implement the hand in such a way that doesn't mean juggling arrays.

I'd start with a LinkedHashSet as that maintains dealt order, or you might prefer either the TreeSet or ConcurrentSkipListSet if you want the cards to be in sorted order. Note that this isn't as useful for dealing the cards from a deck as you would want that to be in a List because Collections.shuffle takes a list as arguments. You also don't have to worry about pulling cards out of the middle of the deck when dealing. So the LinkedList would work very nicely for the deck itself when dealing cards (see pollFirst if you want to do it that way).

Some games though, you may find that you need to keep it in a deque (such as a LinkedList - so you get the poll first and last). Others you want to keep the cards in a sorted structure, or others you may want something else. It all depends on what you want to do and finding the correct Collection (or not) to do it.

However, the data structure for a card should be that of the card presented by Oracle in the enum tutorial. And then you use the Collection that maps to how you want to hold the cards.

Related Topic