Skip to content

Instantly share code, notes, and snippets.

@danopia

danopia/LinkedList.cpp

Forked from anonymous/LinkedList.h
Last active April 13, 2023 23:58
Show Gist options
  • Save danopia/5506135 to your computer and use it in GitHub Desktop.
Save danopia/5506135 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
LinkedList.cpp
#include "LinkedList.h"
template <class T>
LinkedList<T>::LinkedList()
{
first = NULL;
last = NULL;
}
template <class T>
LinkedList<T>::~LinkedList()
{
Node<T>* temp = first;
while(temp != NULL)
{
temp = temp->next;
delete(first);
first = temp;
}
}
template <class T>
void LinkedList<T>::insertAtBack(T valueToInsert)
{
Node<T>* newNode;
newNode->val = valueToInsert;
newNode->next = NULL;
Node<T>* temp = first;
if (temp != NULL)
{
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
}
else
{
first = newNode;
}
}
template <class T>
bool LinkedList<T>::removeFromBack()
{
if (first == NULL && last == NULL) {return false;}
if (first == last)
{
cout<<"First is equal to Last."<<endl;
delete(first);
first = last = NULL;
return true;
}
else
{
Node<T>* temp = first;
int nodeCount = 0;
while (temp != NULL)
{
nodeCount = nodeCount + 1;
temp = temp->next;
}
Node<T>* temp2 = first;
for(int i = 1; i < (nodeCount - 1); i++)
{
temp2 = temp2->next;
}
cout << temp2->val<<endl;
delete(temp2->next);
last = temp2;
last->next = NULL;
return true;
}
}
template <class T>
void LinkedList<T>::print()
{
Node<T>* temp = first;
if (temp == NULL)
{
cout<<"";
}
if (temp->next == NULL)
{
cout<<temp->val;
}
else
{
while (temp != NULL)
{
cout<< temp->val;
temp = temp->next;
cout<< ",";
}
}
}
template <class T>
bool LinkedList<T>::isEmpty()
{
if (first == NULL && last == NULL) {return true;}
else {return false;}
}
template <class T>
int LinkedList<T>::size()
{
if (first == NULL && last == NULL) {return 0;}
Node<T>* temp = first;
int nodeCounter = 0;
while (temp != NULL)
{
nodeCounter = nodeCounter + 1;
temp = temp->next;
}
return nodeCounter;
}
template <class T>
void LinkedList<T>::clear()
{
Node<T>* temp = first;
while(temp != NULL)
{
temp = temp->next;
first = temp;
delete(temp);
}
}
template <class T>
void LinkedList<T>::insertAtFront(T valueToInsert)
{
Node<T>* newNode;
newNode->val = valueToInsert;
if(first == NULL)
{
first = newNode;
}
else
{
newNode->next = first;
first = newNode;
}
}
template <class T>
bool LinkedList<T>::removeFromFront()
{
if (first == NULL && last == NULL) {return false;}
else
{
Node<T>* temp;
temp = first;
first = first->next;
delete(temp);
return true;
}
}
template <class T>
T& LinkedList<T>::firstNum()
{
return first->val;
}
Raw
LinkedList.h
using namespace std;
#include <iostream>
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
template <class T>
struct Node
{
T val;
Node<T> *next;
};
template <class T>
class LinkedList
{
public:
LinkedList();
~LinkedList();
void insertAtBack(T valueToInsert);
bool removeFromBack();
void print();
bool isEmpty();
int size();
void clear();
void insertAtFront(T valueToInsert);
bool removeFromFront();
T& firstNum();
private:
Node<T> *first;
Node<T> *last;
};
#endif
Raw
main.cpp
using namespace std;
#include <iostream>
#include "Queue.h"
#include "LinkedList.h"
int main()
{
try
{
int type = 0;
cout<<"What data type do you want to work with? 1 = int, 2 = char, 3 = string"<<endl;
cin>>type;
if(type == 1)
{
Queue <int> q;
q.enqueue(1);
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
q.enqueue(3);
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
q.enqueue(5);
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
q.dequeue();
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
q.dequeue();
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
q.dequeue();
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
}
if (type == 2)
{
Queue <char> q;
q.enqueue('a');
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
q.enqueue('b');
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
q.enqueue('c');
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
q.dequeue();
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
q.dequeue();
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
q.dequeue();
cout<<"The size is: "<< q.size() <<". And the top is: " << q.front() <<endl;
}
return 1;
}
catch (int e)
{
if (e == 2)
{
cout<<"Call to dequeue() generated an exception, because the queue is empty."<<endl;
}
else if (e == 3)
{
cout<<"Call to front() generated an exception, because the queue is empty."<<endl;
}
}
}
Raw
Queue.cpp
#include "Queue.h"
template <class T>
Queue<T>::Queue(){}
template <class T>
Queue<T>::~Queue(){}
template <class T>
void Queue<T>::enqueue(T value)
{
insertAtBack(value);
}
template <class T>
T using LinkedList<T>::dequeue()
{
if(isEmpty())
{
throw 2;
}
else
{
T firstElmnt = firstNum();
removeFromFront();
return firstElmnt;
}
}
template <class T>
T& using LinkedList<T>::front()
{
if(isEmpty())
{
throw 3;
}
else
{
return firstNum();
}
}
Raw
Queue.h
using namespace std;
#include <iostream>
#include "LinkedList.h"
#ifndef QUEUE_H
#define QUEUE_H
template <class T>
class Queue: public LinkedList<T>
{
public:
Queue();
~Queue();
void enqueue(T value);
T dequeue();
T& front();
};
#endif
@karubian
Copy link

