current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 4 down vote favorite

The vast majority of my experience is in writing managed code. I'm putting myself through C++ boot camp right now and trying to really wrap my head around pointers and memory management in general. Right now I'm working out of Gayle Laakmann's Cracking the Coding Interview. I've used it before for other languages and am revisiting it for C++.

Here, I'm mostly concerned about memory management, but would also like to hear about any other C++ faux pas that might make me look bad in a whiteboarding session. I'll be moving on to other data structures after this, but this is my springboard, so I want to adjust as early as possible to write good code. The exercises I did are outlined in in main() with their outputs. I think out of all of this, I'm most concerned about how I'm approaching deleteDuplicateEntries for exercise 2.1.

Also, any positive comments about implementation would be much appreciated so I make sure I continue to do what's working well.

#include <iostream>

template <class Type>
class ListNode {
public:
    ListNode(Type input): value(input), next(NULL) {}
    void setValue(Type input) {
        value = input;
    }
    Type getValue() {
        return value;
    }
    void setNext(ListNode *nextTarget) {
        if(nextTarget != NULL) {
            next = nextTarget;
        }
    }
    ListNode * getNext() {
        return next;
    }
private:
    Type value;
    ListNode<Type> *next;
};

// singly linked list
template <class Type>
class List {
public:
    List(Type value) {
        _head = new ListNode<Type>(value);
        _tail = _head;
        _size = 1;
    }
    ~List() {
        // second param deletes as it traverses
        traverseHeadToTail(false, true);
    }
    // inserts at the end of the list
    void append(Type value) {
        ListNode<Type> *newNode = new ListNode<Type>(value);
        _tail->setNext(newNode);
        _tail = newNode;
        _size++;
        // if this makes two items, point head to tail
        if(_size == 2) {
            _head->setNext(_tail);
        }
    }
    // inserts at the head of the list
    void prepend(Type value) {
        ListNode<Type> *newNode = new ListNode<Type>(value);
        ListNode<Type> *formerHead = _head;
        _head = newNode;
        _head->setNext(formerHead);
        _size++;
    }
    // note this inserts AFTER the position
    void insertAtPosition(int pos, Type value) {
        // validate, optimization
        if(!isPosValid(pos)) { return; }
        if(pos == 1) { prepend(value); return; }
        if(pos == _size) { append(value); return; }

        ListNode<Type> *newNode = new ListNode<Type>(value);
        ListNode<Type> *targetNode = getNodeAtPos(pos);
        ListNode<Type> *nextNode = targetNode->getNext();
        targetNode->setNext(newNode);
        newNode->setNext(nextNode);
        _size++;
    }
    void deleteAtPosition(int pos) {
        if(!isPosValid(pos)) { return; }
        if(_size == 1) {
            std::cout << "List must have at least one element to exist\n";
            return;
        }
        ListNode<Type> *targetNode = getNodeAtPos(pos);
        // handle for deletes at beginning and end
        if(pos == 1) {
            _head = getNodeAtPos(2);
        } else if (pos == _size) {
            _tail = getNodeAtPos(_size - 1);
        } else {
            // inside list delete
            ListNode<Type> *prevNode = getNodeAtPos(pos - 1);
            ListNode<Type> *nextNode = targetNode->getNext();
            prevNode->setNext(nextNode);
        }
        delete targetNode;
        _size--;
    }
    void writeAtPosition(int pos, Type value) {
        if(!isPosValid(pos)) { return; }
        getNodeAtPos(pos)->setValue(value);
    }
    void printList() {
        std::cout << "Printing list contents...\n";
        traverseHeadToTail(true, false);
    }
    int getSize(bool printSize) {
        if (printSize) { std::cout << "The size is " << _size << "\n"; }
        return _size;
    }
    void deleteDuplicateEntries() {
        if(_size == 1) { return; }
        Type firstValue = _head->getValue();
        List<Type> *uniqueList = new List<Type>(firstValue);
        int newSize = 1;
        ListNode<Type> *curNode = _head;
        while(curNode->getNext() != NULL) {
            Type curNodeVal = curNode->getValue();
            if(!valueExistsInList(uniqueList, curNodeVal)) {
                uniqueList->append(curNodeVal);
                newSize++;
            }
            curNode = curNode->getNext();
        }
        // delete all nodes and their children (old list)
        traverseHeadToTail(false, true);
        _head = uniqueList->getNodeAtPos(1);
        _size = newSize;
    }
    bool valueExistsInList(List<Type> *listIn, Type value) {
        if(listIn->getSize(false) == 1 && (listIn->getValueAtPosition(1) == value)) { return true; }
        ListNode<Type> *curNode = listIn->getNodeAtPos(1);
        while(curNode->getNext() != NULL) {
            if(curNode->getValue() == value) {
                return true;
            }
            curNode = curNode->getNext();
        }
        return false;
    }
    Type getValueAtPosition(int pos) {
        if(!isPosValid(pos)) { return 0; }
        ListNode<Type> *targetNode = getNodeAtPos(pos);
        return targetNode->getValue();
    }
    Type getNthToLastValue(int n) {
        if (n == 0) { std::cout << "Invalid position\n"; return NULL; }
        int targetPos = (_size + 1) - n;
        if(!isPosValid(targetPos)) { return NULL; }
        return getValueAtPosition(targetPos);
    }
    ListNode<Type> * getNodeAtPos(int pos) {
        if(!isPosValid(pos)) { return NULL; }
        ListNode<Type> *curNode = _head;
        for(int i = 1; i <= _size; i++) {
            if(i == pos) { return curNode; break; }
            curNode = curNode->getNext();
        }
        return NULL;
    }
private:
    ListNode<Type> *_head;
    ListNode<Type> *_tail;
    int _size;
    ListNode<Type> * traverseHeadToTail(bool printList, bool destroyAll) {
        ListNode<Type> *curNode = _head;
        ListNode<Type> *nextNode = _head->getNext();
        int count = 1;

        // if we need to print and there's only one element
        if(printList && nextNode == NULL) { std::cout << count << ". " << curNode->getValue() << "\n"; }

        while(curNode->getNext() != NULL) {
            if(printList) { std::cout << count << ". " << curNode->getValue() << "\n"; }
            if(destroyAll) { delete curNode; }
            curNode = nextNode;
            nextNode = curNode->getNext();
            count++;
        }

        // if the list was larger than one, print the last element's value
        if(printList && count > 1) { std::cout << count << ". " << curNode->getValue() << "\n"; }

        if(destroyAll) {
            delete curNode;
            return NULL;
        } else {
            return curNode;
        }
    }
    bool isPosValid(int pos) {
        bool result = true;
        if(pos > _size || pos <= 0) {
            std::cout << "Position " << pos << " is out of bounds\n";
            result = false;
        }
        return result;
    }
};

