How to retrieve Last element from Linked List

[bobcat854]

Hi, I'm trying to implement some basic functions for a Singular Linked List. The one I'm currently working on at the moment is the Last function. The purpose of this function is to return the last element. I'm also trying to work on some basic error checking, if the user calls the front/last methods when the list is empty. Unfortunately I'm getting a run time error and my code crashes and I can't seem to figure out why. Check lines 44, 52 for the start of the function definitions. Any help would be greatly appreciated as I'm new to working with Linked Lists!

SLinkedList.h

#ifndef SLINKEDLIST_H
#define SLINKEDLIST_H
#include"MyExceptions.h"

// define the node
template <typename E>
class SNode {					// singly linked list node
private:
	E elem;					// linked list element value
	SNode<E>* next;			// next item in the list
	template<class E> friend class SLinkedList;
};
// interface of the Linked List
template <typename E>
class SLinkedList {				// a singly linked list
public:
	SLinkedList();				// empty list constructor
	~SLinkedList();				// destructor
	bool empty() const;				// is list empty?
	const E& front() const throw(LinkedListException);			// return front element
	const E& last() const throw(LinkedListException);			// return last element
	void addFront(const E& e);			// add to front of list
	void removeFront();				// remove front item list

private:
	SNode<E>* head;				// head of the list
	SNode<E>* tail;				// tail of the list
};


// implementation
template <typename E>
SLinkedList<E>::SLinkedList()
	: head(NULL), tail(NULL) { }                        // Setting the Head & Tail initially to null, as the linked list initially is empty 

template <typename E>
bool SLinkedList<E>::empty() const			// is list empty?
{
	return head && tail == NULL;
}

// returns the front element of the linked list
template <typename E>
const E& SLinkedList<E>::front() const throw(LinkedListException){
	if(empty()) throw LinkedListException ("Front of empty Linked List.");
	
	return head->elem;
}

// returns the last element of the linked list
template <typename E>
const E& SLinkedList<E>::last()  const throw(LinkedListException){
	if (empty()) throw LinkedListException("Last of empty Linked List.");

	while (tail->next != NULL) {
		tail->next;
	}
	return tail->elem;
} 
template <typename E>
SLinkedList<E>::~SLinkedList()			// destructor, To remove the linked list while its not empty
{
	while (!empty()) removeFront();
}

template <typename E>
void SLinkedList<E>::addFront(const E& e) {		// add to front of list
	SNode<E>* v = new SNode<E>;				// create new node
	v->elem = e;					// store data
	v->next = head;					// head now follows v | v now points to the old head node
	head = v;						// v is now the head | head pointer now points to the new element making it the new head
}

template <typename E>
void SLinkedList<E>::removeFront() {			// remove front item

	SNode<E>* old = head;				// save current head
	head = old->next;					// skip over old head
	delete old;						// delete the old head

}

#endif 

MyExceptions.h

  #ifndef MYEXCEPTIONS_H
#define MYEXCEPTIONS_H
#include<string>
using namespace std;
// implement exceptions

class RuntimeException {
private:
	string errorMsg;
public:
	RuntimeException(const string& err) {
		errorMsg = err;
	}
	string getMessage() const { return errorMsg; }
};

class LinkedListException : public RuntimeException {
public:
	LinkedListException(const string& err) : RuntimeException(err) {}
};

#endif

[jonnin]

tail->next;
what do you think this does?
it wouldn't crash but its not helping.

throwing exceptions for an empty container seems harsh, if it were more than for practice/fun.

[bobcat854]

I'm pretty sure tail -> next goes to the next node, right?

[dhayden]

No, tail->next evaluates the expression and throws away the result. If you want to assign it to something then you have to do that explicitly.

But you don't want to do that. Since tail should point to the last element, last() should be dead simple:

template <typename E>
const E& SLinkedList<E>::last()  const throw(LinkedListException){
	if (empty()) throw LinkedListException("Last of empty Linked List.");
	return tail->elem;
} 

The problem is that you aren't maintaining the value of tail. Look at the code. Every time that there's a possibility to change head, there is also a possibility to change tail. You have to figure out what those possibilities are and "do the needful" as my Indian friends are fond of saying.

template <typename E>
bool SLinkedList<E>::empty() const			// is list empty?
{
	return head && tail == NULL;   // same as return (head != NULL) && (tail == NULL);
}

This should never return true. Either Head and tail are both null or they are both non-null.

[mbozzi]

Don't use dynamic exception specifications. That's the word throw(LinkedListException) in
const E& SLinkedList<E>::last() const throw(LinkedListException)
It was removed from the language because it is known bad.

There's been expert consensus on this position since the first C++ standard was published in 1998. The feature was formally deprecated in 2011 and finally removed from the language in 2017.
Why:
1. The specification is not enforced by the compiler;
2. Its appearance often incurs a performance penalty;
3. The dynamic exception specification only contributes to a function's type in certain cases.

http://wg21.link/p0003
http://www.gotw.ca/publications/mill22.htm

[bobcat854]

@dhayden

I made the following changes, as you suggested. When I try to compile, I'm still getting a null pointer exception.

template <typename E>
bool SLinkedList<E>::empty() const			// is list empty?
{
	return (head == NULL) && (tail == NULL);
}


// returns the last element of the linked list
template <typename E>
const E& SLinkedList<E>::last()  const throw(LinkedListException){
	if (empty()) throw LinkedListException("Last of empty Linked List.");
	
	return tail->elem;
}

int main()
{
	SLinkedList<string> a;
	a.addFront("b");
	a.addFront("a");
	cout << a.last();
	 
}

[bobcat854]

