Home

Linked Lists

     

Introduction

A linked list is a technique of creating a collection of items where an item can be located based on another existing item, unless the list contains only one item, in which case the item would be located from the beginning (called the head).

Here is another example of a linked list. This time, the list allows you to add an item to the beginning or the end of the list:

   
using System;

public class Node<T>
{
    public T Value { get; set; }
    public Node<T> Next { get; set; }
}

public class LinkedList<T>
{
    private  Node<T> begin;
    private  Node<T> end;
    private int size;

    public LinkedList()
    {
        begin = null;
        end = null;
        size = 0;
    }

    public int Count
    {
        get { return size; }
    }

    public void AddFirst(Node<T> item)
    {
        // Get a reference to the node we want to add
        Node<T> current = item;

        // If the list is currently empty, specify that the first
        // and the last are the same and they will receive the argument
        if (begin == null)
            begin = end = current;
        else // If there is already at least one item in the collection
        {
            // Get a reference to the current first item
            Node<T> first = this[0];
            // Get the next item to the first and assign it
            // to the next item of the argument
            current.Next = first.Next;
            // Replace the next item of the first with the argument
            first.Next = current;
        }

        // Increase the count of items
        size++;
    }

    public void AddLast(Node<T> item)
    {
        // Get a reference to the new item that will be added
        // and assign the argument to that reference
        Node<T> current = item;

        // Indicate that the first node will become next to the new item
        current.Next = begin;
        // Indicate that the new item becomes the first of the collection
        begin = current;

        // Increase the count of items
        size++;
    }

    public void Delete()
    {
        if (begin == null)
            return; // throw new NullReferenceException("The list is currently empty");

        Node<T> current;

        current = begin.Next;
        begin.Next = current.Next;
        size--;
    }

    public void Clear()
    {
        size = 0;
    }

    public void Show()
    {
        Console.Write("Current List: ");
        for (Node<T> current = begin; current != null; current = current.Next)
            Console.Write(current.Value + " - ");
        Console.WriteLine();
    }

    public Node<T> Get(int index)
    {
        Node<T> current = begin;

        for (int i = size - 1; (i > index) && (current != null); i--)
            current = current.Next;
        return current;
    }

    public Node<T> this[int index]
    {
        get
        {
            Node<T> current = begin;

            for (int i = size - 1; (i > index) && (current != null); i--)
                current = current.Next;
            return current;
        }
    }

    public override string ToString()
    {
        string result = "- ";
        Node<T> current = begin;

        if (begin == null) // throw new NullReferenceException("The list is currently empty");
            return "The list is currently empty";
        else
        {
            for (int i = 0; i < size; i++)
            {
                result = result + current.Value + " - ";
                current = current.Next;
            }
        }

        return result;
    }
}

public class Exercise
{
    static int Main(string[] args)
    {
        Node<string> name = null;
        LinkedList<string> employees = new LinkedList<string>();

        name = new Node<string>();
        name.Value = "Alan Baxter";
        employees.AddFirst(name);

        name = new Node<string>();
        name.Value = "Joan Bramble";
        employees.AddLast(name);

        name = new Node<string>();
        name.Value = "Lionel Berg";
        employees.AddLast(name);

        name = new Node<string>();
        name.Value = "Paul Bertrand Yamaguchi";
        employees.AddFirst(name);

        name = new Node<string>();
        name.Value = "Flora Bruze";
        employees.AddLast(name);

        name = new Node<string>();
        name.Value = "Christopher Fox";
        employees.AddLast(name);

        name = new Node<string>();
        name.Value = "Holly Madsen";
        employees.AddFirst(name);

        for(int i = 0; i < employees.Count; i++)
            Console.WriteLine("Name {0}: {1}", i + 1, employees[i].Value);

        Console.WriteLine("----------------------------------");

        employees.Delete();

        for (int i = 0; i < employees.Count; i++)
            Console.WriteLine("Name {0}: {1}", i + 1, employees[i].Value);

        return 0;
    }
}

This would produce:

Name 1: Holly Madsen
Name 2: Paul Bertrand Yamaguchi
Name 3: Alan Baxter
Name 4: Joan Bramble
Name 5: Lionel Berg
Name 6: Flora Bruze
Name 7: Christopher Fox
----------------------------------
Name 1: Holly Madsen
Name 2: Paul Bertrand Yamaguchi
Name 3: Alan Baxter
Name 4: Joan Bramble
Name 5: Lionel Berg
Name 6: Christopher Fox
Press any key to continue . . .
 
 

Home Copyright © 2010-2011 FunctionX