C# Examples - Linked Lists

	Linked Lists

Overview of Lists

Introduction

A linked list is a technique of creating a list with the ability to add, delete, or retrieve items. Additional operations can also be provided to a more elaborate list such as finding an item, deleting an item, etc.

The Items of a List

Before creating a list, you probably should first decide or define what the list would be made of. As different as they are, one list can be made of numbers. For example, a list that will be made of numbers can define the item's class as follows:

class Items
{
	double Number;
}

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. For example, if you are starting a database for a car part dealer, you may want to create a list that includes information about car parts. The class that holds information for a part can be created as follows:

class CarPart
{
	public long   PartNumber;
	public string PartName;
	public double UnitPrice;
};

Implementing a Linked List

Introduction

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. Here is an example:

using System;

class CarPart
{
	public long   PartNumber;
	public string PartName;
	public double UnitPrice;
};

class ListOfParts
{
	public ListOfParts()
	{
	}
}

class Exercise
{
	static int Main()
	{
		ListOfParts Parts = new ListOfParts();
		return 0;
	}
}

It is commonly a good practice to include in a class' list a member that can be used to keep track of the number of items in the list. You can declare such a member variable as public but because it is a regular member variable, it is also a habit of OOP developers to make such a member private. If you do this and if you want the value to be accessed outside, you should then provide a public method that serves as the entry point. Here is how this can be done:

using System;

class CarPart
{
	public long   PartNumber;
	public string PartName;
	public double UnitPrice;
};

class ListOfParts
{
	private int size;

	public ListOfParts()
	{
		size = 0;
	}
	
	public int Count
	{
		get { return size; }
	}
}

class Exercise
{
	static int Main()
	{
		ListOfParts Parts = new ListOfParts();

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

		return 0;
	}
}

This would produce:

Number of Parts: 0

The Beginning of a Linked List

If you create an array-based list, you can start by declaring an array member variable that would hold the items and each item can be located by an index that is assigned to it when the item is added to the list. When you do this, you must provide an estimate of the maximum number of items that will be allowed in the list. Without good planning, the dimension you specify could be too high or too low but C# doesn't allow you to declare an array without a dimension if you are not initializing the array. This means that, when you create an array-based list, you must also specify the maximum number of items that the list can hold.

A linked list is a list that can grow or shrink as the user wishes. This means that, when creating the list, you don't need to predict the maximum number of items that will be added to the list. To use this flexibility, the items must be managed through pointers. Because the list would use a member that defines its item, you can declare a member variable that is conform to the intended items.

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. This 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. Although this member is declared as a pointer and it marks the beginning of the list, you should not allocate memory for it in the constructor. Its memory would be managed when it is accessed. Therefore, you can simply initialize is as null. Here is an example:

class ListOfParts
{
	private int size;

	public ListOfParts()
	{
		size = 0;
		Head = null;
	}
	
	public int Count
	{
		get { return size; }
	}
	
	public CarPart Head;
}

The Linking of a List

As mentioned already, each member of an array-based list can be accessed using its index, stored in an item member variable declared as an array. Because the items of a linked list are not indexed, you must provide another mechanism to locate an item in the list. The easiest way to do this is to first locate an item, then ask that item to provide you with a pointer to the item that succeeds it. If the list is empty, this information would be provided as null. If the item you first access is the last in the list, you would also provide nothing. Any other item in the middle would give you access to the next item in the list. To support this theory, you must provide a pointer to the next item in the list as a member variable to the class that holds the item. As a tradition, this member variable is called Next but you can give it any name you want. Because this item actually is a complete one, it must be declared as a self-referencing member that has the same name as its class:

class CarPart
{
	public long PartNumber;
	public string PartName;
	public double UnitPrice;

	public CarPart Next;
}

Operations of a Linked List

Item Addition

The primary operation you can perform on a list is to add a new item to it, since a list is fundamentally empty when it starts. In order to indicate that you want to add an item to the list, you can declare 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:

using System;

class CarPart
{
	public long   PartNumber;
	public string PartName;
	public double UnitPrice;

	public CarPart Next;
};

class ListOfParts
{
	private int size;

	public ListOfParts()
	{
		size = 0;
		Head = null;
	}
	
	public int Count
	{
		get { return size; }
	}
	
	public CarPart Head;

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

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

class Exercise
{
	static int Main()
	{
		ListOfParts Parts = new ListOfParts();
		CarPart     Part;

		Part  = new CarPart();
		Part.PartNumber = 9743;
		Part.PartName = "Air Filter";
		Part.UnitPrice  = 8.75;
		Parts.Add(Part);
	
		Part  = new CarPart();
		Part.PartNumber = 27487;
		Part.PartName = "Clutch Disk";
		Part.UnitPrice  = 47.15;
		Parts.Add(Part);

		Part  = new CarPart();
		Part.PartNumber = 87873;
		Part.PartName = "Brake Disk";
		Part.UnitPrice  = 35.15;
		Parts.Add(Part);

		Part  = new CarPart();
		Part.PartNumber = 27644;
		Part.PartName = "A/C Filter Drier";
		Part.UnitPrice  = 55.55;
		Parts.Add(Part);

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

		return 0;
	}
}

This would produce:

Number of Parts: 4

Item Retrieval

Once a list exists, the user can explorer it. One of the operations performed on items is to locate and retrieve one. To do this, you can declare a method that takes as argument as 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 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;

class CarPart
{
	public long   PartNumber;
	public string PartName;
	public double UnitPrice;

	public CarPart Next;
};

class ListOfParts
{
	private int size;

	public ListOfParts()
	{
		size = 0;
		Head = null;
	}
	
	public int Count
	{
		get { return size; }
	}
	
	public CarPart Head;

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

		Sample      = NewItem;
		Sample.Next = Head;
		Head        = Sample;
		return size++;
	}
	
	public CarPart Retrieve(int Position)
	{
		CarPart Current = Head;

		for(int i = 0; i < Position && Current != null; i++)
			Current = Current.Next;
		return Current;
	}
}

class Exercise
{
	static int Main()
	{
		ListOfParts Parts = new ListOfParts();
		CarPart     Part;

		Part  = new CarPart();
		Part.PartNumber = 9743;
		Part.PartName = "Air Filter";
		Part.UnitPrice  = 8.75;
		Parts.Add(Part);
	
		Part  = new CarPart();
		Part.PartNumber = 27487;
		Part.PartName = "Clutch Disk";
		Part.UnitPrice  = 47.15;
		Parts.Add(Part);

		Part  = new CarPart();
		Part.PartNumber = 87873;
		Part.PartName = "Brake Disk";
		Part.UnitPrice  = 35.15;
		Parts.Add(Part);

		Part  = new CarPart();
		Part.PartNumber = 27644;
		Part.PartName = "A/C Filter Drier";
		Part.UnitPrice  = 55.55;
		Parts.Add(Part);
		
		Console.WriteLine(" -=- Store Inventory -=-");
		Console.WriteLine("Number of Parts: {0}", Parts.Count);

		for(int i = 0; i < Parts.Count; i++)
		{
			CarPart part = Parts.Retrieve(i);
			Console.WriteLine("\nCar Part Information");
			Console.WriteLine("Part #:      {0}", part.PartNumber);
			Console.WriteLine("Description: {0}", part.PartName);
			Console.WriteLine("Unit Price:  {0:C}", part.UnitPrice);
		}

		return 0;
	}
}

This would produce:

Number of Parts: 4

Car Part Information
Part #:      27644
Description: A/C Filter Drier
Unit Price: $55.55

Car Part Information
Part #:      87873
Description: Brake Disk
Unit Price: $35.15

Car Part Information
Part #:      27487
Description: Clutch Disk
Unit Price: $47.15

Car Part Information
Part #:      9743
Description: Air Filter
Unit Price: $8.75

Item Deletion

Deleting an item consists of removing it from the list. There are two main types of deletion you can perform on a list. 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 routines operations such as decrementing the count of items in the list. Here is an example:

using System;

class CarPart
{
	public long   PartNumber;
	public string PartName;
	public double UnitPrice;

	public CarPart Next;
};

class ListOfParts
{
	private int size;

	public ListOfParts()
	{
		size = 0;
		Head = null;
	}
	
	public int Count
	{
		get { return size; }
	}
	
	public CarPart Head;

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

		Sample      = NewItem;
		Sample.Next = Head;
		Head        = Sample;
		return size++;
	}
	
	public CarPart Retrieve(int Position)
	{
		CarPart Current = Head;

		for(int i = 0; i < Position && Current != null; i++)
			Current = Current.Next;
		return Current;
	}

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

		CarPart Current;

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

class Exercise
{
	static int Main()
	{
		ListOfParts Parts = new ListOfParts();
		CarPart     Part;

		Part  = new CarPart();
		Part.PartNumber = 9743;
		Part.PartName = "Air Filter";
		Part.UnitPrice  = 8.75;
		Parts.Add(Part);
	
		Part  = new CarPart();
		Part.PartNumber = 27487;
		Part.PartName = "Clutch Disk";
		Part.UnitPrice  = 47.15;
		Parts.Add(Part);

		Part  = new CarPart();
		Part.PartNumber = 87873;
		Part.PartName = "Brake Disk";
		Part.UnitPrice  = 35.15;
		Parts.Add(Part);

		Part  = new CarPart();
		Part.PartNumber = 27644;
		Part.PartName = "A/C Filter Drier";
		Part.UnitPrice  = 55.55;
		Parts.Add(Part);
		
		Console.WriteLine(" -=- Store Inventory -=-");
		Console.WriteLine("Number of Parts: {0}", Parts.Count);

		for(int i = 0; i < Parts.Count; i++)
		{
			CarPart part = Parts.Retrieve(i);
			Console.WriteLine("\nCar Part Information");
			Console.WriteLine("Part #:      {0}", part.PartNumber);
			Console.WriteLine("Description: {0}", part.PartName);
			Console.WriteLine("Unit Price:  {0:C}", part.UnitPrice);
		}

		Parts.Delete();

		Console.WriteLine("\n -=- Store Inventory -=-");
		Console.WriteLine("Number of Parts: {0}", Parts.Count);

		for(int i = 0; i < Parts.Count; i++)
		{
			CarPart part = Parts.Retrieve(i);
			Console.WriteLine("\nCar Part Information");
			Console.WriteLine("Part #:      {0}", part.PartNumber);
			Console.WriteLine("Description: {0}", part.PartName);
			Console.WriteLine("Unit Price:  {0:C}", part.UnitPrice);
		}

		Console.WriteLine();
		return 0;
	}
}

This would produce:

Number of Parts: 4

-=- List of Parts -=-
Car Part Information
Part #:      27644
Description: A/C Filter Drier
Unit Price: $55.55

Car Part Information
Part #:      87873
Description: Brake Disk
Unit Price: $35.15

Car Part Information
Part #:      27487
Description: Clutch Disk
Unit Price: $47.15

Car Part Information
Part #:      9743
Description: Air Filter
Unit Price: $8.75

Number of Parts: 3

-=- List of Parts -=-
Car Part Information
Part #:      27644
Description: A/C Filter Drier
Unit Price: $55.55

Car Part Information
Part #:      27487
Description: Clutch Disk
Unit Price: $47.15

Car Part Information
Part #:      9743
Description: Air Filter
Unit Price: $8.75

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, or null, depending on how you create it. Here is an example:

using System;

class CarPart
{
	public long   PartNumber;
	public string PartName;
	public double UnitPrice;

	public CarPart Next;
};

class ListOfParts
{
	private int size;

	public ListOfParts()
	{
		size = 0;
		Head = null;
	}
	
	public int Count
	{
		get { return size; }
	}
	
	public CarPart Head;

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

		Sample      = NewItem;
		Sample.Next = Head;
		Head        = Sample;
		return size++;
	}
	
	public CarPart Retrieve(int Position)
	{
		CarPart Current = Head;

		for(int i = 0; i < Position && Current != null; i++)
			Current = Current.Next;
		return Current;
	}

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

		CarPart Current;

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

	public bool Delete(int Position)
	{
		if( this.Retrieve(Position) == null )
			return false;

		this.Retrieve(Position - 1).Next = this.Retrieve(Position + 1);
		size--;
		return true;
	}
}

class Exercise
{
	static int Main()
	{
		ListOfParts Parts = new ListOfParts();
		CarPart     Part;

		Part  = new CarPart();
		Part.PartNumber = 9743;
		Part.PartName = "Air Filter";
		Part.UnitPrice  = 8.75;
		Parts.Add(Part);
	
		Part  = new CarPart();
		Part.PartNumber = 27487;
		Part.PartName = "Clutch Disk";
		Part.UnitPrice  = 47.15;
		Parts.Add(Part);

		Part  = new CarPart();
		Part.PartNumber = 87873;
		Part.PartName = "Brake Disk";
		Part.UnitPrice  = 35.15;
		Parts.Add(Part);

		Part  = new CarPart();
		Part.PartNumber = 27644;
		Part.PartName = "A/C Filter Drier";
		Part.UnitPrice  = 55.55;
		Parts.Add(Part);
		
		Console.WriteLine(" -=- Store Inventory -=-");
		Console.WriteLine("Number of Parts: {0}", Parts.Count);

		for(int i = 0; i < Parts.Count; i++)
		{
			CarPart part = Parts.Retrieve(i);
			Console.WriteLine("\nCar Part Information");
			Console.WriteLine("Part #:      {0}", part.PartNumber);
			Console.WriteLine("Description: {0}", part.PartName);
			Console.WriteLine("Unit Price:  {0:C}", part.UnitPrice);
		}

		Parts.Delete(2);

		Console.WriteLine("\n -=- Store Inventory -=-");
		Console.WriteLine("Number of Parts: {0}", Parts.Count);

		for(int i = 0; i < Parts.Count; i++)
		{
			CarPart part = Parts.Retrieve(i);
			Console.WriteLine("\nCar Part Information");
			Console.WriteLine("Part #:      {0}", part.PartNumber);
			Console.WriteLine("Description: {0}", part.PartName);
			Console.WriteLine("Unit Price:  {0:C}", part.UnitPrice);
		}

		Console.WriteLine();
		return 0;
	}
}

This would produce:

Number of Parts: 4

-=- List of Parts -=-
Car Part Information
Part #:      27644
Description: A/C Filter Drier
Unit Price: $55.55

Car Part Information
Part #:      87873
Description: Brake Disk
Unit Price: $35.15

Car Part Information
Part #:      27487
Description: Clutch Disk
Unit Price: $47.15

Car Part Information
Part #:      9743
Description: Air Filter
Unit Price: $8.75

Number of Parts: 3

-=- List of Parts -=-
Car Part Information
Part #:      27644
Description: A/C Filter Drier
Unit Price: $55.55

Car Part Information
Part #:      87873
Description: Brake Disk
Unit Price: $35.15

Car Part Information
Part #:      9743
Description: Air Filter
Unit Price: $8.75

Item Location

One of the operations hardly performed on a list is to find one. 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 item is found in the list would it be recognized. In the source code, we implement this method as Find().

There are different ways you can try locating an item in a list. For example, you can provide partial information and try locating all items that match such an entry. Here is an example:

Linked List Source Code

using System;

class CarPart
{
	public long PartNumber;
	public string PartName;
	public double UnitPrice;

	public CarPart Next;
}

class ListOfParts
{
	private int size;

	public ListOfParts()
	{
		size = 0;
		Head = null;
	}
	public int Count
	{
		get { return size; }
	}

	public CarPart Head;

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

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

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

		for(int i = 0; i < Position && Current != null; i++)
			Current = Current.Next;
		return Current;
	}

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

		CarPart Current;

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

	public bool Delete(int Position)
	{
		if( this.Retrieve(Position) == null )
			return false;

		this.Retrieve(Position - 1).Next = this.Retrieve(Position + 1);
		size--;
		return true;
	}

	public bool Find(CarPart ItemToFind)
	{
		CarPart Current = new CarPart();

		if( ItemToFind == null )
			return false;
			
		for(Current = Head; Current != null; Current = Current.Next)
		{
			if( (Current.PartNumber == ItemToFind.PartNumber) &&
				(Current.PartName   == ItemToFind.PartName) &&
				(Current.UnitPrice  == ItemToFind.UnitPrice) )
				return true;
		}

		return false;
	}
}

class Exercise
{
	static int Main()
	{
		ListOfParts Parts = new ListOfParts();
		CarPart     Part;
		CarPart     PartToFind;

		Part  = new CarPart();
		Part.PartNumber = 9743;
		Part.PartName = "Air Filter";
		Part.UnitPrice  = 8.75;
		Parts.Add(Part);
	
		Part  = new CarPart();
		Part.PartNumber = 27487;
		Part.PartName = "Clutch Disk";
		Part.UnitPrice  = 47.15;
		Parts.Add(Part);

		Part  = new CarPart();
		Part.PartNumber = 87873;
		Part.PartName = "Brake Disk";
		Part.UnitPrice  = 35.15;
		Parts.Add(Part);

		Part  = new CarPart();
		Part.PartNumber = 27644;
		Part.PartName = "A/C Filter Drier";
		Part.UnitPrice  = 55.55;
		Parts.Add(Part);

		Console.WriteLine(" -=- Store Inventory -=-");
		Console.WriteLine("Number of Parts: {0}", Parts.Count);

		for(int i = 0; i < Parts.Count; i++)
		{
			CarPart part = Parts.Retrieve(i);
			Console.WriteLine("\nCar Part Information");
			Console.WriteLine("Part #:      {0}", part.PartNumber);
			Console.WriteLine("Description: {0}", part.PartName);
			Console.WriteLine("Unit Price:  {0:C}", part.UnitPrice);
		}

		PartToFind = new CarPart();
		PartToFind.PartNumber = 87873;
		PartToFind.PartName = "Brake Disk";
		PartToFind.UnitPrice  = 35.15;

		bool Found = Parts.Find(PartToFind);
		if( Found == true )
			Console.WriteLine("\nItem was found\n");
		else
			Console.WriteLine("\nItem not found\n");

		Console.WriteLine();
		return 0;
	}
}


Home	Copyright � 2004-2014 FunctionX. Inc.