@ mbozzi

Sorry, I don't really know what dynamic exception specification is. How would one rewrite this code without using this specification?

[mbozzi]

I don't really know what dynamic exception specification is

Rewrite line 11 in your last post from
const E& SLinkedList<E>::last() const throw(LinkedListException) {
To
const E& SLinkedList<E>::last() const /* throw(LinkedListException) */ {
And do the same in every similar case.

[bobcat854]

@mbozzi

So, I've made the changes. However, when I run the program I'm still getting a null pointer exception. I believe I'm getting this error is because I've initially set both the Head and Tail pointers to be null when the list is empty like this:

// implementation
template <typename E>
SLinkedList<E>::SLinkedList()
: head(NULL), tail(NULL) { }// Setting the Head & Tail initially to null, as the linked list initially is empty  

So when writing tail->elem, it's returning a null pointer?
Which is why my initial post had a while loop traversing through the list to find the point at which tail->next == NULL, break out of the loop and return that element. However another user commented saying it should be as simple as just returning tail-> elem. Could I just get some clarity as to why I'm getting this error and how to properly return the last element in the linked list?

template <typename E>
bool SLinkedList<E>::empty() const			// is list empty?
{
	return (head == NULL) && (tail == NULL);
}

// returns the last element of the linked list
template <typename E>
const E& SLinkedList<E>::last()  const /* throw(LinkedListException) */{
	if (empty()) throw LinkedListException("Last of empty Linked List.");
	
	return tail->elem;
}

int main()
{
	SLinkedList<string> a;
	a.addFront("b");
	a.addFront("a");
	cout << a.last();
	 
}

[dutch]

You need to show your fixed 'addFront' and 'removeFront', too.
Remember that you need to add code to properly set the tail pointer.
It's not going to magically set itself! :)

[bobcat854]

@dutch
Set what tail pointer? I honestly can't see my mistake.

template <typename E>
void SLinkedList<E>::addFront(const E& e) { // add to front of list
	SNode<E>* v = new SNode<E>; // create new node
	v->elem = e;	// store data
	v->next = head; // head now follows v | v now points to the old head node
	head = v;	    // v is now the head | head pointer now points to the new element making it the new head
}

template <typename E>
void SLinkedList<E>::removeFront() { // remove front item

	SNode<E>* old = head; // save current head
	head = old->next; // skip over old head
	delete old;	 // delete the old head

}

[mbozzi]

The problem is that tail is never updated. When an element is added to the front of the list, tail is left NULL.

This linked list design has a special case when adding an element:
If the list is empty (equivalently, if the tail pointer is NULL), then tail must be updated to point to the new element.

To eliminate the special case, place the head node before the beginning of the list, e.g. as in this post:
http://www.cplusplus.com/forum/beginner/253235/#msg1113770

[dhayden]

mbozzi wrote:

To eliminate the special case, place the head node before the beginning of the list

This is a rare case where I'm going to disagree. Making this change would require changes to every method of the list class, so I fear it will confuse the OP more than it will help.

My advice is to fix addFront() and removeFront() to set the tail pointer when necessary.

Also, just to be clear, the symptom that you're having is in last(), but actual bugs are in addFront() and removeFront().

[bobcat854]

@dutch

I have updated some of my code with the tail pointers, to what I feel is correct. Please make any changes if you think otherwise. I'm not getting any null pointer exceptions! However, I'm not getting any output with my int main() looking something like this.

int main()
{
	SLinkedList<string> a;
	a.addFront("c");
	a.addFront("b");
	a.addFront("a");
	cout << a.last();
	
	 
}

addFront()

template <typename E>
void SLinkedList<E>::addFront(const E& e) {		// add to front of list
	SNode<E>* v = new SNode<E>;				// create new node
	v->elem = e;					// store data
	v->next = head;					// head now follows v | v now points to the old head node
	head = v;						// v is now the head | head pointer now points to the new element making it the new head

	while (v->next != NULL) { // Traverses through the linked list until it the last element
		v->next;
	}
	tail = v; // Sets the tail pointer pointing to the last element
}

removeFront()

template <typename E>
void SLinkedList<E>::removeFront() {			// remove front item

	SNode<E>* old = head;				// save current head
	head = old->next;					// skip over old head
	while (old->next != NULL) {			// Traverses through the list until it finds the last element
		old->next;						// Sets the last element to the tail element
	}
	tail = old;
	delete old;						// delete the old head

}

[keskiverto]

Having a tail is just cached data; singly linked list does not desperately need it.

Plan B, keep it simple: Remove the member tail entirely.

[bobcat854]

@keskiverto
It's like a practice exercise for the Data Structures course, I'm currently taking. The prof wants it done with both the head and tail pointers. The sample code we had to work off only had the head pointer. I know I'm pretty close to getting the last output of the linked list... just need a bit more guidance.

[keskiverto]

Ok,

First notes.
Modern C++ has nullptr that is more precise than the C's NULL macro.

template <typename E>
SLinkedList<E>::SLinkedList()
: head(nullptr), tail(nullptr)
{ }

If list is empty, then head is empty, isn't it? Can the tail be non-empty, if the head is empty?
If not, why test both?

You add to the front. When does the tail change?
When the first node is added. After that the tail node remains the same no matter how many nodes you add to the front.

You remove from the front. When does the tail change?
It becomes nullptr when you remove the last node.

[dhayden]

Your new code for addFront and removeFront may work, but it's inefficient. If the list is hundreds or thousands of items long, then you'll walk down the whole thing to set tail.

Assume that tail is set correctly when you enter these functions. What must you do to update it? If you think this through, you'll find that there's a much easier way.