Showing posts with label Introduction to C# collection Linked Lists. Show all posts
Showing posts with label Introduction to C# collection Linked Lists. Show all posts

Thursday, 16 February 2012

Operations on c # Linked Lists

Common Routines of a Linked List

 
Introduction


To enhance the functionality of a linked list, you will need to keep track of what item is the first and which one is the last. This is because some operations must be performed in the starting point of a collection and some others will need to reference the last item. To keep track of these two special nodes, you should (must) create a variable for each:
Linked List
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;
}
Of course, when the collection starts, the first and the last items have no value. Therefore, you should initialize them to null or their default value if you are using a primitive type. Here is an example:
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;

    public LinkedList()
    {
        begin = null;
        end = null;
    }
}
Other than that, in previous lessons, we saw that you should usually (if not always) provide a way to get the current number of items in a collection. We also saw that you provide a mechanism to get to an item inside the collection. You can use a method or a read-only indexed property for the same purpose. You should also provide a Boolean read-only property that checks whether the list is currently empty or not. Here is an example:
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 bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            return false;
        }
    }

    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 = end;

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

        return result;
    }
}
Adding a First Item

The first item of a collection is the last item that was added to the list:
First Item
Still, if you want, you can create a new item and add it as the first in the collection. To do this, create a method that receives the intended item as argument:
  • If the list is currently empty, assign the argument to both the first and the last item
  • If the list already contains at least one item:
    1. Get a reference to the first item
    2. Get the next item to the first and assign it to the next item of the argument
    3. Replace the next item of the first with the argument
  • Increase the number of items in the collection
Here is an example:
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 bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            return false;
        }
    }

    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 Node<T> this[int index]
    {
        get
        {
            Node<T> current = end;

            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 = "Lionel Berg";
        employees.AddFirst(name);

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

        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);

        return 0;
    }
}
This would produce:
Name 1: Holly Madsen
Name 2: Christopher Fox
Name 3: Flora Bruze
Name 4: Lionel Berg
Name 5: Joan Bramble
Name 6: Alan Baxter
Press any key to continue . . .
Using the First Item

If you use an indexed list to identify the members of a collection, the first item of the list is the one with the index of 0. You can use that feature to get the first member. Here is an example:
public class Exercise
{
    static int Main(string[] args)
    {
        Node<string> name = null;
        LinkedList<string> employees = new LinkedList<string>();

        . . .

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

        return 0;
    }
}
This would produce:
Name 1: Holly Madsen
Name 2: Christopher Fox
Name 3: Flora Bruze
Name 4: Paul Bertrand Yamaguchi
Name 5: Lionel Berg
Name 6: Joan Bramble
Name 7: Alan Baxter
---------------------------------
First Item: Holly Madsen
Press any key to continue . . .
Remember that our collection class has a field that represents the first item of the list. You can create a method or a read-only property that simply returns that field. Here is an example:
using System;

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

    public Node<T> Nullify()
    {
        return default(Node<T>);
    }
}

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

    . . . No Change
    
    public Node First
    {
        get
        {
            // If the list has no item, throw an exception
            if( begin == null ) 
                throw new NullReferenceException(
                 "There is no item in the collection");
            else
            {
                // This variable will be used for looping
                Node temp = null;
                // Get a reference to the first item of the collection
                Node current = begin;

                // Loop through the collection, from one item to the next.
                // This allows you to get to the first item
                while (current != null)
                {
                    temp = current;
                    current = current.Next;
                }

                // Return that first item
                return temp;
            }
        }
    }

}

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 = "Lionel Berg";
        employees.AddFirst(name);

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

        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("----------------------------------");
        Console.WriteLine("First Item: {0}", employees.First.Value); // employees[0].Value);

        return 0;
    }
}
This would produce:
Name 1: Holly Madsen
Name 2: Christopher Fox
Name 3: Flora Bruze
Name 4: Lionel Berg
Name 5: Joan Bramble
Name 6: Alan Baxter
----------------------------------
First Item: Holly Madsen
Press any key to continue . . .
Another way you can use the first position is to replace the item in that position with another item.
Adding the Last Item

The technique we saw in the previous lesson about adding a new item to a linked list actually adds the item to the end of the list. This means that we can just name that method AddLast and the result would be the same. Here is an example:
using System;

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

public class LinkedList<T>
{
    . . . No Change

    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++;
    }
}
Using the Last Item

In some cases, you may want to get the last item of a collection. Here is an example of how to access it:
using System;

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

    public Node<T> Nullify()
    {
        return default(Node<T>);
    }
}

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 Node<T> First
    {
        get
        {
            // If the list has no item, throw an exception
            if( begin == null ) 
                throw new NullReferenceException(
                 "There is no item in the collection");
            else
            {
                // This variable will be used for looping
                Node<T> temp = null;
                // Get a reference to the first item of the collection
                Node<T> current = begin;

                // Loop through the collection, from one item to the next.
                // This allows you to get to the first item
                while (current != null)
                {
                    temp = current;
                    current = current.Next;
                }

                // Return that first item
                return temp;
            }
        }
    }

    public Node<T> Last
    {
        get
        {
            return begin;
        }
    }

    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 Node<T> this[int index]
    {
        get
        {
            if( (index == 0) && (begin == null) )
                throw new NullReferenceException(
                 "There is no item in the collection");
            else
            {
                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.AddLast(name);

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

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

        name = new Node<string>();
        name.Value = "Lionel Berg";
        employees.AddLast(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.AddLast(name);

        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: Alan Baxter
Name 2: Joan Bramble
Name 3: Paul Bertrand Yamaguchi
Name 4: Lionel Berg
Name 5: Flora Bruze
Name 6: Christopher Fox
Name 7: Holly Madsen
----------------------------------
First Item: Alan Baxter
Last Item:  Holly Madsen
----------------------------------
Press any key to continue . . .
. Here is an example:
public
Inserting an Item Using an Index

As you should know already, inserting an item consists of putting one between two existing items. One way you can do this consists of passing the new item and an index. When implementing the method, first identify the index. If the user passes an index of 0, this is equivalent to adding the first item. If the user passes an index that is equal to the size of the list, add the item as the last. If the user passes an index that is larger than the size of the list, you can either throw an exception or add the item as the last. If the user passes an index that is positive but less than the total size of the list:
  1. Get a reference to the item passed as argument
  2. Get the item located at the specified index
  3. Get the item next to the one at the index and assign it to the item next to the argument
  4. Assign the argument to the item next to the one at the index
  5. Increase the number of items
Here is an example:
public class Node<T>
{
    public T Value { get; set; }
    public Node<T> Next { get; set; }
}

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

    . . . No Change

    public void Insert(Node<T> item, int index)
    {
        if (index == 0)
            AddFirst(item);
        else if (index >= size)
            AddLast(item);
        else
        {
            Node<T> current = item;

            Node<T> itemAtIndex = this[index];
            current.Next = itemAtIndex.Next;
            itemAtIndex.Next = current;
            
            size++;
        }
    }
}
Here is an example of testing the method:
public class Exercise
{
    static int Main(string[] args)
    {
        Node<string> name = null;
        LinkedList<string> employees = new LinkedList<string>();

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

        name = new Node<string>();
        name.Value = "Alan Baxter";
        employees.AddLast(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.AddLast(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.AddLast(name);

        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: Mathew Jeremy Williams
Name 2: Alan Baxter
Name 3: Joan Bramble
Name 4: Lionel Berg
Name 5: Paul Bertrand Yamaguchi
Name 6: Flora Bruze
Name 7: Christopher Fox
Name 8: Holly Madsen
Press any key to continue . . .
Here is another test:
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.AddLast(name);

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

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

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

        name = new Node<string>();
        name.Value = "Paul Bertrand Yamaguchi";
        employees.AddLast(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.AddLast(name);

        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: Alan Baxter
Name 2: Joan Bramble
Name 3: Mathew Jeremy Williams
Name 4: Lionel Berg
Name 5: Paul Bertrand Yamaguchi
Name 6: Flora Bruze
Name 7: Christopher Fox
Name 8: Holly Madsen
Press any key to continue . . .
Here is one more test:
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.AddLast(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.AddLast(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 = "Mathew Jeremy Williams";
        employees.Insert(name, 3);

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

        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: Alan Baxter
Name 2: Joan Bramble
Name 3: Lionel Berg
Name 4: Mathew Jeremy Williams
Name 5: Paul Bertrand Yamaguchi
Name 6: Flora Bruze
Name 7: Christopher Fox
Name 8: Holly Madsen
Press any key to continue . . .
Deleting an Item

 
Deleting the First Item

To delete the first item of a linked list, get a reference to the next item of the starting positio, assign that reference to the next item to the first. Here is an example:
public void DeleteFirst()
{
        if (begin == null)
            return;

        Node<T> current = begin.Next;

        begin.Next = current;
        size--;
}
Deleting the Last Item

This would produce: 
Number of Items: 0
Press any key to continue . . .
Posted by at No comments :
Labels: , ,

Introduction to C# collection Linked Lists

Introduction


Like an array, a collection is a series of items of the same type. The particularity with creating an array is that you must know in advance the number of items that will make up the list. There are times when you don't know, you can't know, or you can't predict the number of items of the list. For this reason, you may want to create the list for which you don't specify the maximum number of items but you allow the user of the list to add, locate, or remove items at will. Such a list is referred to as a linked list.
Before creating a list, most of the time you would first decide or define what the list would be made of. As different as collections are, one list can be made of numeric values, such as a list that will be made of numbers. You may want a list that is made of names. Such a list can be created from a class that includes a string member variable. Another type of list can contain complex objects. In some other cases, at the time you are creating the collection class, you may not want to specify its type of items. In this case, you can create the class as generic.
Implementing a Collection

After deciding what each item of the list would be made of, you can create a class that would manage the list. This class would be responsible for all operations that can be performed on the list. If the list will be made of primitive values, you can directly create a field of the desired type. Here is an example: 
using System;

public class Numbers
{
    public double Number;
}

public class Exercise
{
    static int Main(string[] args)
    {
        Numbers nbrs = new Numbers();

        return 0;
    }
}
If the list will be made of objects, you can first create a class that specifies those types of items and then declare its variable in the list class. Here is an example of a simple class that holds a double-precision value: 
using System;

public class Number
{
    public double Item;
}

public class Numbers
{
    Number Sample;
}

public class Exercise
{
    static int Main(string[] args)
    {
        Numbers nbrs = new Numbers();

        return 0;
    }
}
When creating a list, one of the aspects you should pay attention to is to keep track of the number of items in the list. To do this, you can create a property that holds the number. The value of this property would increase as the items are added to the list and the value would decrease as the items are removed from the list. Here is how this can be done: 
using System;

public class Number
{
    public double Item;
}

public class Numbers
{
    int size;
    Number Sample;

    public Numbers()
    {
        size = 0;
    }

    public int Count
    {
        get { return size; }
    }
}

public class Exercise
{
    static int Main(string[] args)
    {
        var nbrs = new Numbers();

        Console.WriteLine("Number of Items: {0}", nbrs.Count);

        return 0;
    }
}
This would produce: 
Number of Items: 0
Press any key to continue . . .
You can also create a Boolean read-only property that allows you to check whether the list is currently empty or not. When implementing the get accessor of this property, if the size of the list is 0, return true; otherwise, return false. This would be done as follows:
using System;

public class Number
{
    public double Item;
}

public class Numbers
{
    int size;
    Number Sample;

    public Numbers()
    {
        size = 0;
    }

    public int Count
    {
        get { return size; }
    }
    
    public bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            return false;
        }
    }
}
 
The Beginning of a Collection

A good collection is a list that can grow or shrink as the user wishes. When creating the list, you don't need to predict the maximum number of items that will be added to the list. When a list starts, it is empty or at least it must be considered like that, before any item is added to it. To specify this, you should declare a primary member variable. Although you can call it anything, it is usually called Head:
Collection
The head member can be made private if you don't intend to access it outside of the class. If you want clients of the class to access it, you can make it public. Here is an example:
public class Numbers
{
    int listSize;
    Number Sample;

    public Numbers()
    {
        size = 0;
        Head = null;
    }

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

    public Number Head;
}
Linking the Items of a Collection

We saw that when using an array, each member could be accessed using its index. If the items of a collection are not indexed, you must provide a mechanism to locate an item. To do this, you can use a starting point that determines the beginning of the list. Then, to locate an item, you can check whether another item follows that starting point:
Collection
If no item follows an item, either you are at the end of the list or the list is empty.
To be able to scan a list from one item to another, you can declare a field. Although this member variable can be called anything, for the sake of clarify, you should call it Next. The field is the same type as its class. Here is an example:
public class Number
{
    public double Item;
    public Number Next;
}
Operations on a Collection

 
Adding an Item

Since a list is fundamentally empty when it starts, the primary operation you can perform on a list is to add a new item to it. In order to indicate that you want to add an item to the list, you can create a method that receives an item as argument. For the return type, you have two main options. Because the main job of this method is to add a new item, which it hardly fails to do if you implement it right, it can be defined as void. Alternatively, you can make it return the position of the new item in the list. Here is an example:
 
public class Numbers
{
    int size;
    Number Sample;
    public Number Head;

    public Numbers()
    {
        size = 0;
        Head = null;
    }

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

    public int Add(Number NewItem)
    {
        Number Sample = new Number();

        Sample = NewItem;
        Sample.Next = Head;
        Head = Sample;
        return size++;
    }
}
Getting an Item

Once a list exists, the user can explore it. One of the operations performed on a collection is to locate and retrieve an item. To do this, you can create a method that takes as argument an index. The method would examine the argument with regards to the number of items in the list to make sure the argument's value is in the range of the current items of the list. If the number is too low or too high, the method can return null or 0. If the number is in the range, the method can return the item at that position. Here is an example:
using System;

public class Number
{
    public double Item;
    public Number Next;
}

public class Numbers
{
    int size;
    public Number Head;

    public Numbers()
    {
        size = 0;
        Head = null;
    }

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

    public int Add(Number NewItem)
    {
        Number Sample = new Number();

        Sample = NewItem;
        Sample.Next = Head;
        Head = Sample;
        return size++;
    }

    public Number Get(int Position)
    {
        Number Current = Head;

        for (int i = Count - 1; i > Position && Current != null; i--)
            Current = Current.Next;
        return Current;
    }
}

public class Exercise
{
    static int Main(string[] args)
    {
        Number nbr = null;
        var lstNumbers = new Numbers();

        Console.WriteLine("Number of Items: {0}", lstNumbers.Count);
        Console.WriteLine("-------------------------------------");

        nbr = new Number();
        nbr.Item = 424.06;
        lstNumbers.Add(nbr);

        nbr = new Number();
        nbr.Item = 12500.58;
        lstNumbers.Add(nbr);

        nbr = new Number();
        nbr.Item = 28.0746;
        lstNumbers.Add(nbr);

        nbr = new Number();
        nbr.Item = 1046.88;
        lstNumbers.Add(nbr);
        
        nbr = new Number();
        nbr.Item = 52407.920;
        lstNumbers.Add(nbr);

        for (int i = 0; i < lstNumbers.Count; i++)
            Console.WriteLine("Number {0}: {1}", i + 1, lstNumbers.Get(i).Item);

        Console.WriteLine("-------------------------------------");
        Console.WriteLine("Number of Items: {0}\n", lstNumbers.Count);

        return 0;
    }
}
This would produce:
Number of Items: 0
-------------------------------------
Number 1: 424.06
Number 2: 12500.58
Number 3: 28.0746
Number 4: 1046.88
Number 5: 52407.92
-------------------------------------
Number of Items: 5

Press any key to continue . . .
An alternative is to create a mechanism that would use foreach.
Removing an Item

Deleting an item consists of removing it from the list. There are two main approaches you can use. You can simply ask the class to delete an item. In this case, it is usually the item at the end that gets deleted. If you do this, make sure you perform other routine operations such as decrementing the count of items in the list. Here is an example: 
public class Numbers
{
    . . . No Change

    public bool Delete()
    {
        if (Head == null)
        {
            Console.WriteLine("The list is empty");
            return false;
        }

        Number Current;

        Current = Head.Next;
        Head.Next = Current;
        size--;
        return true;
    }
}
Another technique used to delete an item consists of specifying the position of the item to be deleted. To do this, you can pass an argument as the desired position. The method would check the range of values of the current list. If the specified position is beyond the appropriate range, the method can return false, 0, null, or throw an exception, depending on how you create it.
In the same way, you can create a method that would delete all items from a collection.
Finding an Item

One of the operations hardly performed on a list is to find an item. This is because if you ask a list to locate a particular item, you must provide as much information as possible. Probably the most expedient way you can do this is to completely define an item and pass it to the list. Only if the (exact) item is found in the list would it be recognized.
Here is an example: 
using System;

public class Number
{
    public double Item;
    public Number Next;
}

public class Numbers
{
    int size;
    Number Sample;
    public Number Head;

    public Numbers()
    {
        size = 0;
        Head = null;
    }

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

    public int Add(Number NewItem)
    {
        Number Sample = new Number();

        Sample = NewItem;
        Sample.Next = Head;
        Head = Sample;
        return size++;
    }

    public Number Retrieve(int Position)
    {
        Number Current = Head;

        for (int i = Count - 1; i > Position && Current != null; i--)
            Current = Current.Next;
        return Current;
    }

    public bool Delete()
    {
        if (Head == null)
        {
            Console.WriteLine("The list is empty");
            return false;
        }

        Number Current;

        Current = Head.Next;
        Head.Next = Current;
        size--;
        return true;
    }

    public bool Find(Number toFind)
    {
        Number Current = new Number();

        if (toFind == null)
            return false;

        for (Current = Head; Current != null; Current = Current.Next)
        {
            if( Current.Item  == toFind.Item )
                return true;
        }

        return false;
    }
}

public class Exercise
{
    static int Main(string[] args)
    {
        Number  real;
        Numbers reals = new Numbers();

        real = new Number();
        real.Item = 2974.03;
        reals.Add(real);

        real = new Number();
        real.Item = 748.25;
        reals.Add(real);

        real = new Number();
        real.Item = 50883.82;
        reals.Add(real);

        real = new Number();
        real.Item = 29.24;
        reals.Add(real);

        real = new Number();
        real.Item = 772.85;
        reals.Add(real);

        real = new Number();
        real.Item = 106628.06;
        reals.Add(real);

        Console.WriteLine("Number of items: {0}", reals.Count);

        for (int i = 0; i < reals.Count; i++)
        {
            Number nbr = reals.Retrieve(i);
            Console.WriteLine("Number[{0}] = {1}", i, nbr.Item);
        }

        reals.Delete();

        Console.WriteLine("\nNumber of items: {0}", reals.Count);

        for (int i = 0; i < reals.Count; i++)
        {
            Number nbr = reals.Retrieve(i);
            Console.WriteLine("Number[{0}] = {1}", i, nbr.Item);
        }

        Number nbrToFind = new Number();
        nbrToFind.Item = 26486.56;

        bool Found = reals.Find(nbrToFind);
        if (Found == true)
            Console.WriteLine("\nThe number {0} was found in the list", 
    nbrToFind.Item);
        else
            Console.WriteLine("\nThe number {0} was NOT found in the list", 
    nbrToFind.Item);

        nbrToFind = new Number();
        nbrToFind.Item = 50883.82;

        Found = reals.Find(nbrToFind);
        if (Found == true)
            Console.WriteLine("The number {0} was found in the list\n", 
   nbrToFind.Item);
        else
            Console.WriteLine("The number {0} was NOT found in the list\n",
    nbrToFind.Item);

        return 0;
    }
}
This would produce:
Number of items: 6
Number[0] = 2974.03
Number[1] = 748.25
Number[2] = 50883.82
Number[3] = 29.24
Number[4] = 772.85
Number[5] = 106628.06

Number of items: 5
Number[0] = 2974.03
Number[1] = 748.25
Number[2] = 50883.82
Number[3] = 29.24
Number[4] = 106628.06

The number 26486.56 was NOT found in the list
The number 50883.82 was found in the list

Press any key to continue . . .
Introduction to Generic Linked Lists

 
Overview

The Numbers class we created is either non-professional or used in a restricted scenario in which you know the exact type of value you want to use. An alternative is to use a generic technique, in which you would not specify, in advance, the type of value you are dealing. You only indicate to the compiler that you are reserving a place holder for a type but the compiler has to wait until you want to create an actual collection to find out what type of value the items would be made of.
Creating a Node Class

Based on the rules of generics, to create a class that would be used for the items of your collection, you can name it Node (this is not a rule, just a habit), add the <> delimiters to its name and, inside the delimiters, enter a letter or word that represents the type. Here is an example:
public class Node<T>
{
    public T Value;
    public Node<T> Next;
}
 
Representing a Node in a Collection Class

Just as done for a linked list that uses an explicit type, when you start a generic collection class, you should (must) represent the node class, which is done using a field. Because this field primarily represents the beginning of the list, it is usually named head (or Head) or first (or First) (again, this is not a rule, only a habit).
When the collection starts, the first item has no value. Therefore, you should initialize it with null. This can be done in a constructor. Here is an example:
public class Node<T>
{
    public T Value;
    public Node<T> Next;
}

public class LinkedList<T>
{
    public Node<T> Head;
    private int nbrOfItems;

    public LinkedList()
    {
        First = Head;
        nbrOfItems = 0;
    }

    public int Count
    {
        get { return nbrOfItems; }
    }
    
    public bool IsEmpty
    {
        get
        {
            if (size == 0)
                return true;
            return false;
        }
    }
}
Introduction to Operations on a Generic Linked List

 
Adding an Item

The technique of adding an item to a generic linked list is the same as that of a generic linked list. You just have to use the type where the specific type would be used. Here is an example:
using System;

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

public class LinkedList<T>
{
    public Node<T> Head;
    private int nbrOfItems;

    public LinkedList()
    {
        Head = null;
        nbrOfItems = 0;
    }

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

    public void Add(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 = Head;
        // Indicate that the new item becomes the first of the collection
        Head = current;

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

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

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

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

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

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

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

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

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

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

        return 0;
    }
}
This would produce:
Number of Items: 0
-------------------------------------
Number of Items: 6
-------------------------------------
Press any key to continue . . .
Deleting an Item

To remove an item from a linked list, use the same steps we reviewed from the primitive type:
  1. Get a reference to the item that follows the head
  2. Assign the next item of that reference to the next item of the head
  3. Decrease the number of items of the collection
Here is an example:
using System;

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

public class LinkedList<T>
{
    . . . No Change

    public void Delete()
    {
        if (Head == null)
            return; // throw new NullReferenceException("The list is currently empty");
            
        Node<T> current;

        current = Head.Next;
        Head.Next = current;
        nbrOfItems--;
    }
}

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

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

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

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

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

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

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

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

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

        employees.Delete();
        employees.Delete();

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

        return 0;
    }
}
This would produce:
Number of Items: 0
-------------------------------------
Number of Items: 6
-------------------------------------
Number of Items: 4
-------------------------------------
Press any key to continue . . .
Clearing a Collection

The simplest way to remove all items from a linked list consists of reset its number of items to 0. Here is an example:
using System;

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

public class LinkedList<T>
{
    . . . No Change

    public void Clear()
    {
        nbrOfItems = 0;
    }
}

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

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

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

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

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

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

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

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

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

        employees.Delete();

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

        employees.Clear();

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

        return 0;
    }
}
This would produce:
Number of Items: 0
-------------------------------------
Number of Items: 6
-------------------------------------
Number of Items: 5
-------------------------------------
Number of Items: 0
-------------------------------------
Press any key to continue . . .
Getting the List

 
Introduction

Most of the time, when dealing with a linked list, you visit each item. Probably the easiest way to display the items of a list consists of calling the console to show the item's value while you are at its location. Here is an example:
using System;

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

public class LinkedList<T>
{
    . . . No Change

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

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

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

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

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

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

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

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

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

        Console.WriteLine("-------------------------------------");
        Console.WriteLine("Number of Items: {0}", employees.Count);

        return 0;
    }
}
This would produce:
Number of Items: 0
-------------------------------------
Current List: Alan Baxter -
Current List: Joan Bramble - Alan Baxter -
Current List: Lionel Berg - Joan Bramble - Alan Baxter -
Current List: Flora Bruze - Lionel Berg - Joan Bramble - Alan Baxter -
Current List: Christopher Fox - Flora Bruze - Lionel Berg - Joan Bramble - Alan Baxter -
Current List: Holly Madsen - Christopher Fox - Flora Bruze - Lionel Berg - Joan Bramble - Alan Baxter -
-------------------------------------
Number of Items: 6
Press any key to continue . . .
Looping in the List

There are various ways you can get items from a list. You can get one item at a time or you can get a list of all items that are currently in the collection. To get one item, you have many options. You can create a method that is passed an index as argument. In the method, make sure the index passed as arguments is within the range of the number of items in the list. Also, make sure the list is not empty. If these two conditions are met, scan the list until you get to the index passed as argument, then return the item at that position. This can be done as follows:
using System;

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

public class LinkedList<T>
{
    . . . No Change

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

        for (int i = nbrOfItems - 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>();

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

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

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

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

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

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

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

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

        Console.WriteLine("-------------------------------------");
        Console.WriteLine("Number of Items: {0}", employees.Count);

        return 0;
    }
}
This would produce:
Number of Items: 0
-------------------------------------
Number 1: Alan Baxter
Number 2: Joan Bramble
Number 3: Lionel Berg
Number 4: Flora Bruze
Number 5: Christopher Fox
Number 6: Holly Madsen
-------------------------------------
Number of Items: 6
Press any key to continue . . .
Although not regularly used, an alternative to the above Get() function consists of createing a read-only indexed property. In its get accessor, provide the exact same mechanism as above. Here is an example:
public class Node<T>
{
    public T Value;
    public Node<T> Next;
}

public class LinkedList<T>
{
    . . . No Change
    
    public Node<T> Get(int index)
    {
        Node<T> current = Head;

        for (int i = nbrOfItems - 1; (i > index) && (current != null); i--)
            current = current.Next;
        return current;
    }
    
    public Node<T> this[int index]
    {
        get
        {
            Node<T> current = Last;

            for (int i = nbrOfItems - 1; (i > index) && (current != null); i--)
                current = current.Next;
            return current;
        }
    }
}
Converting a List to String

Another solution is to store the whole collection of items in a value, then access that value if or when you want the list. To implement this solution, you can override the ToString() method. In the method, get a reference to the first item of the list. Use a loop to visit each item of the collection. When you get to an item, store it in the value you will return. At the end of the method, return the variable that holds the collection. This can be done as follows:
using System;

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

public class LinkedList<T>
{
    public Node<T> Head;
    private int nbrOfItems;

    public LinkedList()
    {
        Head = null;
        nbrOfItems = 0;
    }

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

    public void Add(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 = Head;
        // Indicate that the new item becomes the first of the collection
        Head = current;

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

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

        Node<T> current;

        current = Head.Next;
        Head.Next = current;
        nbrOfItems--;
    }

    public void Clear()
    {
        nbrOfItems = 0;
    }

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

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

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

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

        if (Head == null)
            return "The list is currently empty"; // throw new NullReferenceException("The list is currently empty");
        else
        {
            for (int i = 0; i < nbrOfItems; 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>();

        Console.WriteLine("Number of Items: {0}", employees.Count);
        Console.WriteLine("-------------------------------------");

        Console.WriteLine("Current List: {0}", employees);

        name = new Node<string>();
        name.Value = "Alan Baxter";
        employees.Add(name);
        Console.WriteLine("Current List: {0}", employees);

        name = new Node<string>();
        name.Value = "Joan Bramble";
        employees.Add(name);
        Console.WriteLine("Current List: {0}", employees);

        name = new Node<string>();
        name.Value = "Lionel Berg";
        employees.Add(name);
        Console.WriteLine("Current List: {0}", employees);

        name = new Node<string>();
        name.Value = "Flora Bruze";
        employees.Add(name);
        Console.WriteLine("Current List: {0}", employees);

        name = new Node<string>();
        name.Value = "Christopher Fox";
        employees.Add(name);
        Console.WriteLine("Current List: {0}", employees);

        name = new Node<string>();
        name.Value = "Holly Madsen";
        employees.Add(name);
        Console.WriteLine("Current List: {0}", employees);

        Console.WriteLine("-------------------------------------");
        Console.WriteLine("Number of Items: {0}", employees.Count);

        return 0;
    }
}
This would produce:
Number of Items: 0
-------------------------------------
Current List:
Current List: - Alan Baxter -
Current List: - Joan Bramble - Alan Baxter -
Current List: - Lionel Berg - Joan Bramble - Alan Baxter -
Current List: - Flora Bruze - Lionel Berg - Joan Bramble - Alan Baxter -
Current List: - Christopher Fox - Flora Bruze - Lionel Berg - Joan Bramble - Alan Baxter -
Current List: - Holly Madsen - Christopher Fox - Flora Bruze - Lionel Berg - Joan Bramble - Alan Baxter -
-------------------------------------
Number of Items: 6
Press any key to continue . . .
Posted by at No comments :
Labels: , ,
Subscribe to: Posts ( Atom )