The course book is Data Structures and Problem Solving Using Java, by Mark Weiss, 4th edition. It teaches both how to design data structures and how to take advantage of them in programming. There is a website where you can download all the example code from the book.
Other interesting books, some of them free to read online
One of the real classic computer science books is Programming Pearls by Jon Bentley, and it’s very relevant for the course. It’s a collection of articles, most of them describing an imaginative solution to some programming problem. It’s also a) well written, b) quite short and c) quite cheap. If you read it you will be a better programmer!
If you want to brush up on your Haskell skills, try Learn You a Haskell for Great Good. You can read it free online. It’s got cartoons and everything!
Real World Haskell is also good, and also free to read online, but has XML instead of cartoons. :(
For data structures in functional languages, the classic reference is Chris Okasaki’s book, Purely Functional Data Structures. Instead of buying the book, you can download his PhD thesis, which contains much of the same stuff.