April 23, 2016
Code Baselined: April 12, 2016
Synopsis
This paper presents code for a singly linked list implemented in C# without using the System.Collections namespace.
Introduction
I’ve recently embarked on the path to true enlightenment. No, I’m not referring to Transcendental Meditation, Zen Buddhism, or some other form of spiritual awakening—though some may consider it that. No, my journey is taking me into the realm of coding…C# coding to be exact. I believe you can read all the books you want on a programming language, but real learning only takes place when you start writing actual programs.
Not surprisingly, since I’m learning C# I’m also learning to use the Microsoft Visual Studio IDE (Integrated Development Environment).
I chose linked lists to implement as my first project in C# because it was the first data structure I learned in college and I’m somewhat familiar with the concept. Besides, I try to make it a practice when learning a new language to implement either a straightforward linked list or binary tree—just to see if I can still do it.
Design
For this exercise, I wrote all the code to manage the linked list without using the System.Collections namespace. I chose a singly linked list data structure to implement a stack. In a stack, the last data item pushed or added to the stack is the first data item popped or removed (LIFO) from the stack.
The length of the list, i.e., depth of the stack, is finite. The list length is determined by a parameter passed by the calling program.
Nodes are the mechanism by which data are stored in the list. Each node is comprised of two data fields: INFO and LINK as shown in Figure 1. The INFO field holds user data and the LINK field holds a pointer to the next node in the list.
I’ve decided to implement two header nodes; one header node points to the top of the stack and the other header node points to the top of the available nodes list. Each node consists of two data fields, INFO and LINK (see Figure 1). As a result, if the LINK field of the stack header node is null then the stack is empty. Likewise, if the LINK field of the available nodes list is null, then the stack is full.
The stack header node and the list of available nodes are initialized in the linked list class constructor as illustrated in Figure 2 below.
Methods implemented in the linked list class include:
AddNode—implements a stack Push operation by adding a node from the Avail list to the front (top) of the list. The Head node always points to the top of the stack. Figure 3 illustrates the contents of the stack and the Avail list after the value “Board” is added (pushed) on the stack.
DeleteNode—implements a stack Pop operation by removing the data item at the front (top) of the list. The deleted node is returned to the Avail list.
ShowNodes—displays the contents of the stack or Avail list depending on the value of the calling parameter.
The layout of the nodes in Figure 3 above should not be taken literally. That is, the nodes in memory aren’t actually being moved around, only the pointers in the affected nodes’ LINK field are being updated. See Knuth Vol. 1 for more information on linked list processing.
Code
using System;
namespace LinkedList
{
public class Node
{
public Node next;
public string data;
}
public class LinkedList
{
public Node head;
public Node avail;
public LinkedList(int nodecount)
{
head = new Node();
head.data = "Head";
head.next = null;
avail = new Node();
avail.data = "Avail";
avail.next = null;
Node saveNode = null;
int count = nodecount;
for (int i = 0; i < count; i++)
{
Node newNode = new Node();
newNode.next = null;
newNode.data = i.ToString();
if (i == 0)
{
avail.next = newNode;
saveNode = avail.next;
}
else
{
saveNode.next = newNode;
saveNode = newNode;
}
}
}
public void AddNode(string content)
{
if (avail.next != null)
{
Node p = avail.next;
avail.next = p.next;
p.data = content;
if (head.next != null)
p.next = head.next;
else
p.next = null;
head.next = p;
}
else
Console.WriteLine("No Avail Nodes! Can't add: " + content);
}
public void DeleteNode()
{
if (head.next != null)
{
Node p = head.next;
head.next = p.next;
p.next = avail.next;
avail.next = p;
Console.WriteLine("Node: '" + p.data + "' Removed!");
}
else
Console.WriteLine("Head List is Empty! Nothing to Delete.");
}
public void ShowNodes(string showlist)
{
Node llist = null;
switch(showlist)
{
case "Head":
llist = head;
break;
case "Avail":
llist = avail;
break;
default:
Console.WriteLine(showlist + ": Invalid/Missing Request!");
return;
}
if (llist.next == null)
Console.WriteLine(llist.data + " List is Empty! Nothing to Show.");
else
{
Console.WriteLine("<" + llist.data + " List>");
Node inList = llist.next;
while (inList != null)
{
Console.WriteLine(inList.data);
inList = inList.next;
}
Console.WriteLine("</" + llist.data + " List>");
}
}
}
class Program
{
static void Main(string[] args)
{
LinkedList LIFOstack = new LinkedList(5);
LIFOstack.ShowNodes("Head");
LIFOstack.ShowNodes("Avail");
LIFOstack.DeleteNode();
LIFOstack.AddNode("Board");
LIFOstack.AddNode("Drawing");
LIFOstack.AddNode("The");
LIFOstack.AddNode("To");
LIFOstack.AddNode("Back");
LIFOstack.ShowNodes("Head");
LIFOstack.AddNode("Get");
LIFOstack.ShowNodes("Avail");
LIFOstack.DeleteNode();
LIFOstack.ShowNodes("Head");
LIFOstack.ShowNodes("Avail");
}
}
}
Runtime Output
Head List is Empty! Nothing to Show. <Avail List> 0 1 2 3 4 </Avail List> Head List is Empty! Nothing to Delete. <Head List> Back To The Drawing Board </Head List> No Avail Nodes! Can't add: Get Avail List is Empty! Nothing to Show. Node: 'Back' Removed! <Head List> To The Drawing Board </Head List> <Avail List> Back </Avail List>
Copyright secured by Digiprove © 2020 Gerard Sczepura