# Is this a properly implemented linked list class?

The code below is a class implementation of a linked list. I DO have concerns. For example, is it normal for the class to have at least one node? In other words, this implementation cannot have an empty linked list. The length is always 1. Lastly, would this be a proper way to implement a linkedList in, say, a professional environment? Or perhaps there is a better way to do it? I am not a professional in any way, mind you, just a college freshman.

Here is the cpp file

#include "ListNode.h"
#include <iostream>
#include <climits>

using namespace std;

ListNode::ListNode()
{
}

ListNode::ListNode(int value, ListNode* node){
this->value = value;
this->next = node;
}

void ListNode::setNext(ListNode* node){
this->next = node;
}

void ListNode::setValue(int value){
this->value = value;
}

ListNode* ListNode::getNext(){
return this->next;
}

int ListNode::getValue(){
return this->value;
}

int ListNode::getLength(){
if (this != NULL){//if this is not NULL
if ((*this).getNext() == 0)
return 1;
else{
ListNode* temp = this;
int count = 0;
while (temp != 0){
count++;
temp = (*temp).getNext();
}//end while
temp = NULL;
return count;
}//end else
}//end if
return 0;
}

void ListNode::replace(int position, int value){
ListNode* temp = this;
if (position > -1 && position < getLength()){
for (int i = 0; i < position; i++){
temp = (*temp).getNext();
}//end for
(*temp).setValue(value);
}//end if
else
cout << "Desired index is out of bounds by " << getLength() - position + 1 << " units" << endl;
temp = NULL;
}

void ListNode::remove(int position){
ListNode* temp = this;
if (position > -1 && position < getLength()){
for (int i = 0; i < position - 1; i++){
temp = (*temp).getNext();
}//end for
(*temp).setNext((*(*temp).getNext()).getNext());
}//end if
else
cout << "Desired index is out of bounds by " << getLength() - position+1 << " units" << endl;
temp = NULL;
}

ListNode* temp = this;
ListNode* temp2;
if (position > -1 && position < getLength() + 1){
if (position == 0){
}//end if
else
if (position == getLength()){
}//end else if
else{
for (int i = 0; i < position - 1; i++){
temp = (*temp).getNext();
}//end for
temp2 = (*temp).getNext();
(*temp).setNext(new ListNode(value, temp2));
}//end else
}//end if
else
cout << "Desired index is out of bounds by " << getLength() - position << " units" << endl;
temp = NULL;
temp2 = NULL;
}

ListNode* temp = this;
while ((*temp).getNext() != 0){
temp = (*temp).getNext();
}
(*temp).setNext(new ListNode(value, NULL));
temp = NULL;
}

ListNode* temp = (*this).getNext();
int num = (*this).getValue();
(*this).setValue(value);
(*this).setNext(new ListNode(num, temp));
temp = NULL;
}

int ListNode::elementAt(int position){
if (this == 0 || (*this).getLength() <= position)
return INT_MIN;
ListNode* temp = this;
for (int i = 0; i < position; i++){
temp = (*temp).getNext();
}
int num = (*temp).getValue();
temp = NULL;
return num;
}

int ListNode::indexOfElement(int value){
ListNode* temp = this;
for (int i = 0; i < (*this).getLength(); i++){
if ((*temp).getValue() == value)
return i;
temp = (*temp).getNext();
}
temp = NULL;
return -1;
}

int ListNode::lastIndexOfElement(int value){
ListNode* temp = this;
int count = -1;
for (int i = 0; i < (*this).getLength(); i++){
if ((*temp).getValue() == value)
count = i;
temp = (*temp).getNext();
}
temp = NULL;
return count;
}

void ListNode::deleteFirstElement(){
ListNode* temp = this;
if ((*(*this).getNext()).getNext() == 0){//if there are only two nodes
temp = (*temp).getNext();
(*this) = *temp;
(*this).setNext(0);
delete temp;
}
else{//if there are more than two nodes
temp = (*temp).getNext();
(*this) = *temp;
temp = (*temp).getNext();
(*this).setNext(temp);
temp = NULL;
}
}

void ListNode::deleteLastElement(){
ListNode* temp = this;
while ((*(*temp).getNext()).getNext() != 0){
temp = (*temp).getNext();
}
(*temp).setNext(0);
temp = NULL;
}

void ListNode::printList(){
ListNode* temp = this;
while (temp != NULL){
cout << (*temp).getValue() << " ";
temp = (*temp).getNext();
}//end while
cout << endl;
}

