A Linked List That Utilizes Templates
Linked List Concept
Terminology
Node | The fundamental building block of a Linked List. A node contains the data |
actually being stored in the list, as well as 1 or more pointers to other nodes. | |
This is typically implemented as a nested class (see below). | |
Singly-linked | A Linked List would be singly-linked if each node only has a single pointer to |
another node, typically a “next” pointer. This only allows for uni-directional | |
traversal of the data—from beginning to end. | |
Doubly-linked | Each node contains 2 pointers: a “next” pointer and a “previous” pointer. This |
allows for bi-directional traversal of the data—either from front-to-back or back- | |
to-front. | |
Head | A pointer to the first node in the list, akin to index 0 of an array. |
Tail | A pointer to the last node in the list. May or may not be used, depending on the |
implementation of the list. |
Nested Classes
class MyClass | // To create nested classes… | ||||
{ | // Use the Scope Resolution Operator | ||||
public: | MyClass::NestedClasssomeVariable; | ||||
// Nested class | |||||
structNestedClass | // With a class template… | ||||
{ | TemplateClass |
||||
intx, y, z; | TemplateClass |
||||
intSomeFunction(); | |||||
}; | /* NOTE 1: You can make nested classes | ||||
private: | private if you wish, to prevent access to | ||||
// Data for "MyClass" | them outside of the encapsulating class. */ | ||||
NestedClassmyData[5]; | |||||
NestedClass*somePtr; | /* Why is NestedClass a struct in this | ||||
float values[10]; | case? No reason in particular. Remember a | ||||
// Etc… | structis just a class with public access | ||||
}; | by default. */ | ||||
/* NOTE 2: Nested classes and templates can | |||||
make for some ugly code. Be sure to read | |||||
the section at the end about typename */ | |||||
Benefits and Drawbacks
Linked List versus Array – Who Wins?
Array | Linked List |
Fast access of individual elements as well as | Changing the Linked List is fast – nodes can be |
iteration over the entire array | inserted/removed very quickly |
Random access – You can quickly “jump” to the | Less affected by memory fragmentation, nodes |
appropriate memory location of an element | can fit anywhere in memory |
Changing the array is slow – Have to rebuild the | No random access, slow iteration and access to |
entire array when adding/removing elements | individual elements |
Memory fragmentation can be an issue for | Extra memory overhead for nodes/pointers |
arrays—need a single, contiguous block large | |
enough for all of the data |
Code Structure
Function Reference
Behaviors | |
PrintForward | Iterator through all of the nodes and print out their values, one a time. |
PrintReverse | Exactly the same as PrintForward, except completely the opposite. |
PrintForwardRecursive | This function takes in a pointer to a Node—a starting node. From that node, |
recursively visit each node that follows, in forward order, and print their values. | |
This function MUST be implemented using recursion, or tests using it will be | |
worth no points. Check your textbook for a reference on recursion. | |
PrintReverseRecursive | Same deal as PrintForwardRecursive, but in reverse. |
Accessors | |
NodeCount | How many things are stored in this list? |
FindAll | Find all nodes which match the passed in parameter value, and store a pointer to |
that node in the passed in vector. Use of a parameter like this (passing a | |
something in by reference, and storing data for later use) is called an output | |
parameter. | |
Find | Find the first node with a data value matching the passed in parameter, |
returning a pointer to that node. Returns nullptr if no matching node found. | |
GetNode | Given an index, return a pointer to the node at that index. Throws an exception |
of type out_of_range if the index is out of range. Const and non-const versions. | |
Head | Returns the head pointer. Const and non-const versions. |
Tail | Returns the tail pointer. Const and non-const versions. |
Insertion Operations | |
AddHead | Create a new Node at the front of the list to store the passed in parameter. |
AddTail | Create a new Node at the end of the list to store the passed in parameter. |
AddNodesHead | Given an array of values, insert a node for each of those at the beginning of the |
list, maintaining the original order. | |
AddNodesTail | Ditto, except adding to the end of the list. |
InsertAfter | Given a pointer to a node, create a new node to store the passed in value, after |
the indicated node. | |
InsertBefore | Ditto, except insert the new node before the indicated node. |
InsertAt | Inserts a new Node to store the first parameter, at the index-th location. So if |
you specified 3 as the index, the new Node should have 3 Nodes before it. | |
Throws an out_of_range exception if given an invalid index. | |
Removal Operations | |
RemoveHead | Deletes the first Node in the list. Returns whether or not the Node was removed. |
RemoveTail | Deletes the last Node, returning whether or not the operation was successful. |
Remove | Remove ALL Nodes containing values matching that of the passed-in parameter. |
Returns how many instances were removed. | |
RemoveAt | Deletes the index-th Node from the list, returning whether or not the operation |
was successful. | |
Clear | Deletes all Nodes. Don’t forget the node count—how many nodes do you have |
after you deleted all of them? | |
Operators | |
operator[] | Overloaded subscript operator. Takes an index, and returns data from the index- |
the node. Throws an out_of_range exception for an invalid index. Const and non-const | |
const versions. | |
operator= | Homework operator. After listA = listB, listA == listB is true. Can you utilize any |
of your existing functions to make write this one? (Hint: Yes you can.) | |
operator== | Overloaded equality operator. Given listA and listB, is listA equal to listB? What |
would make one Linked List equal to another? If each of its nodes were equal to | |
the corresponding node of the other. (Similar to comparing two arrays, just with | |
non-contiguous data). | |
Construction / Destruction | |
LinkedList() | Default constructor. How many nodes in an empty list? (Answer: 0) What is head |
pointing to? What is tail pointing to? (Answer: nullptr) Initialize your variables! | |
Copy Constructor | Sets “this” to a copy of the passed in LinkedList. For example, if the other list has |
10 nodes, with values of 1-10? “this” should have a copy of that same data. | |
~LinkedList() | The usual. Clean up your mess. (Delete all the nodes created by the list.) |
Template Types and the "typename" Keyword
The compilation process for templates requires specialization—that is, your compiler essentially copies-and-pastes a version of your template, replacing all the instances of
In order to know how to specialize, it has to know everything about the template class. If that template has some other template, it needs to know everything… before it knows everything… and therein lies the problem.
The typename keyword is a way of telling your compiler “Hey, what immediately follows typename is a data type. Treat it as such when you compiler everything else.” For example:
template
classFoo
{
public:
structNested
{
T someThing;
};
Nested SomeFunction();
};
When defining the function “SomeFunction” you might write this:
template
Nested Foo
You could clean that up by specifying that a Nested object is part of the Foo class:
template
Foo::Nested Foo
Okay… how about this?
template
Foo
When the Foo class is being defined, it is referencing a type, Nested. This type is part of the Foo class, but the compiler doesn’t know it’s part of the class until it’s done defining the class… But, since Foo is in the process of being defined… how can something simultaneously be defined not-yet-defined? Answer: It can’t.
Solution: using the typename keyword, tell the compiler that Nested IS IN FACT A TYPE, and so the compiler doesn’t have to wait to fully define Foo before finding out what it is.
// typename: Yes, compiler, Foo
typenameFoo
Ugly? You bet! Part of the joy of working with templates? It sure is! Every programming language has quirks like this that you just have to learn over time.
Code Solution
#ifndef LINKEDLIST_H
# define LINKEDLIST_H
#include
#include
using namespace std;
template
class Node{
public:
T type;
Node
Node
void print();
};
template
classLinkedList{
public:
Node
Node
int length;
LinkedList();
~LinkedList();
voidappendright(T& item);
voidappendleft(T& item);
voidPrintForward();
voidPrintReverse();
voidPrintForwardRecursively(Node
voidPrintReverseRecursively(Node
unsignedintNodeCount();
voidFindAll(vector
Node
Node
Node
Node
voidAddHead(T& value);
voidAddTail(T& value);
voidAddNodesHead(T* value,int count);
voidInsertAfter(Node
voidInsertBefore(Node
voidInsertAt(T& value, int index);
voidAddNodesTail(T* value,int count);
voidRemoveHead();
voidRemoveTail();
void Remove(T& value);
voidRemoveAt(int index);
void Clear();
T operator[](constint index);
bool operator==(LinkedList
LinkedList
};
#endif