I tried to run it but getting a syntax error at queue.cpp with T using LinkedList stuff

@RazMardi
Copy link

If you're looking for some feedback;

template
int LinkedList::size()
{
if (first == NULL && last == NULL) {return 0;}

Node<T>* temp = first;
int nodeCounter = 0;

while (temp != NULL)
{
    nodeCounter = nodeCounter + 1;
    temp = temp->next;
}
return nodeCounter;

}

Instead of walking the list O(N) operation to find size, I would store size as a private data member in your list and increment/decrement size every time you add and remove nodes. You can then just return size from that function. Also you should be aware of using the const keyword. Mark that size function with const since you shouldn't be modifying anything inside the class.
int LinkedList::size() const

Additionally;
if (first == NULL && last == NULL) {return false;}
will always short circuit, because if your head pointer is NULL then your tail pointer will also be NULL always. You only need to check the head (first) for NULL and then return. You should use your isEmpty() helper function somewhere and call that so you don't repeat code. Mark that const as well since it won't change any of the underlying code.

I'm sorry if I sound like a jerk, I'm just trying to be helpful. Good-work though!

@BSweet16
Copy link

BSweet16 commented Oct 9, 2016 •
edited
Loading

This file returns the following error?

`LinkedList.cpp:9:2: error: ‘first’ was not declared in this scope
first = NULL; // Define first and last

LinkedList.cpp:10:2: error: ‘last’ was not declared in this scope
last = NULL;`

@LaurenzGebauer
Copy link

LaurenzGebauer commented Dec 5, 2017 •
edited
Loading

Dear danopia ,
Thanks for your work, i am getting the same error as the both up here. Could you please explain why this happens? I did some reserach but didnt find any solution.

Queue.cpp:16:3: error: expected unqualified-id before ‘using’
Queue.cpp:32:4: error: expected unqualified-id before ‘using’

@mhassanist
Copy link

In your likedlist.cpp file

in the insertAtBack
Modify this line
Node* newNode ;
to be
Node* newNode = new Node();

@danopia
Copy link
Author

danopia commented Aug 30, 2019

Sorry all, I must've been in a fugue state when I wrote C++, I don't remember this at all. I'd recommend going elsewhere for your linked list needs.

@rafaelwitter
Copy link

how can i invert a linked list template?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment