One of the first questions I came up with yesterday when digging into F# was this: what does an F# type look like to C#? As a noob, that's an interesting question to me. Of course, being a noob, I had no clue about how to create a custom type. So, I asked Google what an F# type definition looked like, then massaged that until I had something that I might not completely understand, but that does show the problem at hand. I created a lame Name class that only supports a first name. Boo-yah!

First, I went to an existing file in an F# library called stuff.fs. There, I added the following class:

For you C# heads out there, let's look at what the code above really is saying.

• Create a new type, Name.
• Name has a single constructor that takes a string.
• Name has a member variable, fName, whose value can change at runtime.
• Name has a public property, FName, that has a getter and a setter.

OK, so now what does this look like in C#? I add the F# library to a C# project, instantiate a copy of Stuff.Name (I'll get to the Stuff item in a moment), and then I right click on Stuff.Name and pick Go to Definition. Since we are in C# land, VS 2008 will pull up the C# vision. This looks exactly like the following:

That's kind of weird. I didn't expect to see Name declared as a inner class from a static class whose name comes from the name of the F# file. Still, that's what we have. Does this mean that F# code doesn't allow one to create CLR namespaces? No-- of course not! So, how do you get the Name class into a CLR namespace called SomeNamespace? I did a little digging and found out how:

Yeah-- there's a keyword called namespace that allows you to add objects to a CLR namespace. The odd bit here is that one doesn't say namespace blah =. Instead, you omit the '='. The '=' will work, but you will get a message saying that the syntax has been deprecated. With this small change in place, things look more correct to my C# eyes. The static class disappears, and that's good!

Right now, I think my focus will be on writing F# code that plays well/looks natural to C# developers. I'll keep that point of view until I see a reason to change.

A long while back, I mentioned that my wife, Jean, and I were looking at starting up a company. Well, we've done a lot of thinking about what the product should do and how this should be done. Because of other recent activities, I haven't had a lot of time to execute on the idea. The fact of the matter is that we still like the underlying concept, but the implementation concept has morphed several times since we had the idea. The biggest changes are these:

1. F#: A VS2010 language (currently in Beta)
2. Azure: A Cloud platform

F# is a functional .NET language. I've always been a fan of functional programming as it typically allows me to write my applications using fewer lines than what I would do in pure imperative mode. For better or worse, imperative languages are still center stage (and have been for decades). In order to pay the bills, it is easier to find work using C++/C#/Java than using LISP/Prolog/Scala. However, with F# (an OCaml based language), we have a chance of seeing functional programming go mainstream. I have a project in mind that needs a .NET language, so why not use the project as a means to really get into F#.

The second thing that happened is the beta release of Azure at the 2008 PDC. A big concern of mine has been hosting the set of servers that will eventually be needed if the web site idea takes off. Yes, I'm familiar with how to make sites scalable, how to buy a server, etc. I'm also familiar with the fact that more servers means more people I'd have to hire who may or may not have the chops to manage a large-ish web site. The cloud stuff is very appealing to me as it allows someone who worries only about managing servers do whatever that is. I can then focus on conserving space, writing better algorithms, and paying a smaller price to keep that service up and running (yeah, I'm assuming that, like other managed services, the cost of going to the cloud is less that the cost of personnel + equipment + power + licensing).

So, until I either lose interest or get so swamped with work/life/whatever, expect to see the blog focus on F# and Azure stuff. Right now, I'm a noob.

For anyone who read this thing, I apologize for the long break. Between my last post and now, I wrote a book with my good friend, Kenn Scribner. The book, Effective REST Services via .NET, is currently in the technical review stage. This means that some really smart people are reviewing the book and letting Kenn and I know where things don't make sense or are just wrong. Kenn was asked to write this book back in July of 2008 after developing a bunch of samples and other content for the folks involved with WCF/Oslo. Kenn then asked me to collaborate with him and I accepted.

Anyhow, writing a book removes any drive I might otherwise have to blog. Now that I'm able to get things done in smaller chunks based on the reviews that are flowing in, I have the writing bug back again.

