Take the tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

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()
{
}

Here is the 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
share|improve this question
1  
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 2 hours ago
 
Certainly. Ive added the header file. –  Chuck Onwuzuruike 2 hours ago
add comment

2 Answers

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 a segmentation fault. 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, segmentation fault!


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) ; // Memory leak most likely.
}

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

share|improve this answer
 
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 15 mins ago
add comment

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. Such lists always have a head node that either points to the first node in the list or NULL if the list is empty. If the list is empty, then the length is 0.

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 was also created by experts, same as the Standard Template Library as a whole. If you want to ensure your code is as professional as possible, I'd recommend closely following the STL while studying best-practices in the language. As a college freshman, you still have a long way to go. Heck, I'm a college senior, and I still have a long way to go! But not every student desires to seek knowledge outside the classroom, and I commend you for asking for help here. You're on the right track!

After looking at it now, 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 that of the 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 classes - the list itself and a node (although the node can instead be a struct). The node class should be a private member of the linked list class. The node class just has two data members - a value (of some type) and a pointer to the next node. 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 if the list is empty, or the first node if it's not.


Moreover, I'll point out some general flaws in your code with no regards to the above:

  • The linked list's next pointer should point to NULL or nullptr (in C++11) instead of 0. NULL corresponds to a memory address of 0, and pointers should point to memory addresses.

  • 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. As such, you need to deallocate the memory with delete when you're finished with the list. If you do not, you'll experience memory leaks. This deallocation should be done in the destructor, specifically in the form of a loop that deletes each node and (ideally) sets the head pointer back to NULL.

  • You're inconsistently using pointer->value and (*pointer).value. Prefer the former as it is more readable than the latter.

share|improve this answer
1  
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 50 mins ago
 
There is no need to set the head pointer back to nullptr in a destructor. –  Anton Golov 15 mins ago
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.