Fog Creek Software
Discussion Board




Which data type would you prefer here?

PS: This time, the link provided is not an EXE or a ZIP file. It is another HTML page.

I wanted to practice some Linked List stuff, so I set out to create a linked list. The  plan was to create the following:

(1) A linked list class in Visual Basic
(2) A non-class based linked list using functions in C
(3) A linked list class in C++

I started with Visual Basic and I wrote an IList interface that I wanted my list to  implement. When I had started, somehow I thought this time, I'd first use a  collection as the ingredient, and so it would not really be a linked list. It would be  an extended collection behaving like a (not linked, but just a) list, as in list of  things. And my new agenda would then be,

(1) A list (not a linked list) class in Visual Basic by extending the Collection object.
(2) A linked list class in Visual Basic
(3) A linked list in Visual Basic that is not class-based but has a struct (Type) and  global functions in a standard module (.bas).
(4) A non-class based linked list using functions in C
(5) A linked list class in C++

I don't like to create lists if they have no meaning, so I thought it would be a good  idea if the list was a list of something and not just "ints". So, I made a list of my  friends here; a list of JoS members. I called the list MyFriends.

I have just finished implementing a list by extending the Visual Basic's Collection  object. My list has the following interface:

[CODE]
Public Function AddAtPos(ByRef Object As Object, _
ByVal Index As Long) As Boolean
End Function

Public Function PeekAtPos(ByVal Index As Long) As Object
End Function

Public Function RemoveAtPos(ByVal Index As Long) As Boolean
End Function

Public Property Get Count() As Long
End Property

Public Function Contains(Object As Object) As Boolean
End Function

Public Function IndexOf(Object As Object) As Long
End Function

Public Sub Serialize()
End Sub

Public Sub Deserialize()
End Sub

Public Sub Clear()
End Sub

Public Sub Sort(ByVal SortOrder As SortOrders)
End Sub

Public Sub Reverse()
End Sub
[/CODE]

If you're interested, you can find the source code and the executable for my first  experiment here. http://www.vbforums.com/showthread.php?s=&threadid=303400

Now, I am set to implement item number (2) in my agenda - the linked list class in  Visual Basic. Once again, the semantics remain the same. I intend to keep the list  as a list of friends. So each node in the list is a friend. While designing the "node"  class or the "MyFriend" class, I stumbled accross this problem. I am recording two  pieces of information about each friend:

(1) Name
(2) Phone Number

Both are of String type. The problem was not with these, but with the "node  pointer" item. I have three data types in mind that I can use to point to the next  node. I am confused as to which one would be a good choice, and I want your  opinion on the same.

Here's what I have thought the node/MyFriend class as:

[B]MyFriend Class[/B]
[CODE]
Implements IList

Private mName As String
Private mPhoneNumber As String

'===Which one do I choose?=======
'Private mNextFriend As MyFriend
'        OR
'Private mNextFriend As Long
'        OR
'Private mNextFriend() As Byte
'==================================
[/CODE]

Let me argue each case, as I thought about them. Starting with the last, if I take  the mNextFriend field as a Byte array, it would help me....do nothing, basically.  So, ruled out.

Next, if took the mNextFriend field as a Long, I think it would be the ideal thing  to do, because VB6 Long's are indeed 32-bit values, and then I would use the  mNextFriend Long field to point to a new instance of MyFriend type, using the  ObjPtr function. I would dereference the mNextFriend Long type by using  RtlMoveMemory. That sounds like a nice plan. However, the problem with this is  that it does not strictly confirm to a Linked List set up, because of the generic  nature of this Long pointer. This pointer could be used to point not only to  MyFriend types but to anything. Since I am going to be the developer audience  for this class, and hence this is only dogfood, it is no problem, but in general, I  don't like it as a habit and I always want my code to represent what it ought to  represent. So, this would be like compromising on a trivial issue.

If I use mNextFriend as a MyFriend type, I solve the problem of the generic  pointer by restricting it to the MyFriend type. So, it's more disciplined this way,  but now, the field is not really a pointer. It is an object. Of course, it is still a 32-bit  reference to the actual object, but it is still not a real pointer.

So, I am confused. If you were to be doing this, what option would you choose  and why? To me, the Long seems like ok, although it is a little bit of a  compromise on the type-checking.

Sathyaish Chakravarthy
Thursday, September 02, 2004

Ask your Comp Sci 101 teacher.

Mr. O
Thursday, September 02, 2004

Mr.O.

It's not like I am learning these things the first time. I was asking for opinion, trying to start a serious discussion. If you don't have anything to say, just move on.