I haven't been completely out-- if you want to see what I've been writing up for my day job, check out the MySpace developer blog. I'm one of several contributors there, posting as "Scott".

If you do any work with LINQ, you have to go out and buy the LINQ Pocket Reference by Joseph and Ben Albahari, ISBN 978-0-596-51924-7, O’Reilly. It’s a tiny, 160 page book that will literally fit into the back pocket of your jeans. I love it, use it whenever I'm doing LINQ stuff. It's a permanent fixture on my desk and in my laptop bag. Just go buy it, now! It's $10.19 at Amazon. If you program for .NET, there is no excuse to NOT own this book. Skip lunch today if you need to budget for the money.

I found this in the forums, but it wasn't super easy to dig out. Hopefully, this post will help someone find things a bit easier.

Symptoms: You can't access a site on local IIS after installing Visual Studio 2008 IIS on Vista or later.

Event log at Windows Logs\System will have an entry that reads as follows:

Log Name: System

Source: Microsoft-Windows-WAS

Date: 8/18/2008 2:24:10 PM

Event ID: 5189

Task Category: None

Level: Error

Keywords: Classic

User: N/A

Computer: xxxx

Description:

The Windows Process Activation Service failed to generate an application pool config file for application pool '*'. The error type is '0'. To resolve this issue, please ensure that the applicationhost.config file is correct and recommit the last configuration changes made. The data field contains the error number.

Event Xml:

<Event xmlns="http://schemas.microsoft.com/win/2004/08/events/event">

<System>

<Provider Name="Microsoft-Windows-WAS" Guid="{524B5D04-133C-4A62-8362-64E8EDB9CE40}" EventSourceName="WAS" />

<EventID Qualifiers="49152">5189</EventID>

<Version>0</Version>

<Level>2</Level>

<Task>0</Task>

<Opcode>0</Opcode>

<Keywords>0x80000000000000</Keywords>

<TimeCreated SystemTime="2008-08-18T19:24:10.000Z" />

<EventRecordID>79948</EventRecordID>

<Correlation />

<Execution ProcessID="0" ThreadID="0" />

<Channel>System</Channel>

<Computer>xxxx</Computer>

<Security />

</System>

<EventData>

<Data Name="AppPoolID">*</Data>

<Data Name="ErrorType">0</Data>

<Binary>90040780</Binary>

</EventData>

</Event>

This is caused by SP1 incorrectly updating applicationHost.config. To fix, do the following:

1. Open an administrative command prompt.
2. Type in: notepad %windir%\system32\inetsrv\config\applicationHost.config
3. Add this text at /configuration/configSections/sectionGroup[@name=system.applicationHost]/

   <section name="configHistory" overrideModeDefault="Deny" />

4. Save applicationHost.config
5. Close Notepad
6. In the administrative command prompt, type in: iisreset /start

For reference, the sectionGroup in applicationHost.config should look like this:

<sectionGroup name="system.applicationHost">

<section name="applicationPools" allowDefinition="AppHostOnly" overrideModeDefault="Deny" />

<section name="customMetadata" allowDefinition="AppHostOnly" overrideModeDefault="Deny" />

<section name="listenerAdapters" allowDefinition="AppHostOnly" overrideModeDefault="Deny" />

<section name="log" allowDefinition="AppHostOnly" overrideModeDefault="Deny" />

<section name="sites" allowDefinition="AppHostOnly" overrideModeDefault="Deny" />

<section name="webLimits" allowDefinition="AppHostOnly" overrideModeDefault="Deny" />

<section name="configHistory" overrideModeDefault="Deny" />

</sectionGroup>

The original source of some of this information is: http://forums.microsoft.com/TechNet/ShowPost.aspx?PostID=2859933&SiteID=17.

CNUG.org sent this to me, and I'm passing it on as a member of LCNUG.org. This will be a lot of fun for Chicago area developers!

What: Chicago Day of Dot Net/Chicago Tech Fest (Name to be decided)

When: September 6^th 2008 – 8:30 am – 5:00 pm

Where: Wheaton IIT

Overview

The Chicago area .Net based users groups are looking for speakers for our forth coming conference on September 6th.