List<int> * addLinkedListNumbers(List<int> *inOne, List<int> *inTwo) {
    // the sizes of each list need to match, if they don't: adjust
    int oneSize = inOne->getSize(false);
    int twoSize = inTwo->getSize(false);
    while(oneSize != twoSize) {
        if(oneSize < twoSize) {
            inOne->append(0);
            oneSize++;
        } else {
            inTwo->append(0);
            twoSize++;
        }
    }
    // now that they match, add them
    List<int> *result = new List<int>(0);;
    int place = 1;
    bool carry = false;
    while(oneSize > 0) {
        int sum = inOne->getValueAtPosition(place) + inTwo->getValueAtPosition(place);
        if(carry) { sum++; carry = false; }
        if(sum > 9) {
            sum = sum - 10;
            carry = true;
        }
        if(oneSize == twoSize) {
            result->writeAtPosition(1, sum);
        } else {
            result->append(sum);
        }
        oneSize--;
        place++;
    }
    return result;
}

int main() {

    // 2.1 - Write code to remove duplicates from an unsorted linked list.
    // make a list full of unsorted duplicates
    List<std::string> *myDuplicateList = new List<std::string>("a");
    myDuplicateList->append("b");
    myDuplicateList->append("a");
    myDuplicateList->append("1");
    myDuplicateList->append("a");
    myDuplicateList->append("z");
    myDuplicateList->append("a");
    myDuplicateList->append("a");
    myDuplicateList->append("1");

    myDuplicateList->deleteDuplicateEntries();
    myDuplicateList->printList();
    // print size
    myDuplicateList->getSize(true);
    // output
    // Printing list contents...
    // 1. a
    // 2. b
    // 3. 1
    // 4. z
    // The size is 4


    // 2.2 - Implement an algorithm to find the nth to last element of a singly linked list.
    std::cout << "The third to last value is " << myDuplicateList->getNthToLastValue(3) << "\n";
    // output
    // The third to last value is b
    delete myDuplicateList;

    // 2.4
    // You have two numbers represented by a linked list, where each node contains a single
    // digit. The digits are stored in reverse order, such that the 1’s digit is at the head of
    // the list. Write a function that adds the two numbers and returns the sum as a linked list.
    // EXAMPLE
    // Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
    // Output: 8 -> 0 -> 8

    // represents decimal 1513
    List<int> *numListOne = new List<int>(3);
    numListOne->append(1);
    numListOne->append(5);
    numListOne->append(1);

    // 295
    List<int> *numListTwo = new List<int>(5);
    numListTwo->append(9);
    numListTwo->append(2);

    std::cout << "Adding 1513 to 295\n";

    List<int> *result = addLinkedListNumbers(numListOne, numListTwo);

    std::cout << "Sum is ";
    for(int i = result->getSize(false); i > 0; i--) {
        std::cout << result->getValueAtPosition(i);
    }
    std::cout << std::endl;
    // output
    // Adding 1513 to 295
    // Result is 1808

    delete numListOne;
    delete numListTwo;
    delete result;
}
share|improve this question
    
