Using the singlylinkedlist class
Introduction
The singlylinkedlist class allows you to store an arbitrary number of values in a singly-linked list. Since the singlylinkedlist class is template-based, you can store arbitrary types of values.
Each singlylinkedlist is composed of a series of singlylinkedlistnodes. Each singlylinkedlistnode contains a value.
This class is similar to the linkedlist class but uses less memory and many of its operations are faster.
However, the move, detach and remove operations are much slower. If your application must run these operations regularly, you should consider using the linkedlist class instead.
Manipulating Values
The singlylinkedlist class provides methods for prepending, appending, inserting and removing values from a linked list, for finding values in the list, for getting the size of the list, clearing the list, and printing the list.
Note that unlike the linkedlist class, there is no method for inserting a value before another value, only a method for inserting a value after another value.
#include <rudiments/singlylinkedlist.h>
#include <rudiments/stdio.h>
int main(int argc, const char **argv) {
singlylinkedlist<uint32_t> sll;
// apppend values to the list
sll.append(5);
sll.append(6);
sll.append(7);
// prepend values to the list
sll.prepend(2);
sll.prepend(1);
sll.prepend(-1);
sll.prepend(-2);
sll.prepend(-2);
sll.prepend(-2);
// insert values before and after other values
sll.insertAfter(sll.find(2),3);
sll.insertAfter(sll.find(3),4);
// remove values from the list
sll.remove(-1);
// remove all of a particular value from the list
sll.removeAll(-2);
// count
stdoutput.printf("The list contains %lld nodes.\n\n",sll.getCount());
// print the list
stdoutput.write("Current contents:\n");
sll.write();
stdoutput.write('\n');
// clear the list
sll.clear();
stdoutput.printf("The list contains %lld nodes after clearing it.\n",
sll.getCount());
}
Manipulating Nodes
The singlylinkedlist class also provides methods for manipulating list nodes directly.
Note that unlike the linkedlist class, there are no methods for inserting or moving a node before another node, only methods for inserting and moving a node after another node.
#include <rudiments/singlylinkedlist.h>
#include <rudiments/stdio.h>
int main(int argc, const char **argv) {
singlylinkedlist<uint32_t> sll;
// apppend nodes to the list
sll.append(new singlylinkedlistnode<uint32_t>(5));
sll.append(new singlylinkedlistnode<uint32_t>(6));
sll.append(new singlylinkedlistnode<uint32_t>(7));
// prepend nodes to the list
sll.prepend(new singlylinkedlistnode<uint32_t>(2));
sll.prepend(new singlylinkedlistnode<uint32_t>(1));
sll.prepend(new singlylinkedlistnode<uint32_t>(0));
// insert nodes
sll.insertAfter(sll.find(2),new singlylinkedlistnode<uint32_t>(3));
sll.insertAfter(sll.find(3),new singlylinkedlistnode<uint32_t>(4));
// move nodes around
sll.prepend(new singlylinkedlistnode<uint32_t>(8));
sll.prepend(new singlylinkedlistnode<uint32_t>(9));
sll.prepend(new singlylinkedlistnode<uint32_t>(10));
sll.moveAfter(sll.find(7),sll.find(8));
sll.moveAfter(sll.find(8),sll.find(9));
sll.moveAfter(sll.find(9),sll.find(10));
// count
stdoutput.printf("The list contains %lld nodes.\n\n",sll.getCount());
// print the list
stdoutput.write("Current contents:\n");
sll.write();
stdoutput.write('\n');
}
Sorting
The singlylinkedlist class also provides methods for sorting the list.
Methods for both insertion and heap sort are provided. Insertion sort is slow, for large lists, but doesn't require any additional memory. Heap sort is fast, even for large lists, but requires additional memory.
#include <rudiments/singlylinkedlist.h>
#include <rudiments/randomnumber.h>
#include <rudiments/stdio.h>
int main(int argc, const char **argv) {
singlylinkedlist<uint32_t> sllis;
singlylinkedlist<uint32_t> sllhs;
// generate random numbers and append them to the lists
randomnumber rr;
rr.setSeed(randomnumber::getSeed());
stdoutput.printf("generating numbers...\n");
for (uint16_t i=0; i<20000; i++) {
uint32_t num;
rr.generate(&num);
sllis.append(num);
sllhs.append(num);
}
// sort one list inexpensively
stdoutput.printf("sorting inexpensively...\n");
sllis.sortInexpensively();
// sort one list quickly
stdoutput.printf("sorting quickly...\n");
sllhs.sortQuickly();
// print the lists
stdoutput.printf("inexpensively sorted list\n");
sllis.write();
stdoutput.write("...\n\n");
stdoutput.printf("quickly sorted list\n");
sllhs.write();
stdoutput.write("...\n\n");
}
Iterating Manually
The singlylinkedlist class also provides methods for manually iterating through the list.
Note, that unlike the linkedlistnode class, the singlylinkedlistnode class does not have a getPrevious() method. Thus, it is impossible to iterate backwards through a singlylinkedlist.
#include <rudiments/singlylinkedlist.h>
#include <rudiments/stdio.h>
int main(int argc, const char **argv) {
singlylinkedlist<uint32_t> sll;
// apppend values to the list
for (uint32_t i=0; i<20; i++) {
sll.append(i);
}
// print the list forwards, all on one line
for (listnode<uint32_t> *n=sll.getFirst(); n; n=n->getNext()) {
stdoutput.printf("%d ",n->getValue());
}
stdoutput.write("\n\n");
}
Data Types
Since the singlylinkedlist class is template-based, it can store any type of data.
Note that the print() method works for primitive types and strings, but for more complex types, it only prints the address of the object.
Note also that the singlylinkedlist class does not manage the data stored in it. If you store a list of dynamically allocated strings or objects, they will not be deleted automatically when a node is removed or the list is cleared. They must be deleted manually.
#include <rudiments/singlylinkedlist.h>
#include <rudiments/stdio.h>
// Define a simple class. Instances of it will be stored in a list later.
class myclass {
public:
myclass(int64_t v) { value=v; }
void print() { stdoutput.printf("value: %lld\n",value); }
private:
int64_t value;
};
int main(int argc, const char **argv) {
// lists of various types
singlylinkedlist<int16_t> i16sll;
singlylinkedlist<int64_t> i64sll;
singlylinkedlist< char * > ssll;
singlylinkedlist< myclass * > osll;
// populate the lists
for (int64_t i=0; i<20; i++) {
i16sll.append(i);
i64sll.append(i);
ssll.append(charstring::parseNumber(i));
osll.append(new myclass(i));
}
// print the lists of primitive types
stdoutput.printf("list of 16-bit integers:\n");
i16sll.write();
stdoutput.write('\n');
stdoutput.printf("list of 64-bit integers:\n");
i16sll.write();
stdoutput.write('\n');
stdoutput.printf("list of strings:\n");
i16sll.write();
stdoutput.write('\n');
// manually print the list of objects
stdoutput.printf("list of objects:\n");
for (listnode< myclass * > *n=osll.getFirst(); n; n=n->getNext()) {
n->getValue()->print();
}
stdoutput.write('\n');
// clean up
for (listnode< char * > *n=ssll.getFirst(); n; n=n->getNext()) {
delete[] n->getValue();
}
for (listnode< myclass * > *n=osll.getFirst(); n; n=n->getNext()) {
delete n->getValue();
}
}
