Member Avatar for arkanoid

I have been working on a number of card games. Important, of course, is shuffling the deck. I have come up with a few different ways to do this. Currently I do not shuffle, but to deal a card, I lay out the deck in order, selecting a random number between 1 and the number of cards remaining and selecting that card. I then remove that card from the deck so that another card can be picked.

There are two main ways to do this, and I am trying to figure out which one is optimal.

The first is to have an array of cards. When one card is dealt, a new array is formed with that card missing. I kind of like keeping the array size exactly the size of the deck, but perhaps this is not efficient. So, the first array has length n and the new array after the card is dealt has length n-1. VB.Net makes it simple to change array sizes around like this.

The second method is to use a linked list for the deck of cards. This makes removing a card fairly swift, aside from the list traversal to get to the place where the card is to be removed.

Is the time taken to traverse a linked list comparable to the time taken to recreate an array or does one greatly outweigh the other?

arkanoid

  • 1 Contributor
  • 1 Reply
  • 197 Views
  • 12 Hours Discussion Span
  • Latest Post Latest Post by arkanoid
Member Avatar for arkanoid

I have been working on a number of card games. Important, of course, is shuffling the deck. I have come up with a few different ways to do this. Currently I do not shuffle, but to deal a card, I lay out the deck in order, selecting a random number between 1 and the number of cards remaining and selecting that card. I then remove that card from the deck so that another card can be picked.

There are two main ways to do this, and I am trying to figure out which one is optimal.

The first is to have an array of cards. When one card is dealt, a new array is formed with that card missing. I kind of like keeping the array size exactly the size of the deck, but perhaps this is not efficient. So, the first array has length n and the new array after the card is dealt has length n-1. VB.Net makes it simple to change array sizes around like this.

The second method is to use a linked list for the deck of cards. This makes removing a card fairly swift, aside from the list traversal to get to the place where the card is to be removed.

Is the time taken to traverse a linked list comparable to the time taken to recreate an array or does one greatly outweigh the other?

arkanoid

It seems that Insertion and Removal are order O(1) with linked lists, so these are probably ideal. I just can't get over the idea that it has to travel down the list to get to the place to do the work.

The other method seems to be O(n^2/2)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.