This section will document any updates applied to the project since original release:

• revision 1: typo in inc/ListOfSinglyLinkedNodes.h fixed (20141211)

In this project, we expand upon our third rewrite of linked list code, doing to lists what we've been doing to nodes all along: linking them together.

This also serves as another part of the End of Course Experience, which wraps up our Data Structures journey this semester.

While we've been using our own custom “node” as the base unit of operations this semester, that is actually unimportant when compared to the concepts we've explored USING nodes.

And how have we used nodes? By linking them together. We explored singly-linking them (next pointer), and then doubly-linking them (adding in a prev). Then with trees, we technically had some situations where we were triply-linking.

The important premise here is the linking. Just as arrays are a bunch of SOMETHING, we can link ANYTHING of the same container togther. That doesn't mean JUST nodes.

What we're going to do is better realize that by extending our linking to lists. As such, instead of exploring a List of Singly/Doubly-Linked Nodes, we will have the following:

• Singly-Linked Lists of Singly-Linked Nodes
• Singly-Linked Lists of Doubly-Linked Nodes
• Doubly-Linked Lists of Singly-Linked Nodes
• Doubly-Linked Lists of Doubly-Linked Nodes

The same basic concept is at play.. we still have nodes, linked together, only now we're dealing with multiple lists as our unit of focus.

As such, this is largely an exercise in abstraction: this should prove to be little different from the basic List of Linked Nodes arrangements we've been playing with all semester.

This project will build upon our newly re-implemented OOP/C++ linked list project (eoce0)… and even then, it really just amounts to little more than function overloading.

This is the same, except for the additions needed to continue propagating the polymorphic magic:

1

#ifndef _LIST_H
#define _LIST_H
 
#include <Node.h>
 
class List {
    public:
        List();
 
        virtual List *copy()                  = 0;
                int   getQuantity();
 
        virtual void  append(Node *, Node *)  = 0;
        virtual void  append(List *, List *)  = 0;
        virtual void  insert(Node *, Node *)  = 0;
        virtual void  insert(List *, List *)  = 0;
        virtual Node *obtain(Node *)          = 0;
        virtual List *obtain(List *)          = 0;
 
        virtual void  display(int)            = 0;
        virtual void  sort(int)               = 0;
        virtual void  swap(Node *, Node *)    = 0;
        virtual Node *find(int)               = 0;
 
        virtual Node *getStart()              = 0;
        virtual Node *getEnd()                = 0;
 
        virtual List *getNext()               = 0;
        virtual void  setNext(List *)         = 0;
 
        virtual List *getPrev()               = 0;
        virtual void  setPrev(List *)         = 0;
 
        virtual      ~List();
 
    protected:
                void  setQuantity(int);
 
        virtual void  setStart(Node *)        = 0;
        virtual void  setEnd  (Node *)        = 0;
 
        virtual Node *setListPosition(int)    = 0;
        virtual int   getListPosition(Node *) = 0;
 
        virtual List *setListNumber(int)      = 0;
        virtual int   getListNumber(List *)   = 0;
 
    private:
                int   quantity;
};
#endif

Here the ListOfSinglyLinkedNodes class receives the same treatment as List.h: polymorphic overloaded functions so that we can do some magic taking place in some derived class. Nothing will need to change in the code you've already written (or will use, should you have opted not to do the extra credit ListOfSinglyLinkedNodes from eoce0).

1

#ifndef _SINGLY_LIST_H
#define _SINGLY_LIST_H
 
#include <List.h>
#include <SinglyLinkedNode.h>
 
class ListOfSinglyLinkedNodes : public List {
        public:
                ListOfSinglyLinkedNodes();
 
                virtual List *copy();
 
                virtual void  append(Node *, Node *);
                virtual void  append(List *, List *) { };
                virtual void  insert(Node *, Node *);
                virtual void  insert(List *, List *) { };
                virtual Node *obtain(Node *);
                virtual List *obtain(List *) { return (NULL); };
 
                virtual void  display(int);
                virtual void  sort(int);
                virtual void  swap(Node *, Node *);
                virtual Node *find(int);
 
                Node *getStart();
                Node *getEnd();
 
                virtual List *getNext() { return (NULL); };
                virtual void  setNext(List *);
 
                virtual List *getPrev() { return (NULL); };
                virtual void  setPrev(List *);
 
                virtual ~ListOfSinglyLinkedNodes();
 
        protected:
                void  setStart(Node *);
                void  setEnd  (Node *);
 
                virtual Node *setListPosition(int);
                virtual int   getListPosition(Node *);
 
                virtual List *setListNumber(int)    { return (NULL); };
                virtual int   getListNumber(List *) { return (-1); };
 
        private:
                Node *start;
                Node *end;
};
#endif

Now for the first of the new: Singly-Linked Lists of Singly-Linked Nodes. Notice how similar it is conceptually to the List of Singly-Linked Nodes… essentially something with a next pointer that we can insert/append/obtain with.

1

#ifndef _SINGLY_LINKED_LISTS_OF_SINGLY_LINKED_NODES_H
#define _SINGLY_LINKED_LISTS_OF_SINGLY_LINKED_NODES_H
 
#include <ListOfSinglyLinkedNodes.h>
 
class SinglyLinkedListsOfSinglyLinkedNodes : public ListOfSinglyLinkedNodes {
    public:
                      SinglyLinkedListsOfSinglyLinkedNodes();
 
        virtual List *copy();
 
        virtual void  append(List *, List *);
        virtual void  insert(List *, List *);
        virtual List *obtain(List *);
 
