Doubly Link List Implementation in C#

We first need to modify the Node class to add an extra link to the class. To distinguish between the two links, we’ll call the link to the next node the FLink, and the link to the previous node the BLink. These fields are set to Nothing when a Node is instantiated. Here’s the code:
public class Node
{
public Object Element;
public Node Flink;
public Node Blink;
public Node()
{
Element = null;
Flink = null;
Blink = null;
}
public Node(Object theElement)
{
Element = theElement;
Flink = null;
Blink = null;
}
}

Insertion method


public void Insert(Object newItem, Object after)
{
Node current = new Node();
Node newNode = new Node(newItem);
current = Find(after);
newNode.Flink = current.Link;
newNode.Blink = current;
current.Flink = newNode;
}
Remove method
We first need to find the node in the list; then we set the node’s back link property to point to the node pointed to in the deleted node’s forward link. Then we need to redirect the back link of the link the deleted node points to and point it to the node before the deleted node.

public void Remove(Object n)

{
Node p = Find(n);
if (!(p.Flink == null))

{
p.Blink.Flink = p.Flink;
p.Flink.Blink = p.Blink;
p.Flink = null;
p.Blink = null;
}
}


Printing the elements of a linked list in reverse order

First, we need a method that finds the last node in the list. This is just a matter of following each node’s forward link until we reach a link that points to null. This method, called FindLast, is defined as follows:
private Node FindLast()

{
Node current = new Node();
current = header;
while(!(current.Flink == null))
current = current.Flink;
return current;
}

Once we find the last node in the list, to print the list in reverse order we just follow the backward link until we get to a link that points to null, which indicates we’re at the header node. Here’s the code:
public void PrintReverse()

{
Node current = new Node();
current = FindLast();
while (!(current.Blink == null))

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

0 Responses to "Doubly Link List Implementation in C#"