This is a one day event that will be hosted by located at The Illinois Institute of Technology (IIT) Wheaton Campus and is a free, community based event. This means we are looking for both seasoned speakers as well as ones trying to get their feet wet. Our sessions will last between 1 – 1.5 hours and are meant to teach and enlighten the audience.

We are in process of planning a great day of learning and we need your help. We are looking for energetic, charismatic, passionate and engaging speakers. If this is you, we want you to help us out. We need your passion towards software development to fill our session slots. We are planning on having 5-6 tracks with 5 sessions per track (25-30 total sessions).

Possible areas of interested are
.Net based technologies (Linq, .Net 3.5, Asp.Net, Smart Client, MVC)

Agile techniques (TDD, BDD, DDD, CI)

MOSS/Sharepoint

User Experience

Biztalk

XNA

TFS

If you are someone who would like to present, please send the following information to Keith Franklin (KeithF@Magenic.com).

Your Name

Company

Email

Phone:

Session Name

Session Abstraction

My wife and I have had ideas for different ventures over the years. Because we always had a youngster in the house and not in school, we focused a lot on making the years before school started as happy years. This Fall, our youngest enters full day Kindergarten in Lake Villa, IL. This means that Mom and I will finally be able to get one or two of these ideas off the ground. We like the idea of an arrangement where I act as Architect on most projects and as a developer as needed. To this end, we are launching Friseton.com. Jean and I got to name the titles we wanted. She's the president of the company. She's been in charge of running the household for the last 13 years, so this title just seems right. I always liked the idea of a Chief Software Architect. Bill Gates gave himself that title when he stepped down as Microsoft's CEO.

This doesn't mean I get to quit my day job. We don't have the resources to do this and, quite frankly, I don't know that any of our ideas will ever generate that kind of income. We are hoping for something that will generate enough revenue to pay expenses and allow us to save for a more comfortable retirement. The current crop of ideas centers around things we would like to make available to charities so that they can run more efficiently. We are on the committees for a few different charities and know what we wish we had access to for coordination and collaboration. Our goal is to make something that helps all the issues one runs into and charge enough to make the services generate a positive cash flow within 18 months of our initial deployment. If annual net revenue ever got to $50,000 US, we'd be thrilled.

I'll post news and update as we progress. Right now, Jean and I are learning SilverLight 2.0. She's quite a bit ahead of me on this one, so it's likely she'll handle the UI portion of the site. You can check out where we are at by keeping tabs on www.friseton.com. If you subscribe to this blog, I promise that I'll post updates as we make progress. At this point, the site represents a total of 60 minutes time in Powerpoint (to generate the banner) and VS 2008.

The site is hosted over at www.crystaltech.com. We have a developer account setup now. I have to say that I really like the admin tools they have. This is far better than others I have used. That said, I've only hosted through Verio and GoDaddy. Verio and GoDaddy were ok. CrystalTech has developed a web interface that is extremely easy to navigate. I've read almost no documentation and figured out how to setup e-mail accounts, FTP, etc. I like the fact that I don't have to think too hard in order to get stuff working.

Tonight, I ran into a scenario where adding the SqlTrackingService to my WorkflowRuntime set of services caused the completion of a simple workflow to hang. To diagnose, I instructed Visual Studio to break when exceptions were thrown. With this, I was treated to a break in System.Data.Sql.SqlConnection.OnError. The SqlException being thrown stated "MSDTC on server '[machine name]' is unavailable." If you look, you'll see that MSDTC is a manual start service on Vista. To fix this issue, just start MSDTC in the Services Control Panel applet and run your workflow code again. You'll be treated to full tracing at this point.

Some friends recently saw my resume and asked about the 40+ languages that I claim to have written code in. Essentially, they asked why I have that claim and questioned if it was even factual. I have that claim because many employers want someone who knows 'Special Language X' in addition to all the other qualifications. In any interview, I usually explain this as follows: "I want to make it clear that no matter what odd wrinkle you have in your system, I know enough about languages and programming in general to tackle your special case."