                List *getNext();
                void  setNext(List *);
 
        virtual      ~SinglyLinkedListsOfSinglyLinkedNodes();
 
    protected:
        virtual List *setListNumber(int);
        virtual int   getListNumber(List *);
 
    private:
                List *next;
};
#endif

Notice how similar this is to the SLLofSLN above… all we're doing is inheriting from the ListOfDoublyLinkedNodes class instead of the ListOfSinglyLinkedNodes class… with that said, there'll be a lot of repetition in our code (ie once you rig this up once, most if not all of it will be usable for the other).

1

#ifndef _SINGLY_LINKED_LISTS_OF_DOUBLY_LINKED_NODES_H
#define _SINGLY_LINKED_LISTS_OF_DOUBLY_LINKED_NODES_H
 
#include <ListOfDoublyLinkedNodes.h>
 
class SinglyLinkedListsOfDoublyLinkedNodes : public ListOfDoublyLinkedNodes {
    public:
                      SinglyLinkedListsOfDoublyLinkedNodes();
 
        virtual List *copy();
 
        virtual void  append(List *, List *);
        virtual void  insert(List *, List *);
        virtual List *obtain(List *);
 
                List *getNext();
                void  setNext(List *);
 
        virtual      ~SinglyLinkedListsOfDoublyLinkedNodes();
 
    protected:
        virtual List *setListNumber(int);
        virtual int   getListNumber(List *);
 
    private:
                List *next;
};
#endif

With DLLofSLN, we add a new tier of inheritance to our list organizational chart… DLLofSLN is a great-grandchild of the List class. And just as with the Doubly-Linked stuff we've been playing with, we now have a prev pointer to content with, to be used against lists!

1

#ifndef _DOUBLY_LINKED_LISTS_OF_SINGLY_LINKED_NODES_H
#define _DOUBLY_LINKED_LISTS_OF_SINGLY_LINKED_NODES_H
 
#include <SinglyLinkedListsOfSinglyLinkedNodes.h>
 
class DoublyLinkedListsOfSinglyLinkedNodes : public SinglyLinkedListsOfSinglyLinkedNodes {
    public:
                      DoublyLinkedListsOfSinglyLinkedNodes();
 
        virtual List *copy();
 
        virtual void  append(List *, List *);
        virtual void  insert(List *, List *);
        virtual List *obtain(List *);
 
                List *getPrev();
                void  setPrev(List *);
 
        virtual      ~DoublyLinkedListsOfSinglyLinkedNodes();
 
    protected:
        virtual List *setListNumber(int)    { return(NULL); };
        virtual int   getListNumber(List *) { return(-1);   };
 
    private:
                List *prev;
};
#endif

And we do the same treatment here with DLLofDLN – which will effectively share the same codebase with DLLofSLN. But I'm having you rig up four separate instances so that you can actually have real tangible examples to play with.

1

#ifndef _DOUBLY_LINKED_LISTS_OF_DOUBLY_LINKED_NODES_H
#define _DOUBLY_LINKED_LISTS_OF_DOUBLY_LINKED_NODES_H
 
#include <SinglyLinkedListsOfDoublyLinkedNodes.h>
 
class DoublyLinkedListsOfDoublyLinkedNodes : public SinglyLinkedListsOfDoublyLinkedNodes {
    public:
                      DoublyLinkedListsOfDoublyLinkedNodes();
 
        virtual List *copy();
 
        virtual void  append(List *, List *);
        virtual void  insert(List *, List *);
        virtual List *obtain(List *);
 
                List *getPrev();
                void  setPrev(List *);
 
        virtual      ~DoublyLinkedListsOfDoublyLinkedNodes();
 
    protected:
        virtual List *setListNumber(int)    { return(NULL); };
        virtual int   getListNumber(List *) { return(-1);   };
 
    private:
                List *prev;
};
#endif

For this project, it is your responsibility to:

• Implement all functions in the following classes:
  • SinglyLinkedListsOfSinglyLinkedNodes
  • SinglyLinkedListsOfDoublyLinkedNodes
  • DoublyLinkedListsOfSinglyLinkedNodes
  • DoublyLinkedListsOfDoublyLinkedNodes
• if you opted not to do the ListOfSinglyLinkedNodes from eoce0, a test reference implementation of that class will be made available in short order.

To be successful in this project, the following criteria must be met:

• Project must be submit on time, by the posted deadline.
  • As this project is due at the very end of the semester, there is no late window. It is either submitted, or it is not.
• All code must compile cleanly (no warnings or errors)
  • all requested functions must be implemented in the related library
  • all requested functionality must conform to stated requirements (either on this project page or in comment banner in source code files themselves).
  • functions that return must have a maximum of 1 return statement (I've noticed many people using 2-3 in their functions, and while it is syntactically not incorrect, like certain people's over-reliance of qty earlier in the semester, the use of multiple return statements encourages a less-than-optimal conceptual and aesthetic exploration of our re-implementation).
• Executed programs must display in a manner similar to provided output
  • output formatted, where applicable, must match that of project requirements
• Processing must be correct based on input given and output requested
• Output, if applicable, must be correct based on values input
• Code must be nicely and consistently indented (you may use the indent tool)
• Code must be commented
  • Any “to be implemented” comments MUST be removed
    • these “to be implemented” comments, if still present at evaluation time, will result in points being deducted.
  • Sufficient comments explaining the point of provided logic MUST be present
• Track/version the source code in a repository
• Submit a copy of your source code to me using the submit tool (make submit will do this) by the deadline.