Definition of Link List

A link list is a list where each item has a link to the next item. It is also known as singly linked list unless chained to the previous node/item.

In essence there is a recursive node, node within node. The search for items or nodes is done in a linear fashion. In C language, a structure is used to encapsulate the idea of such an item/ node. The structure then will contain pointer to its type again. This member pointer data represents the next link. The node essentially contains other data as well besides the self-pointer.

Objective

The objective of this activity is to provide a generic and useful link list template library in OOP paradigm using C++. Many a times people spent effort in trying to re-write code again and again for the same thing. Every sophisticated computer programs/ applications have directly or indirectly used or implemented Link List. This task helps to reduce overhead and implementation details.

Here, you will find a re-useable template class for link list. All you need to do is have the source files for this implementation and change/ modify the node class "CNode". At most, you may be required to implement another add function to allow easy addition to the list.

Next time in your project activity if you want to include link list features, download this small project code and modify the node class accordingly. This is all you need.

Note that the memory destruction method used here is "delete". It is possible to have your own memory allocation and de-allocation scheme.

Implementation Approach

To demonstrate C++ implementation using C++, we devise a generic simple class called "CNode". This serves very much like the structure item/ node of C's usual implementation. Item data consists here of two elements - one, the pointer to itself and the other, an integer element data to indicate physical important representation of such a node.

While the node is represented by a class "CNode" we make use of another class called "CLinkList" to encapsulate the idea of link list implementation. Operations such as Add(), Remove() etc will be made available via this class. Please remember that the node class is a mere data class. All node operations are done using the "CLinkList" class.

Below is given the interface definition file for study. You can study how the class is designed and what are the supported methods and attributes of the class.

· LwCore.h

· A brief pseudo code example is given below. The complete test project can also be downloaded. Example code

References and Downloads

You can find lot of links on data structures and algorithms. For starters, it is good to visit some links containing lessons or chapters on data structures and algorithms. Not only of link list you can learn, but also many other topics related to data structures.

Download code here