Still, 40 sounds like a big number. How, exactly, did I arrive at that figure? First off, understand that many of the languages I have programmed in have had little more than two weeks of the following:

1. Learn the language. This involves finding a good tutorial and burning a day getting conversant. The language choice was frequently driven by either class work, larger system requirements, or "this looks like fun".
2. Write the application. Again, this might be "deliver a PHP web page," an assignment, or an interesting experiment.
3. Deliver the application.

I have used enough of these to know that learning a new language is something that one can do in a day or two. Mastering a new language and its toolset still takes some serious time—I would guess about 3000 hours of full time use prototyping, developing and debugging in that language. Many folks tend to learn a language by learning just enough to get by. In mastery, I would say that the person also actively tries to understand the language grammar, libraries, and how the language interacts with the systems it runs on. 3000 hours just getting stuff done will not allow for mastery.

With that in mind, I've probably only mastered a handful of languages:

1. C
2. C++
3. C#
4. Visual Basic (3.0à6.0)

For another set of languages, I'm just at the intermediate level. I define the intermediate level as this: the user can write moderately complex systems with minimal access to reference material. Code can be debugged, augmented, and generally 'read' with little to no difficulty. This encompasses a larger set of languages—some of which are cheating but included since I see so many places where things like each XML technology counts as a separate 'language':

1. Ada
2. ASP
3. ASP.NET
4. Basic (think QBasic and its relatives)
5. COBOL
6. DOS Batch programming
7. EcmaScript/JavaScript
8. FORTRAN
9. HTML
10. Java
11. Ladder Logic (programming Programmable Logic Controllers/PLCs)
12. SQL
13. Visual Basic.NET
14. WSDL
15. x86 Assembler
16. XML
17. XPath
18. XQuery
19. XSD

Finally, there are the languages I'm a beginner in. Let's define beginner as a language one can read and write with the assistance of the Internet and a good reference book. At some point, I have written at least a small application (~2 weeks of effort) in these languages:

1. LISP
2. MSIL
3. Bash shell
4. Eiffel
5. F#
6. Forth
7. FoxPro
8. Haskell
9. HyperTalk
10. JCL
11. Logo
12. Mathematica
13. Motorola Assembly
14. Objective C
15. OCaml
16. Pascal
17. Perl
18. PHP
19. PL/1
20. PowerShell
21. Prolog
22. Python
23. Ruby
24. Simula
25. SmallTalk

Is this a long list? Sure. But I also know of many folks who know far more than this. Consider any language designer or language geek. Many of these folks have actually mastered more languages than I've gotten to beginner on.

Finally, I want to take note of one recent observation. In the past 5 years, I have slowed down the pace at which I learn new languages. This is happening largely because C# and .NET are providing many of the facilities I would normally need to be more productive. C# 3.0 has added functional language features in the form of LINQ. Its libraries are surprisingly rich. .NET provides so many other features that I'm finding that its pace of innovation is keeping me busy enough without needing to look elsewhere to get the productivity gains I used to look for in other languages. .NET adds wonderful libraries, language features, and more at such a pace that I don't have time for learning language X when technologies like WPF and WF are beckoning to me.

Every once in a while, Visual Studio 2008 will lock up on me. When it was in beta and even after release, I ran into a situation where it put up a dialog saying "Blah blah blah" with the options:

• Switch to application
• Continue waiting

From someone, probably either directly from John Robbins or via one of the many blogs he has recommended through his presentations, I learned that this was being caused by a managed debugging assistant. Looking around on the web, it seems that this bug has been known for quite a while. Here is the issue and why it happens as explained by a Jim Stall from the Visual Studio team (link to post):

It is possible for this MDA to be falsely activated when all of the following conditions are met:
* An application creates COM components from STA threads either directly or indirectly through libraries.
* The application was stopped in the debugger and the user either continued the application or performed a step operation.
*Unmanaged debugging is not enabled.

