Click here to Skip to main content
Click here to Skip to main content

Doubly-Linked List Implementation

, 3 Sep 2002 BSD
Rate this:
Please Sign up or sign in to vote.
An inspired implementation of a doubly-linked list in C# for the .NET Framework.


I was writing some code in C# the other day and I realized I needed a linked list to make something I was doing easier. I wanted a list that would collapse around a removed object, and that was not be backed by an array. I naturally went to the .NET Framework and the System.Collections namespace to look at the .NET linked list that I just assumed would be there. To my surprise there was not one. I could not believe it. I then searched MSDN looking for one to see if it was placed in another namespace. It was not; it just did not exist in the .NET Framework. Finally, I searched the internet and still could not find one implemented in C#.

That inspired me to write my own linked list. Not just a standard linked list, but a doubly-linked list. A list where each element has a reference to the next element and the previous element. A standard linked list would just have a reference to the next element. With doubly-linked list, the list can easily be traversed forward and backwards and delete an element in constant time.

Break It Down

My doubly-linked list, which we will call just LinkedList from now on, starts by implementing the following interfaces.

  • IList (which is a ICollection and IEnumerable)
  • ICloneable

Then under this public facade we have a lot of very important private members that do the bulk of the work.

  • class Node
  • class LinkedListEnumerator
  • FindNodeAt(int)
  • Remove(Node)
  • Node headerNode
  • int modifications

Some Details

The Node class is a very simple class, yet it is a very key part of the LinkedList. It wraps an object and keeps a reference to the next node and the previous node. The Node class is hidden from the user of the LinkedList, so that it works like any other collection in the .NET Framework.

The headerNode member variable of type Node has an important role as the starting point in the list. This Node contains a null reference and can never be accessed by the user or removed. It is not considered in the count of total objects in the list. This Node is important in a doubly-linked list, as it is technically the beginning and ending of the list.

The FindNodeAt(int index) method contains the search algorithm for accessing the list by index. At the moment it divides the list in half and searches from the beginning or the end depending on which is closest to the requested index. This method is used by all the other methods directly or indirectly that require access to an object by index. This helps to make the searches much faster. There is potential for improvement for large lists by further dividing before searching, however, at a cost for small lists. Right now this seems like the best compromise for most usages. The current algorithm used to find a Node is below.

    Node node = headerNode;

    if (index < (count / 2))
      for (int i = 0; i <= index; i++)
        node = node.NextNode;
      for (int i = count; i > index; i--)
        node = node.PreviousNode;

The Remove(Node value) is important because it adjusts the remaining Nodes by compressing the list. This is done simply by taking the Node that needs to be removed and changing its previous Node's next Node reference to its next Node, and changing its next Node's previous Node reference to its previous Node then leaving itself for the garbage collector. This may be easier to understand by viewing the algorithm used in this method below.

    if (value != headerNode)
      value.PreviousNode.NextNode = value.NextNode;
      value.NextNode.PreviousNode = value.PreviousNode;


The modifications member variable of type int is incremented every time there is a modification to the structure of the list. The variable is then used by the LinkedListEnumerator to guard against concurrent modifications to the list while enumerating.

The LinkedList class is not thread safe by design. If thread safety is required, the class can be extended to provide it.

The LinkedListEnumerator class is fail-fast. This means it uses the modifications variable it is passed when it is created to know if any modifications have been made while enumerating. The check is made in its MoveNext() method before it increments to the next value. If a modification has been detected then it will throw a SystemException that can then be caught and handled accordingly. Below is the source for LinkedListEnumerator class.

private class LinkedListEnumerator : IEnumerator
  private LinkedList  linkedList;
  private int         validModificationCount;
  private Node        currentNode;
  public LinkedListEnumerator(LinkedList linkedList)
    this.linkedList         = linkedList;
    validModificationCount  = linkedList.modifications;
    currentNode             = linkedList.headerNode;
  public object Current
      return currentNode.CurrentNode;
  public void Reset()
    currentNode = linkedList.headerNode;

  public bool MoveNext()
    bool moveSuccessful = false;

    if (validModificationCount != linkedList.modifications)
      throw new SystemException(
          "A concurrent modification occured to the LinkedList " + 
          "while accessing it through it's enumerator.");

    currentNode = currentNode.NextNode;

    if (currentNode != linkedList.headerNode)
      moveSuccessful = true;

    return moveSuccessful;

