Linked List Implementation in “Collectionless” C#

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.

Nodes_Figure1
Fig. 1. Node data fields.

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.

Nodes_Figure2
Fig. 2. List initialization.

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.

Nodes_Figure3
Fig. 3. List after first insert.

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

Runtime Output

Click here for reuse options!
Copyright 2016 Gerard Sczepura