Best Data Structures Book

J

jehugaleahsa

Hello:

I got tired of trying to find good implementations of collections and
other data structures in C#. So, I started implementing my own.

However, data structures is a wholly different process in C# compared
to C++. I have to be a lot more careful about dangling pointers to
make sure things don't get pushed into further GC generations.

When I started learning about Comparer and similar classes, I got a
little worried that I am walking in the dark.

Is there a list of things I should be aware of when implementing data
structures in C#? Is there a decent book that covers implementation
details?

Is it possible to implement an efficient Doubly-Linked list without
creating an iterator class? (Just asking)

So far I have implemented an ArrayList<T>, LinkedList<T>, HashTable<K,
V>, BinarySearchTree<T>, Heap<T>, Stack<T>, Queue<T>, and
PriorityQueue<T>. I thought I would stop now before going back becomes
a nightmare.

Should my HashTable really be a HashTable<T>?

Thanks,
Travis
 
?

=?ISO-8859-1?Q?Arne_Vajh=F8j?=

I got tired of trying to find good implementations of collections and
other data structures in C#. So, I started implementing my own.

However, data structures is a wholly different process in C# compared
to C++. I have to be a lot more careful about dangling pointers to
make sure things don't get pushed into further GC generations.

When I started learning about Comparer and similar classes, I got a
little worried that I am walking in the dark.

Is there a list of things I should be aware of when implementing data
structures in C#? Is there a decent book that covers implementation
details?

Is it possible to implement an efficient Doubly-Linked list without
creating an iterator class? (Just asking)

So far I have implemented an ArrayList<T>, LinkedList<T>, HashTable<K,
V>, BinarySearchTree<T>, Heap<T>, Stack<T>, Queue<T>, and
PriorityQueue<T>. I thought I would stop now before going back becomes
a nightmare.

Should my HashTable really be a HashTable<T>?

Why not just use those that comes with .NET ??

Arne
 
R

raylopez99

So far I have implemented an ArrayList<T>, LinkedList<T>, HashTable<K,
V>, BinarySearchTree<T>, Heap<T>, Stack<T>, Queue<T>, and
PriorityQueue<T>. I thought I would stop now before going back becomes
a nightmare.

Should my HashTable really be a HashTable<T>?


I second Arne's comment, that you should use the generics that come
with .NET. THey have stuff like Queue, Deque, and everything you have
except PriorityQueue. And they don't have an N-ary tree (tree with N
branches per node, unbalanced), which I built myself.

RL
 
D

Doug Semler

Hello:

I got tired of trying to find good implementations of collections and
other data structures in C#. So, I started implementing my own.

However, data structures is a wholly different process in C# compared
to C++. I have to be a lot more careful about dangling pointers to
make sure things don't get pushed into further GC generations.

When I started learning about Comparer and similar classes, I got a
little worried that I am walking in the dark.

Is there a list of things I should be aware of when implementing data
structures in C#? Is there a decent book that covers implementation
details?

Is it possible to implement an efficient Doubly-Linked list without
creating an iterator class? (Just asking)

So far I have implemented an ArrayList<T>, LinkedList<T>, HashTable<K,
V>, BinarySearchTree<T>, Heap<T>, Stack<T>, Queue<T>, and
PriorityQueue<T>. I thought I would stop now before going back becomes
a nightmare.

Should my HashTable really be a HashTable<T>?

Alrighty. You sure created alot of work for yourself <G>: .NET 2 has
the following in the System.Collections.Generic namespace:

LinkedList<T>: Your doubly linked list
Queue<T>, Stack<T>: self explanitory
List<T>: basically a self-expanding array
Dictionary<TKey, TValue>: Hashtable with bucket location determined by
key hash.
SortedList<TKey, TValue>: implemented as 2 array lists sorted based on
keys. Searching for the key uses binary search.
SortedDictionary<TKey, TValue>: Implemented as a binary tree

There are a couple of others in System.Collections.ObjectModel:
ReadOnlyCollection, Collection, and KeyedCollection.

MSDN is your friend.
 
M

Mads Bondo Dydensborg

Hello:

I got tired of trying to find good implementations of collections and
other data structures in C#. So, I started implementing my own.

Did you have a look at the c5 lib by Sestoft et. al?

http://www.itu.dk/research/c5/

Article in dr dobbs:
http://www.ddj.com/dept/windows/199902700

The docs is at http://www.itu.dk/research/c5/Release1.0/ITU-TR-2006-76.pdf

Without knowing the competition very well, I think this is a very solid
collection library for C#.

Regards,

Mads

However, data structures is a wholly different process in C# compared
to C++. I have to be a lot more careful about dangling pointers to
make sure things don't get pushed into further GC generations.

When I started learning about Comparer and similar classes, I got a
little worried that I am walking in the dark.

Is there a list of things I should be aware of when implementing data
structures in C#? Is there a decent book that covers implementation
details?

Is it possible to implement an efficient Doubly-Linked list without
creating an iterator class? (Just asking)

So far I have implemented an ArrayList<T>, LinkedList<T>, HashTable<K,
V>, BinarySearchTree<T>, Heap<T>, Stack<T>, Queue<T>, and
PriorityQueue<T>. I thought I would stop now before going back becomes
a nightmare.

Should my HashTable really be a HashTable<T>?

Thanks,
Travis

--
Med venlig hilsen/Regards

Systemudvikler/Systemsdeveloper cand.scient.dat, Ph.d., Mads Bondo
Dydensborg
Dansk BiblioteksCenter A/S, Tempovej 7-11, 2750 Ballerup, Tlf. +45 44 86 77
34
 
A

Andreas Mueller

Hello:

I got tired of trying to find good implementations of collections and
other data structures in C#. So, I started implementing my own.

However, data structures is a wholly different process in C# compared
to C++. I have to be a lot more careful about dangling pointers to
make sure things don't get pushed into further GC generations.

When I started learning about Comparer and similar classes, I got a
little worried that I am walking in the dark.

Is there a list of things I should be aware of when implementing data
structures in C#? Is there a decent book that covers implementation
details?
Well, you definitely should have the "Knuth" on you desk:
http://tinyurl.com/yslfr2
http://tinyurl.com/24nzb4
Is it possible to implement an efficient Doubly-Linked list without
creating an iterator class? (Just asking)
Yes. But why? .NET 2.0 comes with a good LinkedList said:
So far I have implemented an ArrayList<T>, LinkedList<T>, HashTable<K,
V>, BinarySearchTree<T>, Heap<T>, Stack<T>, Queue<T>, and
PriorityQueue<T>. I thought I would stop now before going back becomes
a nightmare.
LinkedList<T> said:
Should my HashTable really be a HashTable<T>?

Not that I was bored ;-), but rather the absence of some containers as
HashTable<T>, PriorityQueue<T> (which basically is a Heap), BinaryTrees
and standard algorithms persuaded me to port and adapt the SGI STL to
C#/.Net: http://www.codeplex.com/nstl.

Maybe you can use it or at least compare your implementations with it.

HTH,
Andy
 
J

jehugaleahsa

Why not just use those that comes with .NET ??

There are plenty of well-implemented data structures in C#, however,
they lack control over the underlying structure. I want to have Skip
Lists, AVL trees and B-Trees - possible many more in the future.

The whole point of generic data structures is the flexibility to find
what works best. I don't want what works best in general.
 
J

jehugaleahsa

Alrighty. You sure created alot of work for yourself said:
the following in the System.Collections.Generic namespace:

LinkedList<T>: Your doubly linked list
Queue<T>, Stack<T>: self explanitory
List<T>: basically a self-expanding array
Dictionary<TKey, TValue>: Hashtable with bucket location determined by
key hash.
SortedList<TKey, TValue>: implemented as 2 array lists sorted based on
keys. Searching for the key uses binary search.
SortedDictionary<TKey, TValue>: Implemented as a binary tree

There are a couple of others in System.Collections.ObjectModel:
ReadOnlyCollection, Collection, and KeyedCollection.

MSDN is your friend.- Hide quoted text -

- Show quoted text -