Search for "c++ template code bloat" and you'll likely get a thousand different ideas, but unfortunately, many of them factually incorrect. This web site describes what I mean. – Edward Mar 9 at 22:39
    
As for interviewing: best advice is to learn the language as well as you can and then be honest about what you know and what you don't. With practice (and by asking for additional code reviews here), you'll get better fast. – Edward Mar 9 at 22:40
    
@Edward Thanks, trying to move my career forward and I can't express how helpful this is. – Charles Mar 9 at 22:44
    
You'll have to join a user in a chatroom for extended discussions. Responses shouldn't be added to questions. – Jamal♦ Mar 13 at 1:45
up vote 4 down vote accepted

It's not bad code, especially if the goal is to practice using pointers, but the extensive use of pointers makes it look like somewhat old-style C++. With that said, here are some suggestions for you you might improve your code.

Avoid using pointers

Modern C++ doesn't really need pointers very often. It's usually better to either use a smart pointer, such as std::unique_ptr or simply use objects or object references.

Avoid new and delete

If you don't use pointers, you have much less reason to use new and delete. But if you do use new, each instance of new must be matched to a corresponding delete. In this particular case, this code leaks memory in the deleteDuplicateEntries() routine.

Think about code bloat

If we have a List of integers and a List of std::string, each of those will have a comletely independent implementation due to the magic of templates. This can often be a good thing, but it can cause code bloat, meaning that you have much more code in the resulting executable than is actually needed to do the job. I often work with embedded systems in which this can be a really important aspect of the design. One way to reduce that, while preserving the benefits of using templates, is to implement a concrete class that uses void * to point to the member. The template version, then, only adds the appropriate casts, maximizing common code.

Use the required #includes

The code uses std::string which means that it should #include <string>. It was not difficult to infer, but it helps reviewers if the code is complete.

Don't use leading underscores in names

Anything with a leading underscore is a reserved name in C++ (and in C). See this question for details.

Don't use std::endl if you don't really need it

