Implementing a proper linked list for a professional environment

Question

I have some concerns:

1. 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.

2. Would this be a proper way to implement a linked list 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.

Implementation 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;
}

void ListNode::addAt(int position, int value){
    ListNode* temp = this;
    ListNode* temp2;
    if (position > -1 && position < getLength() + 1){
        if (position == 0){
            addInfront(value);
        }//end if
        else
        if (position == getLength()){
            addAppend(value);
        }//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;
}

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

void ListNode::addInfront(int value){
    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()
{
}

Header file:

#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 addAppend(int);//adds new node with corresponding value to end of LinkedList
    void addInfront(int);//add new node with corresponding value at the begining of the LinkedList
    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

Answer 1

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:

• Prefer nullptr to NULL if you're using C++11.

• 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.

Answer 2

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
};

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

private:
    ListNode *head ;
    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.

Answer 3

• 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()) {
      addAppend(value);
  }
  

• 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;
  }