Using the linkedlist class


Introduction

The linkedlist class allows you to store an arbitrary number of values in a doubly-linked list. Since the linkedlist class is template-based, you can store arbitrary types of values.

Each linkedlist is composed of a series of linkedlistnodes. Each linkedlistnode contains a value.


Manipulating Values

The linkedlist 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.

#include <rudiments/linkedlist.h>
#include <rudiments/stdio.h>

int main(int argc, const char **argv) {

        linkedlist<uint32_t>    ll;

        // apppend values to the list
        ll.append(5);
        ll.append(6);
        ll.append(7);

        // prepend values to the list
        ll.prepend(2);
        ll.prepend(1);
        ll.prepend(-1);
        ll.prepend(-2);
        ll.prepend(-2);
        ll.prepend(-2);

        // insert values before and after other values
        ll.insertAfter(ll.find(2),4);
        ll.insertBefore(ll.find(4),3);

        // remove values from the list
        ll.remove(-1);

        // remove all of a particular value from the list
        ll.removeAll(-2);

        // length
        stdoutput.printf("The list contains %lld nodes.\n\n",ll.getLength());

        // print the list
        stdoutput.write("Current contents:\n");
        ll.print();
        stdoutput.write('\n');

        // print the first 3 values in the list
        stdoutput.write("First 3 values:\n");
        ll.print(3);
        stdoutput.write('\n');

        // clear the list
        ll.clear();
        stdoutput.printf("The list contains %lld nodes after clearing it.\n",
                                                                ll.getLength());
}

Manipulating Nodes

The linkedlist class also provides methods for manipulating list nodes directly.

#include <rudiments/linkedlist.h>
#include <rudiments/stdio.h>

int main(int argc, const char **argv) {

        linkedlist<uint32_t>    ll;

        // apppend nodes to the list
        ll.append(new linkedlistnode<uint32_t>(5));
        ll.append(new linkedlistnode<uint32_t>(6));
        ll.append(new linkedlistnode<uint32_t>(7));

        // prepend nodes to the list
        ll.prepend(new linkedlistnode<uint32_t>(2));
        ll.prepend(new linkedlistnode<uint32_t>(1));
        ll.prepend(new linkedlistnode<uint32_t>(0));

        // insert nodes before and after other nodes
        ll.insertAfter(ll.find(2),new linkedlistnode<uint32_t>(4));
        ll.insertBefore(ll.find(4),new linkedlistnode<uint32_t>(3));

        // move nodes around
        ll.append(new linkedlistnode<uint32_t>(-1));
        ll.append(new linkedlistnode<uint32_t>(-2));
        ll.append(new linkedlistnode<uint32_t>(-3));
        ll.moveBefore(ll.find(0),ll.find(-3));
        ll.moveBefore(ll.find(0),ll.find(-2));
        ll.moveAfter(ll.find(-2),ll.find(-1));

        // length
        stdoutput.printf("The list contains %lld nodes.\n\n",ll.getLength());

        // print the list
        stdoutput.write("Current contents:\n");
        ll.print();
        stdoutput.write('\n');

        // print the first 3 values in the list
        stdoutput.write("First 3 values:\n");
        ll.print(3);
        stdoutput.write('\n');
}

Sorting

The linkedlist 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/linkedlist.h>
#include <rudiments/randomnumber.h>
#include <rudiments/stdio.h>

int main(int argc, const char **argv) {

        linkedlist<uint32_t>    llis;
        linkedlist<uint32_t>    llhs;

        // 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.generateNumber(&num);

                llis.append(num);
                llhs.append(num);
        }

        // sort one list using insertion sort
        stdoutput.printf("sorting using insertion sort...\n");
        llis.insertionSort();

        // sort one list using heap sort
        stdoutput.printf("sorting using heap sort...\n");
        llhs.heapSort();

        // print the lists
        stdoutput.printf("insertion sorted list\n");
        llis.print(5);
        stdoutput.write("...\n\n");

        // print the list
        stdoutput.printf("heap sorted list\n");
        llhs.print(5);
        stdoutput.write("...\n\n");
}

Iterating Manually

The linkedlist class also provides methods for manually iterating through the list.

#include <rudiments/linkedlist.h>
#include <rudiments/stdio.h>

int main(int argc, const char **argv) {

        linkedlist<uint32_t>    ll;

        // apppend values to the list
        for (uint32_t i=0; i<20; i++) {
                ll.append(i);
        }

        // print the list forwards, all on one line
        stdoutput.write("forwards:\n");
        for (linkedlistnode<uint32_t> *n=ll.getFirst(); n; n=n->getNext()) {
                stdoutput.printf("%d ",n->getValue());
        }
        stdoutput.write("\n\n");

        // print the list backwards, all on one line
        stdoutput.write("backwards:\n");
        for (linkedlistnode<uint32_t> *n=ll.getLast(); n; n=n->getPrevious()) {
                stdoutput.printf("%d ",n->getValue());
        }
        stdoutput.write("\n\n");
}

Data Types

Since the linkedlist 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 linkedlist 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 when the list is cleared. They must be deleted manually.

#include <rudiments/linkedlist.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
        linkedlist<int16_t>     i16ll;
        linkedlist<int64_t>     i64ll;
        linkedlist< char * >    sll;
        linkedlist< myclass * > oll;

        // populate the lists
        for (int64_t i=0; i<20; i++) {
                i16ll.append(i);
                i64ll.append(i);
                sll.append(charstring::parseNumber(i));
                oll.append(new myclass(i));
        }

        // print the lists of primitive types
        stdoutput.printf("list of 16-bit integers:\n");
        i16ll.print();
        stdoutput.write('\n');

        stdoutput.printf("list of 64-bit integers:\n");
        i16ll.print();
        stdoutput.write('\n');

        stdoutput.printf("list of strings:\n");
        i16ll.print();
        stdoutput.write('\n');

        // manually print the list of objects
        stdoutput.printf("list of objects:\n");
        for (linkedlistnode< myclass * > *n=oll.getFirst(); n; n=n->getNext()) {
                n->getValue()->print();
        }
        stdoutput.write('\n');

        // clean up
        for (linkedlistnode< char * > *n=sll.getFirst(); n; n=n->getNext()) {
                delete[] n->getValue();
        }
        for (linkedlistnode< myclass * > *n=oll.getFirst(); n; n=n->getNext()) {
                delete n->getValue();
        }
}