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 one more example of a linked list. This time also, 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;
    public Node<T> end;
    private int size;

    public LinkedList()
    {
        begin = default(Node<T>); // null;
        end = default(Node<T>); // null;
        size = 0;
    }

    public int Count
    {
        get { return size; }
    }

    public bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            return false;
        }
    }

    public Node<T> First
    {
        get
        {
            if (begin == null ) // return null;
                throw new NullReferenceException("There is no item in the collection");
            else
            {
                Node<T> temp = null; // default(T);

                Node<T> current = begin;
                while (current != null)
                {
                    temp = current;
                    current = current.Next;
                }
                return temp;
            }
        }
        set
        {
            begin = value;
        }
    }

    public Node<T> Last
    {
        get
        {
            return begin;
        }
        set
        {
            end = value;
        }
    }

    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 DeleteFirst()
    {
        if (begin == null)
            return; // throw new NullReferenceException("The list is currently empty");

        Node<T> current = begin.Next;

        begin.Next = current;
        size--;
    }

    public void DeleteLast()
    {
        if (begin == null)
            return; // throw new NullReferenceException("The list is currently empty");
        else
        {
            Node<T> current = new Node<T>();
            Node<T> lastItem = this[size];

            current   = lastItem.Next;
            lastItem.Next = current.Next;

            size--;
        }
    }

    public void Insert(Node<T> item, int index)
    {
        if (index == 0)
            AddFirst(item);
        else if (index >= size)
        {
            // Is the user passes an index higher than the total number of items,
            // instead of throwing an exception,
            // we will add the item to the end of the list
            AddLast(item);
        }
        else
        {
            Node<T> current = item;

            Node<T> itemAtIndex = this[index];
            current.Next = itemAtIndex.Next;
            itemAtIndex.Next = current;
            size++;
        }
    }

    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 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.AddFirst(name);

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

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

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

        //name = new Node<string>();
        //name.Value = "Mathew Jeremy Williams";
        //employees.Insert(name, 3);

        name = new Node<string>();
        name.Value = "Christopher Fox";
        employees.AddFirst(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.DeleteFirst();

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

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

        //employees.DeleteLast();

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

        Console.WriteLine("----------------------------------");
        Console.WriteLine("First Item: {0}", employees.First.Value);
        Console.WriteLine("Last Item:  {0}", employees.Last.Value);
        Console.WriteLine("----------------------------------");

        return 0;
    }
}

This would produce:

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

Home Copyright © 2010-2011 FunctionX