/*
Plagiarism Policy:
Associate Professor Steven Halim provides this implementation of basic Singly Linked List (SLL)
for his classes in National University of Singapore (NUS) School of Computing (SoC).
This code is supposed to be studied by his students to understand the technical details
of Singly Linked List (SLL) implementation.
His style is to test his students on "application" of this data structure,
not about re-inventing Singly Linked List (SLL) again and again,
thus his assignments and tests rarely ask students to reuse this code verbatim.
(anyway, you can always use std::forward_list or std::list (Doubly Linked List) to do the same).
If you arrive at this source code from another module that is still testing you on how
to (re)-implement Singly (or Doubly) Linked List (and grade you for that), note that you can still
use this code below, but at your own risk, as you may be accidentally flagged as
commiting plagiarism if your other classmates do the same.
*/
#include
using namespace std;
// https://visualgo.net/en/list?slide=3-1
template
class Vertex { // using C++ class so that we can use class template
public: // the two below must be explicitly set as public
T item; // the data is stored here, an integer in this example
Vertex* next; // this pointer tells us where is the next vertex
};
// this is the version as shown in https://visualgo.net/en/list, SLL with both head and tail pointers
template
class SLL {
private:
Vertex* head;
Vertex* tail; // we can maintain tail pointer so that push_back is O(1)
public:
SLL() {
head = NULL;
}
// https://visualgo.net/en/list?slide=3-8
void push_front(T v) {
Vertex* vtx = new Vertex(); // create new vertex vtx from item v
vtx->item = v;
vtx->next = head; // link this new vertex to the (old) head vertex
if (head == NULL) tail = vtx; // if previously it was an empty SLL, then tail = head too
head = vtx; // the new vertex becomes the new head
}
// https://visualgo.net/en/list?slide=3-12
void push_back(T v) {
if (head == NULL) // an important corner case
push_front(v);
else {
Vertex* vtx = new Vertex(); // create new vertex vtx from item v, O(1)
vtx->item = v; // O(1)
// The O(N) version (if we do not use tail pointer)
// Vertex* tail = head; // we have to start from head
// while (tail->next != NULL) // while we have not reached the last element, O(N) - the slow part
// tail = tail->next; // the pointers are pointing to the higher index
// now we can use the tail pointer, after searching for it in O(N)
// The O(1) version (just by simply maintaining tail pointer at all times)
tail->next = vtx; // just link this, as tail is the i = (N-1)-th item, O(1)
tail = vtx; // now update the tail pointer, O(1)
}
}
T front() {
if (head == NULL) return -1; // avoid crashing when the SLL is empty (assumption: the SLL contains only non-negative integers, so -1 is a 'safe' symbol to indicate 'does not exist')
return head->item;
}
T back() {
if (tail == NULL) return -1; // avoid crashing when the SLL is empty (assumption: the SLL contains only non-negative integers, so -1 is a 'safe' symbol to indicate 'does not exist')
return tail->item;
}
// https://visualgo.net/en/list?slide=3-15
void pop_front() {
if (head == NULL) return; // avoid crashing when the SLL is empty
Vertex* temp = head; // so we can delete it later
head = head->next; // book keeping, update the head pointer
if (head == NULL) tail = NULL; // if the SLL is now becomes empty, then tail = NULL too
delete temp; // which is the old head
}
bool empty() {
return head == NULL;
}
};
// live demo to extend (wrap) SLL to a new class MyStack that can only access subset of SLL features
// another live demo to extend (wrap) SLL to a new class MyQueue that can only access another subset of SLL features
int main() {
// experiment with this baseline code to familiarise yourself with the very basic idea of Linked List data structure
cout << "Our own Singly Linked List (SLL)\n";
SLL l;
l.push_front(5);
l.push_front(2);
l.push_back(6);
l.push_front(7);
cout << l.front() << '\n'; // output 7 as the SLL is 7 (head)->2->5->6 now
l.pop_front();
cout << l.front() << '\n'; // output 2 as the SLL is 2 (head)->5->6 now
l.pop_front();
cout << l.front() << '\n'; // output 5 as the SLL is 5 (head)->6 now
l.pop_front();
cout << l.front() << '\n'; // output 6 as the SLL is 6 (head) now
l.pop_front(); // empty after this
cout << l.front() << '\n'; // -1 (empty SLL), already safe-guarded, won't crash
cout << '\n';
cout << "C++ STL version (std::list (DLL), as the equivalent std::forward_list (SLL) does not have efficient push_back)\n";
list ll;
ll.push_front(5);
ll.push_front(2);
ll.push_back(6); // not available in std::forward_list
ll.push_front(7);
cout << *ll.begin() << '\n'; // output 7 as the SLL is 7 (head)->2->5->6 now
ll.pop_front();
cout << *ll.begin() << '\n'; // output 2 as the SLL is 2 (head)->5->6 now
ll.pop_front();
cout << *ll.begin() << '\n'; // output 5 as the SLL is 5 (head)->6 now
ll.pop_front();
cout << *ll.begin() << '\n'; // output 6 as the SLL is 6 (head) now
ll.pop_front(); // empty after this
cout << (ll.empty() ? -1 : *ll.begin()) << '\n'; // -1 (empty SLL), need to do check first
cout << '\n';
cout << "Equivalency testing on a very large test case\n";
// large random test
clock_t begin = clock();
srand(time(NULL));
SLL ours;
list theirs;
assert(ours.empty() and theirs.empty()); // both empty at the start
int N = 1000000; // usually just a few seconds
for (int i = 0; i < N; ++i) { // insert N random integers to both data structures
int value = rand();
if (rand()%2 == 0)
ours.push_front(value), theirs.push_front(value); // yes you can use comma like this... or just split this into two lines
else
ours.push_back(value), theirs.push_back(value);
}
assert(!ours.empty() and !theirs.empty()); // both not empty (has N entries) by now
while (!ours.empty()) {
assert(ours.front() == theirs.front()); // front-most value (index 0) should match
assert(ours.back() == theirs.back()); // last value (index N-1) should match
ours.pop_front(), theirs.pop_front();
}
assert(ours.empty() and theirs.empty()); // both empty at the end
cout << "Test time = " << fixed << setprecision(2) << (double)(clock()-begin)/CLOCKS_PER_SEC << "s\n";
cout << "If there is no assertion (Run Time Error), then all is good\n";
return 0;
}