The LinkedList(ICollection) constructor and the AddAll(ICollection) and InsertAll(int, ICollection) are there for convenience to the user of the list. This constructor calls AddAll(ICollection) which in turn calls InsertAll(int, ICollection). Below is the the code for this method.

public virtual void InsertAll(int index, ICollection collection)
  if (collection != null)
    if (0 < collection.Count)

      Node startingNode = (index == count ? 
                  headerNode : FindNodeAt(index));
      Node previousNode = startingNode.PreviousNode;

      foreach (object obj in collection)
        Node node             = new Node(obj, 
                  startingNode, previousNode);
        previousNode.NextNode = node;
        previousNode          = node;

      startingNode.PreviousNode = previousNode;

      count += collection.Count;            
      throw new ArgumentOutOfRangeException("index", 
                   index, "less than zero");
    throw new ArgumentNullException("collection");

The LinkedList provides two methods for cloning. The first is the ICloneable interface Clone() method. It provides a shallow copy of the LinkedList. The second is Clone(bool attemptDeepCopy). It attempts to make a deep copy of the list if passed true, if false it will make a shallow copy. If an object in the list is not an ICloneable then it will throw a SystemException. The returned attempted deep copied list is not guaranteed to be a true deep copy. It defers the cloning to the objects own Clone() method. Here is the source for these two methods.

public virtual object Clone()
  LinkedList listClone = new LinkedList();

  for (Node node = headerNode.NextNode; node != headerNode; 
          node = node.NextNode)

  return listClone;

public virtual LinkedList Clone(bool attemptDeepCopy)
  LinkedList listClone;

  if (attemptDeepCopy)
    listClone = new LinkedList();

    object currentObject;

    for (Node node = headerNode.NextNode; node != headerNode; 
           node = node.NextNode)
      currentObject = node.CurrentNode;

      if (currentObject == null)
      else if (currentObject is ICloneable)
        throw new SystemException("The object of type [" + 
                     currentObject.GetType() + 
                     "] in the list is not an ICloneable, cannot attempt " + 
                     "a deep copy.");
    listClone = (LinkedList)this.Clone();

  return listClone;


I believe this is a great class to learn how to implement your own custom collection. It is also very useful as it is, and ready to be included in your next project. The rest of the class is fairly straight-forward for a list collection. The class is fairly well commented using XML comment tags. Experienced and intermediate developers should have no trouble following the class.

This LinkedList is part of a set of .NET utilities I am developing, and have released as an open source project under the GNU General Public License (GPL). My complete project can be found at Source Forge.


This article, along with any associated source code and files, is licensed under The BSD License


About the Author

Rodney S. Foley
Software Developer (Senior)
United States United States
No Biography provided

Comments and Discussions