ListNode::~ListNode()
{
}


#pragma once
class ListNode
{
public:
ListNode();
ListNode(int, ListNode*);
void setValue(int);
void setNext(ListNode*);
int getValue();
void deleteFirstElement();
void deleteLastElement();
int getLength();
int indexOfElement(int);
int lastIndexOfElement(int);
int elementAt(int);
void addAt(int, int);//adds new node with specified value to the specified index...other elements are then shifted(index, value)
void remove(int);//removes first instance of node at specified index
void replace(int, int);//replaces value at specified index with new value, respectively(index, value);
void deleteElement(int, int);
void printList();
ListNode* getNext();
~ListNode();
private:
ListNode* next = 0;
int value;

};//end class

-
It would be helpful for reviewers if you also posted your header. That way, we can see your overall design without looking at all the implementation details. –  red_eight Dec 16 '13 at 5:04
Certainly. Ive added the header file. –  Chuck Onwuzuruike Dec 16 '13 at 5:12
Don't worry; you're not alone. C++ takes just a few lifetimes to master. –  200_success Dec 23 '13 at 10:54
Please remember to upvote any answers you've found useful. You may also accept the answer you've found most helpful, if you think this applies to any. –  Jamal Jan 22 '14 at 15:19

For example, is it normal for the class to have at least one node? In other words, this implementation cannot have an empty linked list. The length is always 1.

No, a linked list can be empty (i.e. size 0).

But there are designs that intentionally always have at least one member in the list. This special member is referred to as a sentinel and should not hold any data or be counted as a member of the list in terms of size. So if the only member of the list is a sentinel, the size is zero.