The reasoning is that:
1) When you're stopped in the debugger while managed-only debugging, unmanaged threads are still running. This means that any unmanaged threads that are waiting on some timeout from managed code will continue to run. The unmanaged thread will see the timeout fire, but it won't realize that the managed thread is actually stopped by the debugger. Thus the managed thread looks it's deadlocked. This is not an issue when unmanaged debugging because then the timeout thread is also frozen when stopped in the debugger, and so the timeout won't fire.

2) The finalizer for an STA COM objects needs to run code on the STA thread. So there's some cross-thread stuff between the finalizer thread and the STA thread.

So the STA thread may be blocked by the debugger (since the whole managed process is frozen at a breakpoint), while the timeout check (on an unmanaged thread) is still ticking.

This is a race because it needs the finalization and debugger event to happen at just the right windows.
We assessed that this scenario as a rare situation. I'd expect you to see this only on very rare occasions (due to prerequisite timing issues).
If you are hitting this bogusly, one workaround is to disable this specific MDA.

Let's walk you through disabling the specific MDA, since this problem still exists and is not as rare as these guys think. I don't get the issue when debugging normally, but I will get it when I run Visual Studio as an admin. Running Visual Studio 2008 as admin is required if you want to deploy applications straight over to the same machine's IIS instance—something I do often enough. Note: I haven't run into this issue in a non-admin context in several months. I think the two conditions are somehow linked.

Please note—you have to run this sequence for every project. VS2008 will not remember your settings across invocations.

1. With an open project, go into the menus and select DebugàExceptions.
2. Expand the Managed Debugging Assistants node. You will see the following screen:

   

3. Select ContextSwitchDeadlock and uncheck it.
4. Click OK.

I hope this helps a few other brave souls out there.

Over the past month, I've finally taken the plunge and decided to finally read those classic technical books that everyone seems to have read (though that many have only skimmed). I've also been reading oddball classics that are recommended by acquaintances and folks in the know. As for the big classics that I've read since May 1:

• The Algorithm Design Manual by Steve Skiena
• Programming Pearls by Jon Bentley
• Peopleware by Tom DeMarco and Timothy Lister
• The Mythical Man-Month by Frederick Brooks

I've also been paging through my Knuth's again. Why, oh why would I be doing this? First off, I love the act of designing systems, writing code, and just geeking out in my chosen profession. Second, I know that I needed to read these classics so I could stop being an architect with no grounding in classic computer literature. I mean, I knew what the books were all about, but that was only through someone else's eyes, not my own. So, with this journey still in motion, what have I been learning?

First, I needed a refresher on my algorithms. I was able to get most of the exercises in Programming Pearls and Skiena with a little bit of thought and some time by a compiler. It felt good to go through Bentley's text and figure out the really advanced, best performing solutions to many problems. It was a morale boost to see that I could still figure this kind of thing out with just a little bit of effort.

From Peopleware, I took many ideas I have for this programming shop I want to start up 'someday' and refined the heck out of a bunch of ideas. For example, did you know that most people find performance reviews to be demotivating? I didn't. I thought I was the oddball that hates performance reviews and would prefer life much better if I never got another one. It turns out that no one likes these—they are stressful. Unfortunately, I also learned some things about businesses I've been introduced to in my area. There are a lot of poisonous businesses out there taking a great profession and turning it into something where you feel odd to be one of the following:

1. A proud, 36 year old developer. In my opinion, that's still young. Yet, many folks in the profession stop coding much before this age. I'm SOOOO glad I'm not one of those people.
2. Unwilling to ship because the quality bar is not only low, it doesn't exist. Apparently, the shipping feature matters even when things aren't right.
3. Unit testing is an OLD idea. JUnit, NUnit, and other unit testing tools are not new ideas. Shoot, Fred Brooks talks about unit testing going on for IBM back in the 1950s and 1960s. And yet, I still have a really hard time convincing folks that unit testing is important and it is an OLD idea. Unfortunately, fixing build breaks takes time when unit tests are present. They slow down development and make it take longer to get to the official test, file bug, fix, repeat cycle.

I find that my focus on my career is getting sharper. I'm seeing how I can make a difference, how to achieve it without stepping on toes and hurting feelings, and I'm seeing how fast people can be expected to change. People hate change and will only do so slowly when you are trying to move a group. People are more willing to change when they are being assimilated into a group—it feels better to be a part of the group than apart from the group. (yes, the use of 'a part' and 'apart' is intentional) At the moment, I'm trying to find a place where I can be a positive force for change and I need to make sure that I do this at a proper speed. If you know of a development shop that is top notch and just wants to get better, give me a call. I'd love to talk to you and find out what you are doing to make things happen.

I had a chance to see David Chappell speak at the Microsoft offices in Downers Grove this past week. If he is coming anywhere near you to talk on Software + Services, I recommend that you go see the talk. I've got a summary of what he covers here, but you've got to see him in person to get the talk. The man is an amazing communicator and helped me connect some dots that I hadn't quite connected in a while—whether that was due to sloth on my part of great speaking on David's part, I don't knowJ.

Anyhow, here's a few hundred words explaining some of what I got out of it.

Training Date: May 20, 2008, 1-4 PM

Location: Microsoft offices, Downers Grove, IL

Presenter: David Chappell, http://www.davidchappell.com/

Summary

The reliability of the Internet, relatively low cost of connectivity, and widespread presence of high bandwidth connections has provided a path for application architectures to evolve. Specifically, this set of changes allows application vendors to provide common applications to end users. Today, these common applications include e-mail, CRM, storage, web site hosting, mapping (ex. 1 Main St., Mundelein, IL), and database hosting. Providers host these services on the Internet, also called the 'cloud' by the software services community. These services commonly provide the following features:

• Data mobility: Consumers own their data and can change providers or move the data in house as needed.
• Application integration: The service in the cloud is part of a larger application used at the enterprise.
• Application customization: The service in the cloud may allow the consumer to customize the application to handle special business needs.

Two terms describe the different business models for the services in the cloud: Software as a Service, SaaS, and Software + Services, S+S. SaaS offers a complete software package in the cloud. SaaS instances may allow for integration and customization. SaaS does not provide much of a role for corporate IT departments outside of application development. S+S describes a hybridization between today's common model of self-hosting applications and the SaaS world. SalesForce.com offers an example of a SaaS application. SalesForce.com manages all the data, the application uptime, etc. An S+S example is a bit more involved, but probably more common for businesses as it allows for control of the perceived competitive advantages of a business.

S+S includes the types of applications that use cloud services as well as custom, in-house services. For example, a business could host Exchange Server locally but make use of a service provider to handle advanced Exchange functionality such as Outlook Web Access, web calendaring, or discussion lists.

With terminology and ideas covered, what else does a business need to look out for? The business should evaluate the service provider in the same way that they would evaluate a packaged, installable software. Beyond that the consumer needs to decide if the service meets their needs.

In both packaged software and services, one must look at how the vendor is trying to lock in the consumer. This lock in happens in different ways. They may lock down data, making it difficult to move to a new vendor. They may also create a platform type of lock in. The platform lock in can cause many different kinds of problems. If the lock in is through the tooling and programming languages, a consumer may find it difficult to port customizations to equally good platforms. Likewise, it may prove difficult to find reasonably priced developer talent. For example, SalesForce.com uses the Apex programming language. Apex is specific to SalesForce.com and isn't commonly available elsewhere. Other tools, like Microsoft Dynamics CRM and Google Apps, use common extension languages, allowing for a larger developer pool. Microsoft Dynamics uses .NET based languages and Google Apps uses Python.

I have a friend who teaches Computer Science. One of the things we've discussed is the need for students/entry level hires to really understand basic data structures. This is true even though most popular languages do the basic ones quite well (linked list, hashtable, queue, stack). A consequence of these things being in most languages is that many of today's students aren't being required to actually build these data structures as part of their education. Many problems in the work place involve situations where one needs to know the characteristics of the data structure in order to implement the most efficient algorithms. One acquires this knowledge through actually building the data structures at least once.

I believe that many of the folks who grew up programming for the web are getting to a point where their script skills will need to fill in these gaps in their education. Browser apps are approaching desktop applications in terms of presentation, interactivity, and capability. The next step in the evolution of browser applications will require developers to have knowledge of the basic data structures and their variance implementation options. The reason: unlike the desktop languages we all use, the browser's programming language, JavaScript, doesn't have any of these. (If I'm mistaken, let me know!)

Right now, I'm reviewing the data structures and algorithms that I learned during the first two years of college. I'm also trying to bring myself up on my level of understanding JavaScript. I think that some of these diversions might prove interesting to the world at large. Today, I've implemented a linked list. A linked list has the following characteristics:

1. Add at the front or end of the list takes O(1) time.
2. Extraction of the nth element takes O(n) time.
3. Insert at a given position, k, takes O(k) time.
4. Delete at a given position, k, takes O(k) time.

Linked lists are effective when typical usage of the list is in scanning all elements. A linked list is 'nice' to memory management. That is, the room needed for the list + one more linked list node is:

Z = (size of node) = ((size of data) + (reference to next node))

(total memory in use when adding a node) = Z x (number of nodes + 1)

This is an improvement over the typical JavaScript Array type whose worst case characteristics for adding one more element to the list is

Z = (size of node) = (size of data)

(total memory needed when adding a node) = Z x ((2 + growth size) x number of nodes)

In many algorithms for array growth, the algorithm calls for a doubling of the array's allocated memory. The reason that so much memory is required is that arrays require contiguous memory in order to maintain O(1) lookup time at any given element.

A Doubly Linked List Implementation

A doubly linked list is a list that one can use to go both forward and backward from one node to the next. To accomplish this, I've created three classes:

function LinkedListNode() {

}

LinkedList.LinkedListNode = {

Data: null,

Next: null,

Previous: null

};

LinkedListNode keeps track of the data, the Next, and the Previous nodes. The algorithms involved all assume that the linked list Next and Previous members will only be other LinkedListNodes or null.

function LinkedListIterator(){}

LinkedListIterator.prototype = {

_current: null,

Current: function() {

var retval = null;

if (this._current != null)

{

retval = this._current.Data;

}

return retval;

},

Next: function() {

if (this._current != null)

{

this._current = this._current.Next;

}

return this._current != null;

},

Previous: function() {

if (this._current != null)

{

this._current = this._current.Previous;

}

return this._current != null;

},

HasData: function() {

return this._current != null;

}

};

LinkedListIterator allows one to go forward and backward within a LinkedList. The iterator can become invalid when it runs off the front or back of the LinkedList.

function LinkedList(){}

LinkedList.prototype = {

_head: null,

_back: null,

_length: 0,

Add: function(data) {

var newNode = new LinkedListNode();

newNode.Data = data;

if (this._head == null)

{

this._head = newNode;

this._back = newNode;

}

else

{

newNode.Previous = this._back;

this._back.Next = newNode;

this._back = newNode;

}

++this._length;

return newNode;

},

RemoveAt: function(index) {

var currentIndex = 0;

var nextNode = this._head;

while (nextNode != null && currentIndex < index)

{

++currentIndex;

nextNode = nextNode.Next;

}

if (currentIndex == index)

{

nextNode.Previous.Next = nextNode.Next;

if (nextNode.Next != null)

{

nextNode.Next.Previous = nextNode.Previous;

}

}

return nextNode;

},

Length: function(){

return this._length;

},

InsertAt: function(index, data) {

var currentIndex = 0;

var nextNode = this._head;

var newNode = new LinkedListNode();

newNode.Data = data;

 

if (index == 0)

{

// Insert at head

if (this._head == null)

{

this.Add(data);

}

else

{

newNode.Next = this._head;

this._head.Previous = newNode;

this._head = newNode;

++this._length;

}

}

else if (index >= this._length)

{

// Add to the end.

this.Add(data);

}

else

{

// Insert in the middle

while (nextNode != null && currentIndex < index)

{

++currentIndex;

nextNode = nextNode.Next;

}

if (currentIndex == index)

{

nextNode.Previous.Next = newNode;

newNode.Previous = nextNode.Previous;

newNode.Next = nextNode;

nextNode.Previous = newNode;

++this._length;

}

}

return nextNode;