In reality, there are various types of linked lists. A singly linked list is a one-way directional list where each item points (only) to the item next to it (in a somewhat right direction). The description we just gave is conform to a singly linked list. Another type is the doubly linked list:
The last type of linked list is called a circular linked list. This list is primarily created as either a singly linked list or a doubly linked list:
Although you can create a linked list collection class from scratch, to assist you, the .NET Framework provides a class named LinkedList and that is a member of the System.Collections.Generic namespace. LinkedList is a generic collection class with three constructors. The default constructor allows you to create an empty linked list. Here is an example of using it: using System;
using System.Windows.Forms;
using System.Collections.Generic;
public class LinkedListExample : Form
{
Button btnLinkedList;
public LinkedListExample()
{
InitializeComponent();
}
private void InitializeComponent()
{
btnLinkedList = new Button();
btnLinkedList.Location = new System.Drawing.Point(12, 12);
btnLinkedList.Text = "Linked List";
btnLinkedList.Click += new EventHandler(btnLinkedListClicked);
Controls.Add(btnLinkedList);
Text = "Linked List Example";
StartPosition = FormStartPosition.CenterScreen;
}
private void btnLinkedListClicked(object sender, EventArgs e)
{
LinkedList<double> numbers = new LinkedList<double>();
}
}
public class Exercise
{
public static int Main()
{
Application.EnableVisualStyles();
Application.SetCompatibleTextRenderingDefault(false);
Application.Run(new LinkedListExample());
return 0;
}
}
Another constructor allows you to create a linked using an existing list. Its syntax is: public LinkedList(IEnumerable<T> collection); The argument can be a variable from any class that implements the IEnumerable<T> interface. Here is an example of using this second constructor: private void btnLinkedListClicked(object sender, EventArgs e)
{
List<double> values = new List<double>();
values.Add(84.597);
values.Add(6.47);
values.Add(2747.06);
values.Add(282.924);
LinkedList<double> numbers = new LinkedList<double>(values);
}
As mentioned already, it is a tradition to call an item of a linked list a node. To define a node as a true object, the .NET Framework provides the LinkedListNode sealed class: public sealed class LinkedListNode<T> This class has only properties, no methods.
The LinkedList class starts as follows: public class LinkedList<T> : ICollection<T>,
IEnumerable<T>,
ICollection, IEnumerable,
ISerializable,
IDeserializationCallback
As you can see, the LinkedList class implements the ICollection interface. This gives it a Count property that produces the number of nodes. Here is an example of accessing it: private void btnLinkedListClicked(object sender, EventArgs e)
{
List<double> values = new List<double>();
values.Add(84.597);
values.Add(6.47);
values.Add(2747.06);
values.Add(282.924);
LinkedList<double> numbers = new LinkedList<double>(values);
MessageBox.Show("There are " + numbers.Count.ToString() + " numbers in the list",
"Linked List",
MessageBoxButtons.OK, MessageBoxIcon.Information);
}
The primary operation to perform on a linked list is to add a new node to it. To support it, the LinkedList class is equipped with various methods. One of them is named AddLast that is overloaded in two versions. One of them uses the following syntax: public LinkedListNode<T> AddLast(T value); This method expects the new value as argument. Here is an example of calling it: using System;
using System.Windows.Forms;
using System.Collections.Generic;
public class LinkedListExample : Form
{
Button btnLinkedList;
public LinkedListExample()
{
InitializeComponent();
}
private void InitializeComponent()
{
btnLinkedList = new Button();
btnLinkedList.Location = new System.Drawing.Point(12, 12);
btnLinkedList.Text = "Linked List";
btnLinkedList.Click += new EventHandler(btnLinkedListClicked);
Controls.Add(btnLinkedList);
Text = "Linked List Example";
StartPosition = FormStartPosition.CenterScreen;
}
private void btnLinkedListClicked(object sender, EventArgs e)
{
LinkedList<double> numbers = new LinkedList<double>();
numbers.AddLast(148.24);
}
}
public class Exercise
{
public static int Main()
{
Application.EnableVisualStyles();
Application.SetCompatibleTextRenderingDefault(false);
Application.Run(new LinkedListExample());
return 0;
}
}
Another version of this method is: public void AddLast(LinkedListNode<T> node); This version expects a LinkedListNode object as argument. Here is an example of calling it: private void btnLinkedListClicked(object sender, EventArgs e)
{
LinkedList<double> numbers = new LinkedList<double>();
LinkedListNode<double> number = new LinkedListNode<double>(148.24);
numbers.AddLast(number);
}
In the same way, you can use this method to add new items. Here are examples: private void btnLinkedListClicked(object sender, EventArgs e)
{
LinkedList<double> numbers = new LinkedList<double>();
LinkedListNode<double> number = new LinkedListNode<double>(148.24);
numbers.AddFirst(number);
number = new LinkedListNode<double>(35.75);
numbers.AddLast(number);
number = new LinkedListNode<double>(2222.06);
numbers.AddLast(number);
number = new LinkedListNode<double>(4.19);
numbers.AddLast(number);
number = new LinkedListNode<double>(66.18);
numbers.AddLast(number);
}
Because the LinkedList implements the ICollection interface, it inherits the Contains method. As a reminder, its syntax is: public bool Contains(T value); This method checks whether the linked list contains the (a) node that has the value passed as argument. If that node is found, the method returns true. Otherwise it returns false. Here is an example of calling it: private void btnLinkedListClicked(object sender, EventArgs e)
{
List<double> values = new List<double>();
values.Add(84.597);
values.Add(6.47);
values.Add(2747.06);
values.Add(282.924);
LinkedList<double> numbers = new LinkedList<double>(values);
LinkedListNode<double> number = new LinkedListNode<double>(148.24);
numbers.AddFirst(number);
number = new LinkedListNode<double>(35.75);
numbers.AddFirst(number);
number = new LinkedListNode<double>(2222.06);
numbers.AddFirst(number);
number = new LinkedListNode<double>(4.19);
numbers.AddFirst(number);
number = new LinkedListNode<double>(66.18);
numbers.AddFirst(number);
if( numbers.Contains(2222.06) == true )
MessageBox.Show("The list contains 2222.06.",
"Linked List",
MessageBoxButtons.OK, MessageBoxIcon.Information);
else
MessageBox.Show("There is no such a number in the list.",
"Linked List",
MessageBoxButtons.OK, MessageBoxIcon.Information);
This method works only if the type of the node is able to perform the comparison for equality. If you are using values of primitive types (int, char, double, DateTime, etc) or string, the method would work fine. If you are using your own class, make sure you override the Equals() method.
While the Contains() method is used to look for a value in a linked list, it only lets you know whether the value was found. If you want to get the actual node that has that value, you can call the Find() method. Its syntax is: public LinkedListNode<T> Find(T value); When this method is called, it starts looking for the value in the linked list. If it finds it, it returns its node. If there is more than one node with that value, the method returns only the first node that has that value. Here is an example of calling this method: private void btnLinkedListClicked(object sender, EventArgs e)
{
List<double> values = new List<double>();
values.Add(84.597);
values.Add(6.47);
values.Add(2747.06);
values.Add(282.924);
LinkedList<double> numbers = new LinkedList<double>(values);
LinkedListNode<double> number = new LinkedListNode<double>(148.24);
numbers.AddFirst(number);
number = new LinkedListNode<double>(35.75);
numbers.AddFirst(number);
number = new LinkedListNode<double>(2222.06);
numbers.AddFirst(number);
numbers.AddFirst(2747.06);
number = new LinkedListNode<double>(4.19);
numbers.AddFirst(number);
number = new LinkedListNode<double>(66.18);
numbers.AddFirst(number);
if( numbers.Find(2747.06) != null )
MessageBox.Show("2747.06 was found in the list.",
"Linked List",
MessageBoxButtons.OK, MessageBoxIcon.Information);
else
MessageBox.Show("2747.06 is nowhere in the list.",
"Linked List",
MessageBoxButtons.OK, MessageBoxIcon.Information);
}
If the list contains more than one node that has the value but you prefer to use the last node, you can call the FindLast() method. public LinkedListNode<T> FindLast(T value); Once again, remember that these two methods are ready to work on primitive types. If you are using your own class for the type of node, you should (must) override the Equals() method.
As you can see, the LinkedList class doesn't implement the IList interface, which means it doesn't have an Item property. As we have seen with the AddLast() method and as we will see in the next sections, each method used to add a node is provided in two versions. One of the versions returns a LinkedListNode object. This means that, when performing an addition operation, you can get the returned value and do what you want with it. The class implements the IEnumerable interface. This makes it possible to use foreach to get to access each node. This can be done as follows: private void btnLinkedListClicked(object sender, EventArgs e)
{
LinkedList<double> numbers = new LinkedList<double>();
LinkedListNode<double> number = new LinkedListNode<double>(148.24);
numbers.AddFirst(number);
foreach (double nbr in numbers)
MessageBox.Show(nbr.ToString());
}
As mentioned already, a linked list has a first and a last nodes (some people or documentations call them the head and the tail). To identify the first node, the LinkedList class is equippped with a read-only property named First. Its syntax is: public LinkedListNode<T> First { get; }
The last node is represented by a read-only property of the same name and that, too, is a LinkedListNode object: public LinkedListNode<T> Last { get; }
Here are examples of accessing these properties: private void btnLinkedListClicked(object sender, EventArgs e)
{
LinkedList<double> numbers = new LinkedList<double>();
LinkedListNode<double> number = new LinkedListNode<double>(148.24);
numbers.AddFirst(number);
number = new LinkedListNode<double>(35.75);
numbers.AddFirst(number);
number = new LinkedListNode<double>(2222.06);
numbers.AddFirst(number);
number = new LinkedListNode<double>(4.19);
numbers.AddFirst(number);
number = new LinkedListNode<double>(66.18);
numbers.AddFirst(number);
MessageBox.Show("The value of the first node is " + numbers.First.Value);
MessageBox.Show("The value of the last node is " + numbers.Last.Value);
}
To access a node that is next to an existing node, you must first know what node is used as reference. To let you access the next node, the LinkedListNode class is equipped with a read-only property named Next: public LinkedListNode<T> Next { get; }
To let you access the node previous to an existing one, the LinkedListNode class is equipped with the read-only Previous property: public LinkedListNode Remember that in both cases, you need a node as reference.
When dealing with a linked list, you have many options on how to add a new node. As mentioned already, a linked list has a first node, a last node, and one or more nodes between them. All nodes have and use some references with regards to the node(s) close to them. Based on this, when adding a new node, you have to specify whether you want it as the first node, the last node, the node before a certain node, or the node after a certain one. The LinkedList class easily supports all these operations with very little effort on your part. We saw that you could call the AddFirst() method to add a new node. In reality, there is no such a thing as simply adding a new node to a linked list. When a linked list has just been created and it is empty, it holds a reference to a null node. There is nothing you can do with that node and you don't need to do anything with it. To start adding nodes, you have the option of setting it as the first or the last item. This would not make any difference because there is no other node in the list. After adding a node, it becomes a reference that new nodes can use. If you call the AddFirst() method, the new node would be added before any existing node in the collection.
By contrast, you can call a method named AddLast. It is overloaded with versions whose syntaxes are: public LinkedListNode<T> AddLast(T value); public void AddLast(LinkedListNode<T> node); When you call this method, the value or node you pass will be added as the last item in the list. Here is an example: using System;
using System.Windows.Forms;
using System.Collections.Generic;
public class LinkedListExample : Form
{
Button btnLinkedList;
ListBox lbxLinkedList;
public LinkedListExample()
{
InitializeComponent();
}
private void InitializeComponent()
{
btnLinkedList = new Button();
btnLinkedList.Location = new System.Drawing.Point(12, 12);
btnLinkedList.Text = "Linked List";
btnLinkedList.Click += new EventHandler(btnLinkedListClicked);
lbxLinkedList = new ListBox();
lbxLinkedList.Location = new System.Drawing.Point(12, 40);
lbxLinkedList.Height = 140;
Controls.Add(btnLinkedList);
Controls.Add(lbxLinkedList);
Text = "Linked List";
StartPosition = FormStartPosition.CenterScreen;
}
private void btnLinkedListClicked(object sender, EventArgs e)
{
List<double> values = new List<double>();
values.Add(84.597);
values.Add(6.47);
values.Add(2747.06);
values.Add(282.924);
LinkedList<double> numbers = new LinkedList<double>(values);
LinkedListNode<double> number = new LinkedListNode<double>(148.24);
numbers.AddFirst(number);
number = new LinkedListNode<double>(35.75);
numbers.AddFirst(number);
numbers.AddLast(2747.06);
number = new LinkedListNode<double>(2222.06);
numbers.AddFirst(number);
number = new LinkedListNode<double>(4.19);
numbers.AddFirst(number);
number = new LinkedListNode<double>(66.18);
numbers.AddFirst(number);
foreach (double dbl in numbers)
lbxLinkedList.Items.Add(dbl);
}
}
public class Exercise
{
public static int Main()
{
Application.EnableVisualStyles();
Application.SetCompatibleTextRenderingDefault(false);
Application.Run(new LinkedListExample());
return 0;
}
}
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Topic
Applied: Introducing Linked Lists
