Creating a very simple linked list

Question

I am trying to create a linked list just to see if I can, and I am having trouble getting my head around it. Does anyone have an example of a very simple implementation of Linked list using C#? All the examples I have found so far are quite overdone.

Answer 1

This one is nice:

  namespace ConsoleApplication1
    {

    // T is the type of data stored in a particular instance of GenericList.
    public class GenericList<T>
    {
        private class Node
        {
            // Each node has a reference to the next node in the list.
            public Node Next;
            // Each node holds a value of type T.
            public T Data;
        }

        // The list is initially empty.
        private Node head = null;

        // Add a node at the beginning of the list with t as its data value.
        public void AddNode(T t)
        {
            Node newNode = new Node();
            newNode.Next = head;
            newNode.Data = t;
            head = newNode;
        }

        // The following method returns the data value stored in the last node in
        // the list. If the list is empty, the default value for type T is
        // returned.
        public T GetFirstAdded()
        {
            // The value of temp is returned as the value of the method. 
            // The following declaration initializes temp to the appropriate 
            // default value for type T. The default value is returned if the 
            // list is empty.
            T temp = default(T);

            Node current = head;
            while (current != null)
            {
                temp = current.Data;
                current = current.Next;
            }
            return temp;
        }
    }
}

Test code:

static void Main(string[] args)
{
    // Test with a non-empty list of integers.
    GenericList<int> gll = new GenericList<int>();
    gll.AddNode(5);
    gll.AddNode(4);
    gll.AddNode(3);
    int intVal = gll.GetFirstAdded();
    // The following line displays 5.
    System.Console.WriteLine(intVal);
}

I encountered it on msdn here

Answer 2

A simple Google search yielded this article:

http://www.functionx.com/csharp1/examples/linkedlist.htm

looks pretty simple on first glance...

Also, when you're ready for the next level, use reflector to examine Microsoft's own LinkedList

Answer 3

A Linked List, at its core is a bunch of Nodes linked together.

So, you need to start with a simple Node class:

public class Node {
    public Node next;
    public Object data;
}

Then your linked list will have as a member one node representing the head (start) of the list:

public class LinkedList {
    private Node head;
}

Then you need to add functionality to the list by adding methods. They usually involve some sort of traversal along all of the nodes.

public void printAllNodes() {
    Node cur = head;
    while (cur.next != null) 
    {
        Console.WriteLine(cur.data);
        cur = cur.next;
    }
}

Also, inserting new data is another common operation:

public void Add(Object data) {
    Node toAdd = new Node();
    toAdd.data = data;
    Node current = head;
    // traverse all nodes (see the print all nodes method for an example)
    current.Next = toAdd;
}

This should provide a good starting point.