I know these classes already exist, but what fun is that? It becomes
more important to implement your own classes when developing compound
data structures where you want to mix things together to find what is
most efficient. Alrighty?
 
J

jehugaleahsa

Did you have a look at the c5 lib by Sestoft et. al?
http://www.itu.dk/research/c5/

Article in dr dobbs:http://www.ddj.com/dept/windows/199902700

The docs is athttp://www.itu.dk/research/c5/Release1.0/ITU-TR-2006-76.pdf

Without knowing the competition very well, I think this is a very solid
collection library for C#.

Regards,

Mads
Med venlig hilsen/Regards

Systemudvikler/Systemsdeveloper cand.scient.dat, Ph.d., Mads Bondo
Dydensborg
Dansk BiblioteksCenter A/S, Tempovej 7-11, 2750 Ballerup, Tlf. +45 44 86 77
34- Hide quoted text -

- Show quoted text -

I did look at the C5 library. It is an extremely flexible and well-
divided library. However, my classes need to have much more limited
interfaces and be sufficiently easier to understand. C5 complicates
things with their "code against interface, not implementation" or
whatever. It is a wonderful way to develop, don't take me wrong, it
just feels to overwhelming for the people I work with. Additionally it
lacks some DSs that I want.
 
J

jehugaleahsa

Well, you definitely should have the "Knuth" on you desk:http://tinyurl.com/yslfr2http://tinyurl.com/24nzb4

I have all three and some more modern algorithms/DS books that
actually cover newer creations like Skip Lists.
Yes. But why? .NET 2.0 comes with a good LinkedList<T>

Too much fun to not do it myself.

Not that I was bored ;-), but rather the absence of some containers as
HashTable<T>, PriorityQueue<T> (which basically is a Heap), BinaryTrees
and standard algorithms persuaded me to port and adapt the SGI STL to
C#/.Net:http://www.codeplex.com/nstl.

Maybe you can use it or at least compare your implementations with it.

I hope you did well. SGI has some incredible code. One of the aspects
I wish to bring to my libraries are iterators and an generic
algorithms library. However, there are issues when comparing
iterators, do to C# not having polymorphic operator overloads. bool
Equals(object obj) to the rescue!

I think I will enjoy looking at your library, thanks. (Finally,
someone who understands)
 
D

Doug Semler

I know these classes already exist, but what fun is that? It becomes
more important to implement your own classes when developing compound
data structures where you want to mix things together to find what is
most efficient. Alrighty?


Fun? Maybe not FUN, but why spend time reinventing the wheel? If you want
to understand *HOW* each of these things work, a good data structures book
that is programming language neutral is fine.

But you needed to say that in your OP. YOUR original post said that you
got tired of trying to find "good implementations" of collections in C#. It
sounded like you didn't know that the ones in the framework existed, and are
pretty good implementations of what they do. (yes, some have a small bit of
generalization) but they're otherwise OK.

I would wondering how much more efficient the collections that you
implemented are over the ones provided by the framework.

--
Doug Semler, MCPD
a.a. #705, BAAWA. EAC Guardian of the Horn of the IPU (pbuhh).
The answer is 42; DNRC o-
Gur Hfrarg unf orpbzr fb shyy bs penc gurfr qnlf, abbar rira
erpbtavmrf fvzcyr guvatf yvxr ebg13 nalzber. Fnq, vfa'g vg?
 
A

Andreas Mueller

I have all three and some more modern algorithms/DS books that
actually cover newer creations like Skip Lists.
Which one? A link would be appreciated :).
I hope you did well. SGI has some incredible code. One of the aspects
I wish to bring to my libraries are iterators and an generic
algorithms library. However, there are issues when comparing
iterators, do to C# not having polymorphic operator overloads. bool
Equals(object obj) to the rescue!
In C# and VB.NET, operator overload work and all my iterators implement
comparison operators. However, I recently came back to using static
object.Equals(object, object), as it the recommended way to do it and it
takes away the problem of a value being null :).
I think I will enjoy looking at your library, thanks. (Finally,
someone who understands)
I hope you do. Feedback is welcome :). I also would like to have a
glance at your implementation, if this would be possible.
Cheers,
Andy
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top