Sathyaish Chakravarthy
Thursday, September 02, 2004

"If I use mNextFriend as a MyFriend type, I solve the problem of the generic  pointer by restricting it to the MyFriend type. So, it's more disciplined this way,  but now, the field is not really a pointer. It is an object. Of course, it is still a 32-bit  reference to the actual object, but it is still not a real pointer."

AFAIK, that's one of the points of working in VB - to avoid dealing with some of the stuff you have to deal with in other languages/tools.

If you want to deal explicitly with pointers, move on to your next steps - C/C++.

Anyway, answering your question, this is the option that makes more sense to me. The "Long" option smells too much of a hack, IMHO.

Paulo Caetano
Thursday, September 02, 2004

me vote myFriend type

Kenny
Thursday, September 02, 2004

The part that uses 'ObjPtr' is fraught with peril.  You would be using a function whose only use should be to get around problems you can't solve any other way.

It should be the first solution -- of type MyFriend.

By the way, I usually use 'My' as a prefix for local data items.  I would NEVER use it as a prefix for a class name.  I want my class names to be more generic than that.

I would want in the future to have a variable named MyFriend, of class Friend.

Also, when building linked lists, for the link data items, or accessor methods, I tend to use 'Next' and 'Prev'.

AllanL5
Thursday, September 02, 2004

Oh, and when your link field is a reference to an object, that's what it is SUPPOSED to be.  You are not supposed to jump through hoops to get a 'real' pointer in there.

AllanL5
Thursday, September 02, 2004

"[...] the field is not really a pointer. It is an object. [...] not a real pointer."

It is not an object, it is a pointer (or reference) to an object.

The "VB way" would be to declare it as MyFriend.

bpd
Thursday, September 02, 2004

Sathyaish,

I recall from a previous thread that you are curious about linked lists as a concept and you have never implemented one.

Trying to implement one in VB will obscure the essence of a linked list with typecasting and other mechanical garbage. You need to work with pointers to "see" what a linked list is doing.

May I suggest an alternative approach: implement one in C. Use a non GUI approach like writing to the console using printfs() in order to see what things look like internally.

In other words, select the tool(s) that will support learning rather than cluttering things up with a tool that isn't intended for the purpose.

And lastly, it will be extremely easy to find examples of simple linked lists on the net coded in C or C++.

I suggest that just doing it will be more instructive than putting all your incremental design decisions up for a group vote.

It's the way I learned many moons ago, and it's quite effective...

Bored Bystander
Thursday, September 02, 2004

I hate to drag in a possible irrelevacy, but what happens if your friend moves house - meaning: hardwired addresses (pointers) are OK if nobody moves.

Consider the classic Bill of Materials schema:

Parent|child|qty

vs

Parent#|child#|qty


The former is more robust, but slower to execute.
The latter more fragile, but potentially much faster.

You're the designer, you choose.
PS which maps to SQL faster?

trollop
Thursday, September 02, 2004

Hi BB,

I agree with all that you have said. In fact, what I am doing is on purpose. I have read the code for linked lists in C already, and from more than three different books and a few places on the Net. I learnt about linked lists in the year 1996. I even taught a limited syllabus of C++, which also covered a chapter on linked lists, back in 1999. But I must admit, I do not know C++ well. I have code samples too. But I am doing this excercise because I want to see how it is going to be trying to simulate one where there is no support. Then, the plan is to do the straight-forward C code for the linked list. Next, will be a C++ class.

And for C, as you have suggested, I'd already thought that I would first do a console app to test the linked list, because otherwise I would need to code a lot of UI in Win32 (which I know well) or MFC (which I don't know very well).

I know pointers well. What I am doing is an experiment. May be I don't have the words to explain. It's more like knowing something but still having a feeling of insecurity that you do not know much. There is more to be known. I want to master these concepts well. May be, at a sub-conscious level, I am doing these things over and over again as a preparation for my goal - to work at Microsoft.

I posted this question because I was really divided in opinion over two of the three data types there. My plan after this is to practice the implementation of a hash table. Then I would move to the sorting algorithms (I mostly use Bubble Sort and Selection Sort, though I know a few others). Then, to compression and encryption, and so on.

BTW, I have to still ask you a few questions on the previous thread. Only they are not in the forefront of my mind as of yet.

Sathyaish Chakravarthy
Thursday, September 02, 2004

> May be, at a sub-conscious level, I am doing these things over and over again as a preparation for my goal - to work at Microsoft.

Someone told me that a reason why MS use "linked list" questions in their interviews is because a lot of the O/S code is written in C (which only old-timers know). So, Sathyaish, if you apply to Microsoft, will you be applying for a job writing O/S-level code?

