Link List (How to develop with C#)

AN OBJECT-ORIENTED LINKED LIST DESIGN

Our design of a linked list will involve at least two classes.We’ll create a Node class and instantiate a Node object each time we add a node to the list. The nodes in the list are connected via references to other nodes. These references are set using methods created in a separate LinkedList class.Let’s start by looking at the design of the Node class.
The Node Class

A node is made up of two data members: Element, which stores the node’s data; and Link, which stores a reference to the next node in the list.We’ll use Object for the data type of Element, just so we don’t have to worry about what kind of data we store in the list. The data type for Link is Node, which seems strange but actually makes perfect sense. Since we want the link to point to the next node, and we use a reference to make the link, we have to assign a Node type to the link member.
To finish up the definition of the Node class, we need at least two constructor methods. We definitely want a default constructor that creates an empty Node, with both the Element and Link members set to null. We also need a parametrized constructor that assigns data to the Element member and sets the Link member to null.
Here’s the code for the Node class:

public class Node
{

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

The LinkedList Class
The LinkedList class is used to create the linkage for the nodes of our linked list. The class includes several methods for adding nodes to the list, removing nodes from the list, traversing the list, and finding a node in the list. We also need a constructor method that instantiates a list. The only data member in the class is the header node.

public class LinkedList
{
protected Node header;
public LinkedList()
{
header = new Node("header");
}
. . .
}

The header node starts out with its Link field set to null. When we add the first node to the list, the header node’s Link field is assigned a reference to the new node, and the new node’s Link field is assigned the null value.

To insert a new node after an existing node

To do this, we create a Private method, Find, that searches through the Element field of each node until a match is found.

private Node Find(Object item)

{
Node current = new Node();
current = header;
while(current.header != item)
current = current.Link;
return current;
}

Once we’ve found the “after” node, the next step is to set the new node’s Link field to the Link field of the “after” node, and then set the “after” node’s Link field to a reference to the new node. Here’s how it’s done:

public void Insert(Object newItem, Object after)

{
Node current = new Node();
Node newNode = new Node(newItem);
current = Find(after);

newNode.Link = current.Link;
current.Link = newNode;
}

Remove a node from a linked list

we simply have to change the link of the node that points to the removed node to point to the node after the removed node.

private Node FindPrevious(Object n)

{
Node current = header;
while(!(current.Link == null) && (current.Link.
Element != n))
current = current.Link;
return current;
}

Now we’re ready to see how the code for the Remove method looks:

public void Remove(Object n)

{
Node p = FindPrevious(n);
if (!(p.Link == null))
p.Link = p.Link.Link;
}

PrintList

public void PrintList()

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

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