AnswerOptimized doubly linked list PinmemberMember 94077375-Sep-12 4:34 
GeneralRe: Optimized doubly linked list PinmemberRodney S. Foley6-Sep-12 21:30 
GeneralMy vote of 5 PinmemberVistaaR22-Feb-11 1:55 
GeneralMy vote of 1 PinmemberBen_Desjardins22-Jan-09 10:00 
GeneralThere is something in the code that is totally unnecessary. PinmemberECDundy7-Jul-08 23:45 
GeneralThis might help! PinmemberMember 335201122-Feb-08 18:40 
QuestionLinked Controls? PinmemberCoderJ22-Aug-07 13:25 
GeneralNot as fas as I expected Pinmemberphm379-Mar-07 4:41 
GeneralJoint collection article PinmemberJonathan de Halleux30-Mar-04 2:33 
Generalsome optimizations PinmemberTweety21-Feb-04 19:21 
GeneralRe: some optimizations Pinmemberphm379-Mar-07 4:00 
QuestionWhy no linked list in framework? PinmemberMike Junkin29-Oct-03 18:41 
AnswerRe: Why no linked list in framework? PinmemberJeff Varszegi29-Oct-03 19:45 
AnswerNow it does! [.NET 2] Pinmembergiddy_guitarist24-Feb-07 1:45 
QuestionTrees with managed code? Pinmemberwarnov6-Oct-03 17:35 
AnswerRe: Trees with managed code? PinmemberAalst6-Oct-03 19:30 
GeneralRe: Trees with managed code? PinmemberJeff Varszegi29-Oct-03 19:55 
GeneralRe: Trees with managed code? PinmemberAalst30-Oct-03 2:58 
GeneralRe: Trees with managed code? PinmemberJeff Varszegi30-Oct-03 16:02 
AnswerRe: Trees with managed code? PinmemberTweety21-Feb-04 19:23 
AnswerRe: Trees with managed code? PinsussAnonymous3-Jul-05 23:49 
GeneralLinked Lists are nice to have... Pinmemberblueling26-Sep-03 4:22 
Generalusing GetHashCode when searching for a value Pinmembertomer dror27-Mar-03 11:39 
GeneralLatest version of the LinkedList available PinmemberAalst16-Sep-02 12:22 
QuestionWhat's the point? PinsussAngry Coder11-Sep-02 21:04 
AnswerRe: What's the point? PinmemberColin^Davies11-Sep-02 21:57 
GeneralRe: What's the point? PinmemberAalst11-Sep-02 22:45 
GeneralRe: What's the point? Pinmemberzquad4-Jul-07 19:57 
AnswerRe: What's the point? PinmemberAalst11-Sep-02 22:43 
GeneralRe: What's the point? PinmemberMark Conger12-Sep-02 2:05 
I have to agree with Aalst here. It's pretty obvious that most of the primary collection classes in .NET base off one of the classes he mentioned(usually CollectionBase). A quick peek with ildasm will reveal that they use an internalized array to really do the job. Aalast covered the differences admirably.

I think one aspect is being glossed over a bit here. When I learned to write data structures in PASCAL, singlely- and doubly-linked lists were the FIRST thing that was taught to me. They provide a fundamental basis for true datastorage (or did in that day in age). CP caters not only to the advanced programmer but to the folks new to programming who may not have a formal education or are making a drastic career switch from language to another. Glancing over this example I can see many basic techniques that were used here that are great for new programmers to see in a useful, but simple example. Need Examples? Basic data storage techniques, Use of interfaces, and implementation of the IEnumerable iterator just to name a couple. Are they how I would have implemented them? Probably not. Does that make them wrong? Absolutely, positively not.

Let me offer one last observation. A good programmer doesn't criticize another's code because its simple or it re-implements something already there. Why? Because tomorrow that simple code or re-implementation may be the elegant and useful problem that was a painful problem. It's the old throwing stones when you live in the glass house philosophy.


Flames to /dev/null , please Smile | :)

GeneralRe: What's the point? PinmemberAalst12-Sep-02 2:29 
GeneralRe: What's the point? PinmemberMark Conger12-Sep-02 4:17 
GeneralRe: What's the point? PinmemberAalst12-Sep-02 4:32 
GeneralRe: What's the point? PinmemberAalst16-Sep-02 12:25 
GeneralRe: What's the point? PinsussAnonymous11-Nov-02 1:51 
GeneralRe: What's the point? PinmemberJon Rista25-Nov-02 21:19 
GeneralRe: What's the point? PinmemberAalst25-Nov-02 22:12 
GeneralRe: What's the point? PinmemberFrans Bouma2-Jan-03 1:21 
GeneralRe: What's the point? PinmemberScott.S3-Jun-03 12:57 
GeneralRight on, brotha PinmemberJeff Varszegi29-Oct-03 20:05 
GeneralRe: What's the point? Pinmembervukovicg5-Jan-06 19:13 
GeneralRe: What's the point? Pinmemberpeterchen19-Jul-03 14:53 
GeneralRe: What's the point? PinmemberDaniel Barr8-Apr-04 15:13 
GeneralRe: What's the point? PinmemberJames Curran7-Jul-06 10:13 
GeneralRe: What's the point? Pinmemberzaccheus17-Sep-06 1:29 
AnswerRe: What's the point? Pinmemberjill2-Jan-03 9:23 
GeneralGood work PineditorNishant S11-Sep-02 20:11 
GeneralNice Job PinmemberNick Parker4-Sep-02 9:40 
GeneralRe: Nice Job PinmemberAalst4-Sep-02 15:29 
GeneralRe: Nice Job PinmemberNick Parker5-Sep-02 3:51 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150414.1 | Last Updated 4 Sep 2002
Article Copyright 2002 by Rodney S. Foley
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid