Reader Level:
ARTICLE

Using Linked List in C#

Posted by Jay Smith Articles | C# Language June 25, 2003
What we going to make is a linked list. Yeah I know there is a class which does the same as a linked list called ArrayList, but we (as a diehard C# programmer) want absolute control and knowledge of what we use.
  • 1
  • 0
  • 297237
Download Files:
 

What we going to make is a linked list. Yeah I know there is a class which does the same as a linked list called ArrayList, but we (as a diehard C# programmer) want absolute control and knowledge of what we use.

First what is a linked list?

A linked list is a dynamically sized array. An array has a size and you have to deal with it you cant just resize an array. Unlike an array a linked list has no absolute size. It can hold as many variables as you want it to.

When to use?

In circumstances where you dont know how many variables you want to add. For example it could be just 1 or it could be 1000. In such a situation its stupid to make an array of 10000 it would be a waist of memory.

Now a design of our classes LinkedList and Node.

Note: Prefix i is for an integer and a prefix n is for a Node.

In the Node class there is a Previous and a Next Node. Because of that all Nodes are linked to eachother (thats why they called it a linkedlist).

Here is the Node class

public class Node
{
protected Node nPrevious;
protected Node nNext;
protected object Object;
#region Properties
public object Value
{
get
{
return Object;
}
set
{
Object =
value;
}
}
public Node Previous
{
get
{
return nPrevious;
}
set
{
nPrevious =
value;
}
}
public Node Next
{
get
{
return nNext;
}
set
{
nNext =
value;
}
}
#endregion
public Node(Node PrevNode, Node NextNode, object obj)
{
nPrevious = PrevNode;
nNext = NextNode;
Object = obj;
}
}

As you can see there isnt much of a surprise
if you studied the class design.

Next thing the LinkedList class.

public class LinkedList
{
int iCount = 1;
int iCurrent = 0;
Node nCurrent;
#region Properties
/// <summary>
/// Give back how many nodes there are.
/// </summary>
public int Count
{
get
{
return iCount;
}
}
/// <summary>
/// Gives back the current Node
/// </summary>
public Node CurrentNode
{
get
{
return nCurrent;
}
}
/// <summary>
/// Keeps track of the index where you are
/// </summary>
public int CurrentNodeIndex
{
get
{
return iCurrent;
}
}
#endregion
/// <summary>
/// Default and only Constructor
/// SetUp our LinkedList
/// </summary>
/// <param name="obj">Value for the first Node</param>
public LinkedList(object obj)
{
nCurrent =
new Node(null, null, obj);
nCurrent.Next =
null;
nCurrent.Previous =
null;
}
/// <summary>
/// This function will add another Node
/// </summary>
/// <param name="obj">Value for the added Node</param>
public void AddNode(object obj)
{
if(nCurrent.Next == null)
{
nCurrent = nCurrent.Next =
new Node(nCurrent, null, obj);
}
else
{
nCurrent = nCurrent.Next =
new Node(nCurrent, nCurrent.Next,obj);
}
iCount++;
iCurrent++;
}
/// <summary>
/// Goes to the next Node
/// </summary>
public void ToNext()
{
// Checks whether the Next Node is null
// if so it throws an exception.
// You can also do nothing but I choos for this.
if(nCurrent.Next == null)
{
throw new Exception("There is no next node!");
}
else // If everything is OK
{
nCurrent = nCurrent.Next;
iCurrent++;
}
}
/// <summary>
/// Goes to the previous Node
/// </summary>
public void ToPrevious()
{
// Look at ToNext();
if(nCurrent.Previous == null)
{
throw new Exception("There is no previous node!");
}
else
{
nCurrent = nCurrent.Previous;
iCurrent--;
}
}
/// <summary>
/// Goes to the index you fill in
/// </summary>
/// <param name="index">Index Where to go?</param>
public void GoTo(int index)
{
if(iCurrent < index)
{
ToNext();
}
else if(iCurrent > index)
{
ToPrevious();
}
}
}

Conclusion:

It isnt hard to make a linked list and I guess most programmers are already familiar with linked lists. And for the C++ programmers out there you see without pointers :p ( I just hate pointers)

Article Extensions
Contents added by isma perez on Apr 12, 2011
Contents added by Mahesh Chand on Aug 25, 2010
C# 2.0 and later versions provides the LinkedList<T> generic class that represents a doubly linked list.

Here is an example from MSDN on how to use LinkedList generic class.


using System;

using System.Text;

using System.Collections.Generic;

 

public class Example

{

    public static void Main()

    {

        // Create the link list.

        string[] words =

            { "the", "fox", "jumped", "over", "the", "dog" };

        LinkedList<string> sentence = new LinkedList<string>(words);

        Display(sentence, "The linked list values:");

        Console.WriteLine("sentence.Contains(\"jumped\") = {0}",

            sentence.Contains("jumped"));

 

        // Add the word 'today' to the beginning of the linked list.

        sentence.AddFirst("today");

        Display(sentence, "Test 1: Add 'today' to beginning of the list:");

 

        // Move the first node to be the last node.

        LinkedListNode<string> mark1 = sentence.First;

        sentence.RemoveFirst();

        sentence.AddLast(mark1);

        Display(sentence, "Test 2: Move first node to be last node:");

 

        // Change the last node be 'yesterday'.

        sentence.RemoveLast();

        sentence.AddLast("yesterday");

        Display(sentence, "Test 3: Change the last node to 'yesterday':");

 

        // Move the last node to be the first node.

        mark1 = sentence.Last;

        sentence.RemoveLast();

        sentence.AddFirst(mark1);

        Display(sentence, "Test 4: Move last node to be first node:");

 

 

        // Indicate, by using parentheisis, the last occurence of 'the'.

        sentence.RemoveFirst();

        LinkedListNode<string> current = sentence.FindLast("the");

        IndicateNode(current, "Test 5: Indicate last occurence of 'the':");

 

        // Add 'lazy' and 'old' after 'the' (the LinkedListNode named current).

        sentence.AddAfter(current, "old");

        sentence.AddAfter(current, "lazy");

        IndicateNode(current, "Test 6: Add 'lazy' and 'old' after 'the':");

 

        // Indicate 'fox' node.

        current = sentence.Find("fox");

        IndicateNode(current, "Test 7: Indicate the 'fox' node:");

 

        // Add 'quick' and 'brown' before 'fox':

        sentence.AddBefore(current, "quick");

        sentence.AddBefore(current, "brown");

        IndicateNode(current, "Test 8: Add 'quick' and 'brown' before 'fox':");

 

        // Keep a reference to the current node, 'fox',

        // and to the previous node in the list. Indicate the 'dog' node.

        mark1 = current;

        LinkedListNode<string> mark2 = current.Previous;

        current = sentence.Find("dog");

        IndicateNode(current, "Test 9: Indicate the 'dog' node:");

 

        // The AddBefore method throws an InvalidOperationException

        // if you try to add a node that already belongs to a list.

        Console.WriteLine("Test 10: Throw exception by adding node (fox) already in the list:");

        try

        {

            sentence.AddBefore(current, mark1);

        }

        catch (InvalidOperationException ex)

        {

            Console.WriteLine("Exception message: {0}", ex.Message);

        }

        Console.WriteLine();

 

        // Remove the node referred to by mark1, and then add it

        // before the node referred to by current.

        // Indicate the node referred to by current.

        sentence.Remove(mark1);

        sentence.AddBefore(current, mark1);

        IndicateNode(current, "Test 11: Move a referenced node (fox) before the current node (dog):");

 

        // Remove the node referred to by current.

        sentence.Remove(current);

        IndicateNode(current, "Test 12: Remove current node (dog) and attempt to indicate it:");

 

        // Add the node after the node referred to by mark2.

        sentence.AddAfter(mark2, current);

        IndicateNode(current, "Test 13: Add node removed in test 11 after a referenced node (brown):");

 

        // The Remove method finds and removes the

        // first node that that has the specified value.

        sentence.Remove("old");

        Display(sentence, "Test 14: Remove node that has the value 'old':");

 

        // When the linked list is cast to ICollection(Of String),

        // the Add method adds a node to the end of the list.

        sentence.RemoveLast();

        ICollection<string> icoll = sentence;

        icoll.Add("rhinoceros");

        Display(sentence, "Test 15: Remove last node, cast to ICollection, and add 'rhinoceros':");

 

        Console.WriteLine("Test 16: Copy the list to an array:");

        // Create an array with the same number of

        // elements as the inked list.

        string[] sArray = new string[sentence.Count];

        sentence.CopyTo(sArray, 0);

 

        foreach (string s in sArray)

        {

            Console.WriteLine(s);

        }

 

        // Release all the nodes.

        sentence.Clear();

 

        Console.WriteLine();

        Console.WriteLine("Test 17: Clear linked list. Contains 'jumped' = {0}",

            sentence.Contains("jumped"));

 

        Console.ReadLine();

    }

 

    private static void Display(LinkedList<string> words, string test)

    {

        Console.WriteLine(test);

        foreach (string word in words)

        {

            Console.Write(word + " ");

        }

        Console.WriteLine();

        Console.WriteLine();

    }

 

    private static void IndicateNode(LinkedListNode<string> node, string test)

    {

        Console.WriteLine(test);

        if (node.List == null)

        {

            Console.WriteLine("Node '{0}' is not in the list.\n",

                node.Value);

            return;

        }

 

        StringBuilder result = new StringBuilder("(" + node.Value + ")");

        LinkedListNode<string> nodeP = node.Previous;

 

        while (nodeP != null)

        {

            result.Insert(0, nodeP.Value + " ");

            nodeP = nodeP.Previous;

        }

 

        node = node.Next;

        while (node != null)

        {

            result.Append(" " + node.Value);

            node = node.Next;

        }

 

        Console.WriteLine(result);

        Console.WriteLine();

    }

}

 

COMMENT USING

Trending up