There are design advantages to using a sentinel as the list never has any NULL pointers. This actually makes implementing the list easier (as you don't have to check for the NULL special case).

Lastly, would this be a proper way to implement a linkedList in, say, a professional environment?

Even without looking at it, I would still have to say that std::list would be preferred in a professional environment as it comes from the Standard Template Library (STL). That said, I'd recommend closely following the STL while studying best practices in the language from any trusted reference material at your disposal. Practicing writing your own list, however, would be helpful for learning how the linked list implementation works under the hood.

After looking at it further, it already looks like an uncommon implementation. There's only one class which, based off the name, seems to resembles a node. However, the implementation seems more like a list itself with the basic aspects of a node, primarily as the private data members. They're two separate entities and should have their own properties, which I will explain below.

You should have two main entities - the linked list itself (as a class) and a node (as a class or as a struct). The node structure should be a private member of the linked list class. The node just has two data members - a value (of some type or a templated type) and a pointer to the next node (and the previous node if it's a doubly-linked list). The linked list class handles the list operations and maintains a pointer to the head node, which should also be private. The head node points to NULL (or a sentinel) if the list is empty, or the first node if it's not. It should also maintain a private size, based on the number of nodes (excluding a sentinel). The size should also be accessible to the client via a public accessor ("getter") function.

Moreover, I'll point out some general flaws and other points in your code with no regard to the above:

• Your accessors (or "getters") should be const. This prevents data members from possibly being modified in the function. This is important because you want to make sure the accessors return the unchanged data member in order to avoid bugs. This also helps ensure const correctness.

• Linked lists add nodes by allocating new memory. In C++, that's done with new. You also need to deallocate the memory with delete when you're finished with it. If you do not, you'll experience memory leaks. This deallocation should be done in the destructor, specifically with a loop that destroys each node with delete.

• You're interchanging pointer->member and (*pointer).member. Prefer the -> operator as it is more readable and "less-awkward" than the other.

-
NULL is just integer 0; using it or not is more a matter of style than a strict flaw. I'd definitely prefer nullptr in a C++11 environment. –  user2357112 Dec 16 '13 at 7:00
There is no need to set the head pointer back to nullptr in a destructor. –  Anton Golov Dec 16 '13 at 7:35
@user2357112: Yes, I was going after style there, but I didn't quite mention it since I'm very used to seeing NULL with linked lists. –  Jamal Dec 16 '13 at 15:20
@AntonGolov: True. I thought I remember once having to do that, but it must've been with a separate function other than the destructor. I'll keep that in mind. –  Jamal Dec 16 '13 at 15:21

I haven't looked at all of you code, but here are a few things that jumped out to me:

Typically, a linked list is composed of two classes. One class represents the list and the other class represents a node in the list.

class ListNode
{
public:
ListNode () ;
ListNode (const int data, const ListNode *next) ;
~ListNode () ;

// Other functions, maybe a getNext, getData, etc...

private:
int data ;
ListNode *next ;
ListNode *previous ; // Optional
};

{
public:
// Constructors, destructors..
// Functions such as insert, remove, getSize, etc...

private:
ListNode *tail ; // Optional
};


You constructor does not initialize your variables. You should use a constructor initialization list.

ListNode::ListNode() : value (0), next (NULL) // or nullptr for C++11
{
}


This is a bug:

if (this != NULL){//if this is not NULL


There is no scenario where this could be NULL. If this was NULL and you tried to call a member function, then you would get undefined behavior. For example:

ListNode node (5, NULL) ; // create on stack
ListNode *node2 = node.getNext () ; // gets a NULL pointer
node2->getLength () ; // oops, we dereferenced a NULL pointer, undefined behavior!


Don't use this notation: (*temp).getNext();.
Use temp->getNext() instead.

An important topic that @Jamal touched up on is Dynamic Memory Ownership.
Let's say you do something like this:

void someFunction (ListNode *list)
{
ListNode node (5, NULL) ;
list->setNext (&node) ;
}

// Somewhere else in the code
ListNode list (0, NULL) ;
someFunction (&list) ;
int n = list.elementAt (1) ; // Why is it crashing here?


What's happening here is that node was allocated on the stack.
Once someFunction exits, node is popped off the stack and is garbage data.
It may not cause your program to crash everytime, but it is undefined behavior.
A container typically wants to take ownership of whatever data is being inserted into it. This is done by calling new when inserting the object into the container and calling delete inside a destructor.

-
In your last bit of code, there is no dynamically allocated memory and so cannot be a memory leak; however, there probably is undefined behaviour. –  Anton Golov Dec 16 '13 at 7:35
dereferencing a NULL is not necessarily a segfault but undefined behavior, or in other words all bets are off on what it will actually do –  ratchet freak Dec 16 '13 at 9:07
@AntonGolov : Thanks for catching that. –  red_eight Dec 17 '13 at 2:17
@ratchetfreak : Thanks for clarifying that. –  red_eight Dec 17 '13 at 2:19
• Don't print error messages to cout, as that hurts reusability. I suggest changing the methods to return true on success and false on failure. The reason for the failure should be obvious enough to the caller. (If you must print error messages, direct them to cerr instead of cout.)
• Avoid calling .getLength(), as that requires you to traverse the entire list. For example, .elementAt() could be

int ListNode::elementAt(int position) {
// You can't call a method on nullptr, so you don't need to check if
// this == 0.  Instead of .getLength(), check for the end of the list
// in the loop below.
//
// if (this == 0 || (*this).getLength() <= position)
//     return INT_MIN;
ListNode* temp = this;
for (int i = 0; i < position; i++) {
if (!temp) {
return INT_MIN;
}
temp = temp->getNext();
}
return temp->getValue();
// Since temp is a local variable, we don't care what its value is
// after the function returns.
// temp = NULL;
}

• In .addAt(), you shouldn't need the special case

if (position == getLength()) {
}

• The name .addAppend() is awkward; .append() should suffice.
• Using similar principles, you could simplify .getLength() by eliminating all the special cases:

int ListNode::getLength() {
int count = 0;
for (ListNode *temp = this; temp; temp = temp->getNext()) {
count++;
}
return count;
}

-
An alternative to error codes would be to throw exceptions. Also, a private variable could be used to keep track of the size of the list. This would make the getLength () method an O(1) operation. –  jliv902 Dec 23 '13 at 16:36
@jliv902 Keeping track of the length is only practical if you do it in a LinkedList object. If you do it in the ListNode class, some operations become expensive. For example, when you insert an element at the head of the list, you would have to increment the length field of every single node. –  200_success Dec 23 '13 at 17:24
elementAt will segfault if position equals the list length. –  David Harkness Feb 5 '14 at 3:31
@DavidHarkness In C/C++, the usual attitude is that if you make an "illegal" request like accessing an element beyond the end of a list, you deserve to crash. –  200_success Feb 5 '14 at 3:44
@200_success In that case, it should crash whether you're 1 beyond or 500, but here it returns INT_MIN if more than 1 beyond the end. Consistency is key. –  David Harkness Feb 5 '14 at 4:04