First post: Implementing a Double Linked List in C# - part I

Hello World!

The first blog post is dedicated to a basic, but important data structure: the double linked list. It is intended to be an academic exercise, rather than a practical one.

Acknowledgement: I'm not a native English speaker, and despite Word's spell & grammar checker, please indulge my language faults. Still, constructive criticism is appreciated!

I've separated the plan of this project into 3 parts: the description of the domain of the problem at hand, definition of the requirements and, finally, the design. The article will be separated into two parts, leaving the design into the second part. A third, bonus, part might be included into the series.

First let's describe the DOMAIN of the problem

Wikipedia comes to our help with a definition of a double linked list (approx.): the (double) linked list is a data structure. It consists of a sequence of nodes, each containing arbitrary data fields and two references, to the next and previous nodes.

Some implementations provide two special nodes, called sentinels. These nodes are placed at the beginning and end of the list, and do not contain any data. Their purpose is to provide a uniform way of treating the insertion and removal of standard nodes.

The main purpose of the linked lists is to be a base for other data structures, like stacks and queues. The main benefit over conventional arrays is that they support the insertion and removal of elements, without creating a new instance of the structure. The advantage of the double linked list over other linked lists is that they can be traversed backwards as well as forwards.

In the .Net world, support for sequential data structures, besides arrays, is provided through collections. Collections are defined by a set of interfaces, which provide a uniform set of patterns for manipulating collections, and the concrete implementations of several types of collections: lists, dictionaries, hash tables and so on.

Another feature of the .Net framework, available from the v2.0 version, is generics. They enable the user to generalize the definition of types, by leaving a part of the implementation of the type to be provided when the type will be consumed. This will enable the list to contain any type of data, as long as it is of the same type (of course, a collection of object objects will hold any data, but that's not the point).

REQUIREMENTS prescription

The requirements for our double linked list represent what is expected from it. They fall into two categories, what is expected from a double linked list, and what is expected from a collection. The two categories are overlapping. The list of requirements is by no means exhaustive, and might be improved in the course of the implementation.

A double linked list should:

• Provide storage for data into nodes.
• Permit the insertion of new node(s) when the list is empty as well as when the list has existing items.
• Permit the removal of a specified item.
• Return the number of existing nodes.
• Return a specific node.
• Provide a consistent mechanism for dealing with errors.
• Provide the next and previous nodes for a given node.

A collection should:

• Provide for data into items.
• Permit the addition of new item(s).
• Permit the removal of item(s).
• Iterate over its values.
• Permit the retrieval of a specified item.
• Permit the alteration of the order of its item (ex. Sorting).

This ends the first two parts of our plan. Next time we will see how we can get from a list o requirements to an usable artifact.