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.
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; } } }
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:
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; }
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:
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; }
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++; } }
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.
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.
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 . . .
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.
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; }
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; } } }
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 . . .
To remove an item from a linked list, use the same steps we reviewed from the primitive type:
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 . . .
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 . . .
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 . . .
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;
}
}
}
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 . . .
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||