Click here to Skip to main content
15,358,946 members
Articles / Programming Languages / C#
Posted 2 Sep 2002


73 bookmarked

Doubly-Linked List Implementation

Rate me:
Please Sign up or sign in to vote.
4.66/5 (31 votes)
3 Sep 2002BSD5 min read
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 Pin
Member 94077375-Sep-12 3:34
MemberMember 94077375-Sep-12 3:34 
GeneralRe: Optimized doubly linked list Pin
Rodney S. Foley6-Sep-12 20:30
MemberRodney S. Foley6-Sep-12 20:30 
GeneralMy vote of 5 Pin
VistaaR22-Feb-11 0:55
MemberVistaaR22-Feb-11 0:55 
GeneralMy vote of 1 Pin
_darksake_22-Jan-09 9:00
Member_darksake_22-Jan-09 9:00 
GeneralThere is something in the code that is totally unnecessary. Pin
ECDundy7-Jul-08 22:45
MemberECDundy7-Jul-08 22:45 
GeneralThis might help! Pin
Member 335201122-Feb-08 17:40
MemberMember 335201122-Feb-08 17:40 
QuestionLinked Controls? Pin
CoderJ22-Aug-07 12:25
MemberCoderJ22-Aug-07 12:25 
GeneralNot as fas as I expected Pin
Jaguas9-Mar-07 3:41
MemberJaguas9-Mar-07 3:41 
GeneralJoint collection article Pin
Jonathan de Halleux30-Mar-04 1:33
MemberJonathan de Halleux30-Mar-04 1:33 
Generalsome optimizations Pin
MyBlindy21-Feb-04 18:21
MemberMyBlindy21-Feb-04 18:21 
GeneralRe: some optimizations Pin
Jaguas9-Mar-07 3:00
MemberJaguas9-Mar-07 3:00 
QuestionWhy no linked list in framework? Pin
Mike Junkin29-Oct-03 17:41
MemberMike Junkin29-Oct-03 17:41 
AnswerRe: Why no linked list in framework? Pin
Jeff Varszegi29-Oct-03 18:45
professionalJeff Varszegi29-Oct-03 18:45 
AnswerNow it does! [.NET 2] Pin
giddy_guitarist24-Feb-07 0:45
Membergiddy_guitarist24-Feb-07 0:45 
QuestionTrees with managed code? Pin
warnov6-Oct-03 16:35
Memberwarnov6-Oct-03 16:35 
AnswerRe: Trees with managed code? Pin
Rodney S. Foley6-Oct-03 18:30
MemberRodney S. Foley6-Oct-03 18:30 
GeneralRe: Trees with managed code? Pin
Jeff Varszegi29-Oct-03 18:55
professionalJeff Varszegi29-Oct-03 18:55 
GeneralRe: Trees with managed code? Pin
Rodney S. Foley30-Oct-03 1:58
MemberRodney S. Foley30-Oct-03 1:58 
GeneralRe: Trees with managed code? Pin
Jeff Varszegi30-Oct-03 15:02
professionalJeff Varszegi30-Oct-03 15:02 
AnswerRe: Trees with managed code? Pin
MyBlindy21-Feb-04 18:23
MemberMyBlindy21-Feb-04 18:23 
AnswerRe: Trees with managed code? Pin
Anonymous3-Jul-05 22:49
MemberAnonymous3-Jul-05 22:49 
GeneralLinked Lists are nice to have... Pin
blueling26-Sep-03 3:22
Memberblueling26-Sep-03 3:22 
Generalusing GetHashCode when searching for a value Pin
tomer dror27-Mar-03 10:39
Membertomer dror27-Mar-03 10:39 
GeneralLatest version of the LinkedList available Pin
Rodney S. Foley16-Sep-02 11:22
MemberRodney S. Foley16-Sep-02 11:22 
QuestionWhat's the point? Pin
Angry Coder11-Sep-02 20:04
sussAngry Coder11-Sep-02 20:04 

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

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