The New LinkedList Class and Iterator Class in C#

13

Jan

we need a header field and a constructor method to instantiate the list.

public class LinkedList()
{
private Node header;
public LinkedList()
{

header = new Node("header");
}
public bool IsEmpty() {
return (header.Link == null);
}
public Node GetFirst() {
return header;
}
public void ShowList() {
Node current = header.Link;
while (!(current == null)) {
Console.WriteLine(current.Element);
current = current.Link;
}
}
}

Demonstrating the Iterator Class

Using the Iterator class, it’s easy to write an interactive program to move through a linked list. This also gives us a chance to put all the code for both the Iterator class and the LinkedList class in one place.

using System;
public class Node
{
public Object Element;
public Node Link;
public Node()
{
Element = null;
Link = null;
}
public Node(Object theElement)
{

Element = theElement;
Link = null;
}
}
public class InsertBeforeHeaderException : System.
ApplicationException
{
public InsertBeforeHeaderException(string message) :
base(message)
{
}
}
public class LinkedList

{
private Node header;
public LinkedList()

{
header = new Node("header");
}
public bool IsEmpty()

{
return (header.Link == null);
}
public Node GetFirst()

{
return header;
}
public void ShowList()

{
Node current = header.Link;
while (!(current == null))

{
Console.WriteLine(current.Element);
current = current.Link;
}
}
}
public class ListIter

{
private Node current;
private Node previous;
LinkedList theList;
public ListIter(LinkedList list)

{
theList = list;
current = theList.GetFirst();
previous = null;
}
public void NextLink()

{
previous = current;
current = current.Link;
}
public Node GetCurrent()

{
return current;
}
public void InsertBefore(Object theElement)

{

Node newNode = new Node(theElement);
if (previous.Link == null)
throw new InsertBeforeHeaderException
("Can't insert here.");
else {
newNode.Link = previous.Link;
previous.Link = newNode;
current = newNode;
}
}
public void InsertAfter(Object theElement)

{
Node newNode = new Node(theElement);
newNode.Link = current.Link;
current.Link = newNode;
NextLink();
}
public void Remove()

{
previous.Link = current.Link;
}
public void Reset()

{

current = theList.GetFirst();
previous = null;
}
public bool AtEnd() {
return (current.Link == null);
}
}
class chapter

{
static void Main()

{
LinkedList MyList = new LinkedList();
ListIter iter = new ListIter(MyList);
string choice, value;
try
{
iter.InsertAfter("David");
iter.InsertAfter("Mike");
iter.InsertAfter("Raymond");
iter.InsertAfter("Bernica");
iter.InsertAfter("Jennifer");
iter.InsertBefore("Donnie");
iter.InsertAfter("Michael");
iter.InsertBefore("Terrill");
iter.InsertBefore("Mayo");
iter.InsertBefore("Clayton");
while (true)
{
Console.WriteLine("(n) Move to next node");
Console.WriteLine("(g)Get value in current node");
Console.WriteLine("(r) Reset iterator");
Console.WriteLine("(s) Show complete list");
Console.WriteLine("(a) Insert after");
Console.WriteLine("(b) Insert before");
Console.WriteLine("(c) Clear the screen");
Console.WriteLine("(x) Exit");
Console.WriteLine();
Console.Write("Enter your choice: ");
choice = Console.ReadLine();
choice = choice.ToLower();
char[] onechar = choice.ToCharArray();
switch(onechar[0])
{
case 'n' :
if (!(MyList.IsEmpty()) &&
(!(iter.AtEnd())))
iter.NextLink();
else
Console.WriteLine("Can' move to
next link.");
break;
case 'g' :
if (!(MyList.IsEmpty()))
Console.WriteLine("Element: " +
iter.GetCurrent().Element);
else
Console.WriteLine ("List is empty.");
break;
case 'r' :
iter.Reset();
break;
case 's' :
if (!(MyList.IsEmpty()))
MyList.ShowList();
else
Console.WriteLine("List is empty.");
break;
case 'a' :
Console.WriteLine();
Console.Write("Enter value to insert:");
value = Console.ReadLine();
iter.InsertAfter(value);
break;
case 'b' :
Console.WriteLine();
Console.Write("Enter value to insert:");
value = Console.ReadLine();
iter.InsertBefore(value);
break;
case 'c' :
// clear the screen
break;
case 'x' :
// end of program
break;
}
}
}
catch (InsertBeforeHeaderException e)
{
Console.WriteLine(e.Message);
}
}
}

GENERIC LINKED LIST CLASS AND THE GENERIC NODE CLASS

The System.Collections.Generic namespace provides two generic classes for building linked lists: the LinkedList class and the LinkedListNode class. The Node class provides two data fields for storing a value and a link, whereas the LinkedList class implements a doubly linked list with methods for inserting before a node as well as inserting after a node. The class also provides method for removing nodes, finding the first and last nodes in the linked list, as well as other useful methods.

Generic Linked List Example

LinkedListNode node1 = new LinkedListNode_(“Raymond");
LinkedList names = new LinkedList();

From here, it’s just a matter of using the classes to build and use a linked list. A simple example demonstrates how easy it is to use these classes:

using System;
using System.Collections.Generic;
using System.Text;
class Program

{
static void Main(string[] args)

{
LinkedListNode node = new
LinkedListNode("Mike");
LinkedList names = new LinkedList();
names.AddFirst(node);
LinkedListNode node1 = new
LinkedListNode ("David");
names.AddAfter(node, node1);
LinkedListNode node2 = new
LinkedListNode ("Raymond");
names.AddAfter(node1, node2);
LinkedListNode node3 = new LinkedListNode (null);
LinkedListNode aNode = names.First;
while(aNode != null)

{
Console.WriteLine(aNode.Value);
aNode = aNode.Next;
}
aNode = names.Find("David");
if (aNode != null) aNode = names.First;
while (aNode != null)

{
Console.WriteLine(aNode.Value);
aNode = aNode.Next;
}
Console.Read()
}
}

The linked list in this example does not use a header node because
we can easily find the first node in the linked list with the First property.
Although it wasn’t used in this example, there is also a Last property
that could be used in the previous While loop to check for the end of the
list:
while (aNode != names.Last) {
Console.WriteLine(aNode.Value);
aNode = aNode.Next;
}
There are two other methods, not shown here, that could prove useful in a linked list implementation: AddFirst and AddLast. These methods can help you implement a linked list without having to provide header and tail nodes in your list.