The difference betweeen std::endl and '\n' is that '\n' just emits a newline character, while std::endl actually flushes the stream. This can be time-consuming in a program with a lot of I/O and is rarely actually needed. It's best to only use std::endl when you have some good reason to flush the stream and it's not very often needed for simple programs such as this one. Avoiding the habit of using std::endl when '\n' will do will pay dividends in the future as you write more complex programs with more I/O and where performance needs to be maximized.

Throw errors rather than printing error messages

The user of your code may be creating a GUI with no command line available and will not appreciate having your code printing instead of indicating an error to the calling code. The two ways that C++ programs generally signal an error are either by throwing an exception (if the circumstance really is exceptional) or by returning a value that indicates an error.

Don't expose class internals

Outside of class List, there is really no need for any other code to have access to or see the structure of ListNode. It would probably be better to simply make this a struct internal to class List.

Use const where practical

The printList and getSize member functions of class List do not alter the underlying object and therefore should be declared const.

Simplify class interfaces

There is a lot of extra stuff that complicates the code and is not really necessary. A prime example is this:

int getSize(bool printSize) {
    if (printSize) { std::cout << "The size is " << _size << "\n"; }
    return _size;
}

I would strongly advocate simply writing this:

std::size_t size() const { return m_size; }

If the caller wants to print the value, that should be its business. It doesn't really belong here. Similarly, the additional arguments to traverseHeadToTail simply complicate and slow down the code because it checks both flags for every single node in the list.

Use a more efficient algorithm

The deleteDuplicateEntries() routine is not very efficient. There's no need to traverse the entire list for each value. If we proceed from the head to the tail, we know that there cannot be any duplicates in the part of the list we've already processed, so all that's necessary is to search the remainder of the list. Here's how I'd do it:

void deleteDuplicateEntries() {
    for (ListNode<Type> *curr = _head; curr && curr->next; curr = curr->next) {
        ListNode<Type> *n = curr;
        for (  ; n && n->next; n = n->next) {
            while (n->next && curr->value == n->next->value) {
                // delete matching node
                auto victim = n->next;
                n->next = victim->next;
                --_size;
                if (_tail == victim) {
                    _tail = n;
                }
                delete victim;
            }
        }
        // does last node match?
        if (n && n->value == curr->value) {
            delete n;
            --_size;
            curr->next = nullptr;
            _tail = curr;
        }
    }
}

Use nullptr rather than NULL

Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful.

Consider using assert for tests

The code functions and demonstrates how the List is to be used, but one nice enhancement would be for the code to automatically tell the user if the results were correct or not. Right now, that's in the comments, but I'd suggest that using an assert would make it much easier for a user to see that everything is working correctly.

share|improve this answer
    
"This means that any calling code could arbitrarily set that to some other value, like nullptr" Nope, the calling code can only modify the instance pointed by the pointer, but not the pointer itself, as it is passed by value and not by reference – Rakete1111 Mar 9 at 16:28
    
@Rakete1111 You're right. I've corrected my answer. Thanks! – Edward Mar 9 at 16:34
    
@Edward Thank you so much! I have bunch more questions now and wasn't sure how to get them in here without adding them to the original question. Thanks again in advance for any further expertise you provide! – Charles Mar 9 at 19:42
1  
I disagree with the comment on pointers. Yes modern code should definitely prefer smart pointers or other tools over old RAW pointers. But there are certain situations where pointers are acceptable (as long as they don't leak out of your class and you just use them internally). Building containers is one such situation. – Loki Astari Mar 9 at 21:32
    
@LokiAstari Perhaps I should have phrased it as "prefer smart pointers to raw pointers" rather than "avoid using pointers." As you rightly point out, using pointers judiciously is still a handy and valuable technique. – Edward Mar 9 at 21:45
up vote 1 down vote

Here is a more senior level addition: Dont use linked lists at all in C and C++. Basically every iteration is a cache miss. An std::vector will be around 100 times faster when accessed linearly. Also random access is much slower. There is only a theoretical advantage for inserting elements (again, cache misses until finding the element usually means a vector would be already shifted and ready before you could relink the list).

Linked list are a great example for pointers, but generally should not appear in production code.

share|improve this answer

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.