He also said that if you apply via HR, they receive a mountain of resumes and might take a year to get back to you: so, better to "fast track" your resume, by giving it to a hiring manager via someone who already works there.

.
Thursday, September 02, 2004

It's good that you're trying to learn this on your own, but wouldn't it be a more effecient use of your time to take CS101 & 102?  That pretty much covers the topics you describe. 

Lee
Thursday, September 02, 2004

Thanks, dot. Actually, as a matter of fact, I have already applied to Microsoft. I applied in June this year and I have already have a HR phone interview from the recruiter. I am awaiting my next phone interview.

No, I dare not apply for a position that would entail writing OS level code. I applied for the position of a Programming Writer - a someone who writes documentation for the next version of Visual Basic, and also some code.

Sathyaish Chakravarthy
Thursday, September 02, 2004

A slight typo here:

>I have already have a HR phone interview from the recruiter

I have already had a HR phone interview from the recruiter

Sathyaish Chakravarthy
Thursday, September 02, 2004

>It's good that you're trying to learn this on your own, but wouldn't it be a more effecient use of your time to take CS101 & 102?  That pretty much covers the topics you describe.

Yes, it would. But I can't leave my day job. But I've read all the PDFs from the Stanford University CS website. And I have two good books on data structures that I read a little by little when I get the time. Besides that, I have K&R, which I have never crossed the 6th chapter of, because each line of that book is pregnant with meaning. And I don't want to miss out implementing anything in that book. In that book, I am stuck at the Polish Notation because I don't like it very much.

Besides, that I have a lot of books on C, including one by Balaguruswamy, two books by Yashwant Karnetkar (Let Us C), one book on Johnathan Morrisson (C++ for Visual Basic programmers), and many more. I've read a few of these already.

And I can write Win32 API programs well even without using a client such as Visual Basic. I love Win32 API very, very, very much. But them, the Win32 API is a platform and not a language, though it is implemented in C.

Sathyaish Chakravarthy
Thursday, September 02, 2004

Space is not a premium anymore.  Use the biggest data type, and give yourself the best possible option for upgrade in the future, as space is not getting smaller.  All databases support large integers now, and the SQL INTEGER is the VB Long anyways. 

The User/User# problem will always be present.  When I am designing a system from scratch, I pick the artsy "pretty code" way (User#).  However, a lot of systems are fully integrated with User, so you'd better be prepared to make a temp table to handle the associations, etc.

devinmoore.com
Thursday, September 02, 2004

I wasn't really talking about the backend issues here, but thanks anyways. As you can see,

http://www.vbforums.com/attachment.php?s=&postid=1777300

I don't perist the list to a database. I serialize it to an INI instead.

Sathyaish Chakravarthy
Thursday, September 02, 2004

"each line of that book is pregnant with meaning. "

That is a beautiful quote.

A.M.
Thursday, September 02, 2004

"each line of that book is pregnant with meaning. "

Agreed. My favourite is the last line on p92:

#endif

Almost Shakespearean in its understated eloquence.

K&R fan
Thursday, September 02, 2004

Sathyaish, I for one find your earnestness and enthusiasm very refreshing. As long as you have that you will go far.

ronk!
Thursday, September 02, 2004

>Sathyaish, I for one find your earnestness and enthusiasm very refreshing. As long as you have that you will go far.

Thank you, ronk. It was very kind of you to say that. When I need motivation, I come back to words like these, and I am rejuvinated.


>That is a beautiful quote.

Yes. I like that phrase. I read it in a book a long time ago. From then, I say it when I need to. When someone tells me something that I think has a lot of meaning to it, I tell them that what they just said was pregnant with meaning.



>Agreed. My favourite is the last line on p92:
>#endif
>Almost Shakespearean in its understated eloquence.

You're my guy! Of all the #endif's that are so sweet, that one endif, the most extolled, sounds the most melodious; that one endif calls to me, and it lives on page 92. It's got the Shakespearian sound, as you say. Enddddddiffff...what a rythm! Like it were an iamb. That #endif on p92 is being talked about a lot these days on comp.lang.c. And I believe Nostradamus also devoted a quatran to the #endif that was going to be written on page 92. He said it would unite two war-waging super powers.


I recieved an email from a user on this board called "A Friend". He sent me a link to a book on data structures and algorithms. I sent my thanks to him by replying to his email but I guess his email was fake, so I'd like to thank him here. A Friend, thanks so much for that book. It means so much to me.

Sathyaish Chakravarthy
Friday, September 03, 2004

*  Recent Topics

*  Fog Creek Home